はじめに
多項式環や形式的冪級数環上の意味のある線形変換について、その転置もまた意味のある線形変換であることが多い。また、行列 $A$ について $v\mapsto Av$を計算するアルゴリズムを「転置」することで、$w\mapsto A^T w$ を計算するほぼ同じ計算量のアルゴリズムが得られる(転置原理、X^N mod P(X) の計算: 行列の転置とアルゴリズムの転置)。
以下では、多項式環や形式的冪級数環上のいくつかの自然な線形変換について、その転置がどのような問題になるか考えてみる。
線形変換の転置と行列の転置
以降は線形空間はすべて共通の体 $\mathbb{F}$ 上の有限次元線形空間とする。
線形空間 $V, W$ について $T\colon V\to W$ を線形写像とする。$V$ の基底 $(v_i)_i$ と $W$ の基底 $(w_j)_j$ について、$T$ の行列表現 $A$ は以下のように定まる。
T v_i = \sum_j A_{j,i} w_j
ここで $A_{j,i}$ は行列 $A$ の $(j,i)$-成分である。
行列 $A$ の転置 $A^T$ は $(A^T)_{j,i}=A_{i,j}$ で定義される行列である。線形写像 $T$ が $A$ で表現されるとき、$A^T$ はどのような線形写像を表現しているのであろうか。一般的には
- 双対写像(転置写像)
- 非退化双線形形式から定まる随伴写像
という二通りの説明がある。線形写像 $T\colon V\to W$ の双対写像 $T^T \colon W^* \to V^*$ について、$T$ の行列表現 $A$ に用いた $V,\,W$ の基底の双対基底を用いて $T^T$ を表現する行列が $A^T$ となる。このような議論は複雑であるし、本稿においては特に利点もないので非退化双線形形式から定まる随伴写像の解釈を採用する。しかし、これらの解釈に本質的な違いはない。
$\langle\cdot,\,\cdot\rangle\colon V\times V\to \mathbb{F}$ は以下を満たすとき双線形形式である。
- $\langle w, av+bv'\rangle = a\langle w,v\rangle + b\langle w, v'\rangle\qquad\forall v,v',w\in V,\, a,b\in\mathbb{F}$.
- $\langle aw+bw', v\rangle = a\langle w,v\rangle + b\langle w', v\rangle\qquad\forall v,w,w'\in V,\, a,b\in\mathbb{F}$.
また、
- $\forall v\in V\setminus\{0\},\exists w\in V\quad \langle w,v\rangle \ne 0$.
- $\forall w\in V\setminus\{0\},\exists v\in V\quad \langle w,v\rangle \ne 0$.
を満たすとき双線形形式は非退化であるという。
また、
- $\forall v,\, v'\in V\quad \langle v,v'\rangle = \langle v',v\rangle$
を満たすとき双線形形式は対称であるという。
非退化な双線形形式 $\langle\cdot,\,\cdot\rangle$ が $V$ と $W$ の両方に定義されているとき、$T\colon V\to W$ の随伴写像 $T^*\colon W\to V$ は
\langle w, T(v)\rangle = \langle T^*(w), v\rangle\qquad\forall v\in V, w\in W
を満たす唯一ものと定義する。
上記の条件を満たす線形写像 $T^*$ は唯一存在する。
$V$ の基底 $(v_i)_i$ を任意に選んだとき、 $\varphi\colon\, v' \mapsto (\langle v', v_i\rangle)_i$ は単射である。実際もし $v', v''\in V$ について $(\langle v',v_i\rangle)_i = (\langle v'',v_i\rangle)_i$ が成り立つとすると、線形性より $\langle v'-v'',v_i\rangle=0$ が任意の $i$ で成り立つ。このとき $\langle v'-v'', v\rangle = 0$ が任意の $v\in V$について成り立つ。よって非退化性の仮定より $v'=v''$ である。また、$\varphi$ を線形写像として見たときに入出力の次元は等しいため、$\varphi$ は全単射である。随伴写像の定義より、任意の $w\in W$について
T^*(w) = \varphi^{-1}\bigl((\langle T^*(w), v_i\rangle)_i\bigr)
= \varphi^{-1}\bigl((\langle w, T(v_i)\rangle)_i\bigr)
と定まるので、写像 $T^*$ は一意に定まる。$T^*$の線形性は明らか。
$V$の基底のペア $((v_i)_i, (\tilde{v}_i)_i)$ が
\langle \tilde{v}_i, v_j\rangle =\delta_{i,j}
を満たすとき(正規)双直交基底という。ここで $\delta_{i,j}$はクロネッカーのデルタである。
また、$((v_i)_i,(v_i)_i)$が双直交基底のとき、$(v_i)_i$を正規直交基底という。双線形形式が正規直交基底を持つとき、双線形形式は対称であるが逆は必ずしも成り立たない。
$V$ の双直交基底 $((v_i)_i,(\tilde{v}_i)_i)$と $W$ の双直交基底 $((w_j)_j,(\tilde{w}_j)_j)$ を任意に選んだとき、基底 $(v_i)_i, (w_j)_j$による $T\colon V\to W$ の行列表現と $(\tilde{w}_j)_j, (\tilde{v}_i)_i$による $T^*\colon W\to V$ の行列表現は転置の関係にある。
$T$の行列表現を $A$、$T^*$の行列表現を $B$とすると
A_{i,j} = \langle \tilde{w}_i, T(v_j)\rangle = \langle T^*(\tilde{w}_i), v_j\rangle = B_{j,i}
が成り立つ。
本稿で現れる非退化双線形形式はすべて対称であり、さらに正規直交基底を持つ。
形式的冪級数環および多項式環の双線形形式
$f=\sum_{n=0}^{N-1}f_n x^n, h=\sum_{n=0}^{N-1}h_n x^n\in\mathbb{F}[[x]]/(x^N)$ について、
\langle h, f\rangle := [x^0]\, h(1/x) f = \sum_{n=0}^{N-1} h_n f_n
と定義する。これは非退化対称双線形形式である。
線形空間を $\mathbb{F}[[x]]/(x^N)$ としたが、これは高々 $N-1$ 次の多項式の貼る線形空間 $\mathcal{P}_{n-1}(\mathbb{F})$ でも構わない。これらは考える線形写像がどちらの文脈で自然かで使い分ける。
アルゴリズムを考えるときには入力をどのような形で受け取り、どのような形で解を出力するかが問題になる。これは行列表現における基底の選択に対応する。多くの場合では冪級数の単項式の係数を入出力に取るだろう。それは行列表現においては単項式基底を選択することに対応する。これは正規直交基底である。転置原理は入力の双直交基底と出力の双直交基底をそれぞれ固定したときに、転置された問題を解く計算量とほぼ同じ計算量でもとの問題が解けるということを保証している。基底の選び方によって、行列表現は変わるし、入出力の形式が変わることで計算量も変わるだろうが、転置された線形写像そのものは変わらない。随伴は双線形形式の選び方のみによって定まる。アルゴリズム設計がしやすいように双線形形式を定める、ということも可能かもしれない。
様々な線形写像とその随伴(転置)
乗算
$g\in\mathcal{P}_{m-1}(\mathbb{F})$ について、線形写像 $\mathrm{Mult}\colon \mathcal{P}_{n-m}\to\mathcal{P}_{n-1}$ を
\mathrm{Mult}(f; g) := fg
と定義する。このとき
\begin{align*}
\langle h, \mathrm{Mult}(f;g)\rangle &= [x^0]\, h(1/x) fg\\
&= \langle g(1/x)h\text{ の0次から$n-m$次} , f\rangle
\end{align*}
より
\begin{align*}
\mathrm{Mult}^*(h;g) &= g(1/x) h \text{ の0次から$n-m$次}\\
&= x^{m-1} g(1/x) h \text{ の$m-1$次から$n-1$次}
\end{align*}
である。これは Middle product と呼ばれる写像である。
多点評価
$\mathrm{Eval}\colon\mathcal{P}_{N-1}(\mathbb{F}) \to \mathcal{P}_{k-1}(\mathbb{F})$ を
\mathrm{Eval}(f; (a_0,\dotsc, a_{k-1})) := \sum_{n=0}^{k-1} f(a_n) x^n
と定義する。
\begin{align*}
\langle h, \mathrm{Eval}(f;(a_1,\dotsc,a_k))\rangle &= \left\langle h,\sum_{n=0}^{k-1} f(a_n)x^n\right\rangle\\
&= \left\langle h,\sum_{n=0}^{k-1} \sum_{m\ge 0} f_m a_n^mx^n\right\rangle\\
&= \sum_{m\ge 0} \left(\sum_{n=0}^{k-1} a_n^m \left\langle h,x^n\right\rangle\right)f_m\\
&= \sum_{m\ge 0} \left(\sum_{n=0}^{k-1} a_n^m h_n\right)f_m\\
&= \left\langle \sum_{m\ge 0} \sum_{n=0}^{k-1} a_n^m h_n x^m, f\right\rangle\\
&= \left\langle \sum_{n=0}^{k-1} \frac{h_n}{1-a_nx}, f\right\rangle
\end{align*}
よって
\mathrm{Eval}^*(h; (a_0,\dotsc,a_{k-1})) = \sum_{n=0}^{k-1}\frac{h_n}{1-a_nx} \mod x^N
である。
もともと多項式だったのに随伴の行き先は形式的冪級数になっている。形式的冪級数の便利な式変形を使ったのでしょうがない。
多項式補間
まだ書いてない。
有理冪級数の N 項目
\mathrm{LR}(f; Q, N) := [t^{N}]\, \frac{f(t)}{Q(t)}
と定義する。
\begin{align*}
\langle h, \mathrm{LR}(f; Q,N)\rangle &= h\cdot\left([t^{N}]\,\frac{f(t)}{Q(t)}\right)\\
&= h\cdot\left([t^{N}]\,\frac{\sum_{m=0}^{d-1} f_m t^m}{Q(t)}\right)\\
&= h\sum_{m=0}^{d-1} f_m \left([t^{N-m}]\,\frac{1}{Q(t)}\right)\\
%&= [x^0]\, \left(h\sum_{m=0}^{d-1}\left([t^{N-m}]\,\frac{1}{Q(t)}\right) x^{-m}\right)f
\end{align*}
よって
\mathrm{LR}^*(h; Q,N) = h \sum_{m=0}^{d-1}\left([t^{N-m}]\,\frac1{Q(t)}\right)x^{m}
である。
それぞれの問題についてアルゴリズムは以下でも解説されている。
合成
$g\in x\mathbb{F}[[x]]$ について $\mathrm{Comp}\colon \mathbb{F}[[x]]/(x^N)\to\mathbb{F}[[x]]/(x^N)$ を
\mathrm{Comp}(f; g) := f(g) \mod x^N
と定義する。
\begin{align*}
\langle h, \mathrm{Comp}(f;g)\rangle &= \left\langle h, \sum_{n\ge 0} f_n g^n\right\rangle\\
&= \sum_{n\ge 0} \left\langle h, g^n\right\rangle f_n\\
&= \left\langle\sum_{n\ge 0} \left\langle h, g^n\right\rangle x^n, f\right\rangle\\
%&= \left\langle\left\langle h, \frac1{1-gx}\right\rangle, f\right\rangle\\
%&= [x^0]\,h(1/x)\sum_{n\ge 0} f_n g^n\\
%&= [x^0]\, \left([t^0] \sum_{n\ge 0} g(t)^n h(1/t) x^{-n}\right)f\\
%&= [x^0]\, \left([t^0] \frac{h(1/t)}{1-g(t)/x}\right) f
\end{align*}
よって
\begin{align*}
\mathrm{Comp}^*(h;g) &= \sum_{n=0}^{N-1} \left\langle h, g^n\right\rangle x^n\\
&= \sum_{n=0}^{N-1} [t^0]\, h(1/t) g(t)^n x^n\\
&=[t^0]\,\frac{h(1/t)}{1-g(t)x}\mod x^N\\
&= [t^{N-1}]\,\frac{t^{N-1}h(1/t)}{1-g(t)x}\mod x^N
\end{align*}
である。この問題についてはシンプルな $O(\mathsf{M}(N)\log N)$ 時間アルゴリズムがある。
このアルゴリズムを一言で説明すると、Bostan--Mori のアルゴリズム(線形漸化的数列のN項目の計算)を実行しながら、分母分子の $t$ の $N$次より上の項を捨てるだけである。1ステップで $N$ が半分になるので、分母分子の $t$ の次数は半分になり、$x$ の次数は倍になるので、次数の積は保存される。
以上の事から転置原理より冪級数の合成も同じ計算量のアルゴリズムが存在する。
そのアルゴリズムを直接導出してみよう。もう一度転置して元に戻すと、
\begin{align*}
\langle \mathrm{Comp}^*(h;g), f\rangle &= [x^0]\, \left([t^0] \frac{h(1/t)}{1-g(t)/x}\right) f\\
&= [x^0]\, h(1/x)\left([t^0]\, \frac{f(t)}{1-g(x)/t}\right)
\end{align*}
よって
\begin{align*}
\mathrm{Comp}(f;g) &= [t^0]\,\frac{f(t)}{1-g(x)/t}\\
&= [t^0]\,\frac{f(t^{-1})}{1-g(x)t}\\
&= [t^{N-1}]\,\frac{t^{N-1}f(t^{-1})}{1-tg(x)}
\end{align*}
である。
\begin{align*}
Q_0(x,t) &:= 1-tg(x)\\
Q_{k+1}(x^2,t) &:= Q_k(x,t) Q_k(-x,t)\\
P(t) &:= t^{N-1}f(t^{-1})
\end{align*}
と定義する。$\mathrm{deg}_t(Q_k) =2^k$ である。すると(とてつもなくいい加減な書き方だが)
[t^{(N-2^k,\,N]}]\, \frac{P(t)}{Q_k(x,t)} \mod x^N = [t^{(N-2^k,\,N]}] \, Q_k(-x,t)\left.\left([t^{(N-2^{k+1},\,N]}]\, \frac{P(t)}{Q_{k+1}(z,t)} \mod z^{\lceil N/2\rceil}\right)\right|_{z=x^2} \mod x^N
という再帰アルゴリズムを考えることができる。このアルゴリズムの計算量は $T(N,k) = T(N/2, k+1) + O(\mathsf{M}(N2^{k+1})) = O(\mathsf{M}(N2^{k+1})\log N)$ より、$T(N,0) = O(\mathsf{M}(N)\log N)$ となる。
基底変換
$(b_n)_{n\ge 0}$ を $\mathbb{F}[[x]$ の線形空間としての基底とする。
ここで $\mathrm{Basis}\colon \mathcal{P}_{N-1}(\mathbb{F}) \to \mathbb{F}[[x]]/(x^N)$ を
\begin{align*}
\mathrm{Basis}(f; (b_n)) &:= \sum_{n\ge 0} \langle x^n, f\rangle\, b_n \mod x^N\\
&= \sum_{n\ge 0} f_n b_n \mod x^N
\end{align*}
と定義する。 これは $x^n\mapsto b_n$ で定義される線型写像である。
\begin{align*}
\langle h, \mathrm{Basis}(f;(b_n))\rangle &= \left\langle h, \sum_{n\ge 0} f_n b_n\right\rangle\\
%&= \sum_{n\ge 0} \langle x^n, f\rangle \left\langle h, b_n\right\rangle\\
&= \sum_{n\ge 0} f_n \left\langle h, b_n\right\rangle\\
%[x^0]\, h(1/x) \sum_{n\ge 0}f_nb_n\\
%&=[x^0]\, \left(\sum_{n\ge 0}\left([t^0]\, b_n(t) h(1/t)\right) x^{-n}\right)f\\
%&=[x^0]\, \left([t^0]\, h(1/t) \sum_{n\ge 0}b_n(t) x^{-n}\right) f
\end{align*}
よって
\begin{align*}
\mathrm{Basis}^*(h;(b_n)) %&= [t^0]\, h(1/t) \sum_{n= 0}^{N-1} b_n(t) x^{n}\\
&= \sum_{n= 0}^{N-1}\langle h,\, b_n\rangle x^{n}\\
&= \left\langle h(t),\, \sum_{n= 0}^{N-1} b_n(t) x^{n}\right\rangle\\
\end{align*}
である。 $(b_n)_n$ が正規直交基底であると仮定すると、これは $b_n\mapsto x^n$ で定義される線型写像であり、$\mathrm{Basis}$ の逆写像である。これらの線形変換は直交変換であり逆写像は転置ということになる。
特別な場合として $\sum_{n\ge 0} b_n(t)x^n$ が二変数有理冪級数のとき、合成のところで用いたアルゴリズムを使うことで高速なアルゴリズムが得られる可能性がある。例えば Chebyshev 多項式についてはこれが二変数有理冪級数となる。しかし分母の次数が低いので、この場合は既に $O(\mathsf{M}(N))$ 時間アルゴリズムが知られている。
Mahler
\mathrm{Mahler}(f;k,c) := f(x^k) x^c
とすると、
\begin{align*}
\langle h,\mathrm{Mahler}(f;k,c)\rangle &= [x^0]\, h(1/x) f(x^k)x^c\\
&= \sum_{n\ge 0} f_n h_{nk+c}\\
%&= [x^0]\, \left(\sum_{n\ge 0} h_{nk+c} x^{-n}\right) f
\end{align*}
よって
\mathrm{Mahler}^*(h;k,c) = \sum_{n\ge 0}h_{nk+c} x^n =\mathrm{Sect}_{c,k}(h)
切り捨て
\mathrm{Tranc}(f;k) := f\mod x^k
とすると、
\begin{align*}
\langle h, \mathrm{Tranc}(f;k)\rangle &= \sum_{n=0}^{k-1} h_n f_n\\
&= \langle \mathrm{Tranc}(h;k), f\rangle
\end{align*}
よって
\mathrm{Tranc}^*(h;k) = \mathrm{Tranc}(h;k)
微分
\mathrm{Deriv}(f) := f' = \sum_{n\ge 0} (n+1)f_{n+1} x^n
とすると
\begin{align*}
\langle h, \mathrm{Deriv}(f)\rangle&= \sum_{n\ge 0} h_n (n+1) f_{n+1}\\
%&= [x^0] \left(\sum_{n\ge 0}(n+1)h_n x^{-(n+1)}\right)f
\end{align*}
よって
\begin{align*}
\mathrm{Deriv}^*(h) &= \sum_{n\ge 0}(n+1) h_n x^{n+1}\\
&= x^2h' + xh
\end{align*}
積分
\mathrm{Integ}(f) := \sum_{n\ge 0} \frac1{n+1} f_n x^{n+1}
とすると、
\begin{align*}
\langle h, \mathrm{Integ}(f)\rangle &= \sum_{n\ge 0} h_{n+1}\frac1{n+1} f_{n}\\
%&= [x^0]\, \left(\sum_{n\ge 0}\frac1{n+1} h_{n+1} x^{-n}\right) f
\end{align*}
よって
\mathrm{Integ}^*(f) = \sum_{n\ge 0}\frac1{n+1} h_{n+1} x^n
多項式への一般的な代入
多項式に何か一般的な集合 $\mathbb{A}$ を代入することを考える。このとき、$\mathbb{A}$ に要請されるのは環であること、$\mathbb{F}$ のスカラー倍が定義されていることである(体 $\mathbb{F}$上の結合多元環)。そして $\mathbb{A}$ に非退化双線形形式が定義されているとする。そのような例としては多変数の多項式や正方行列などがあるだろう。
任意の $a\in \mathbb{A}$ と $f\in\mathcal{P}_{N-1}(\mathbb{F})$ について
\mathrm{Subst}(f; a) := f(a) = \sum_{n\ge 0} f_n a^n
と定義する。すると、
\begin{align*}
\langle h, \mathrm{Subst}(f; a)\rangle &= \sum_{n\ge 0} f_n \langle h, a^n\rangle
\end{align*}
よって、
\mathrm{Subst}^*(h; a) = \sum_{n\ge 0} \langle h, a^n\rangle x^n
である。ここで $\mathbb{A}$上の形式的冪級数に読み替えて $\sum_{n\ge 0} a^nx^n = (1-ax)^{-1}$ を使うと、
\mathrm{Subst}^*(h; a) = \langle h, (1-ax)^{-1}\rangle \mod x^N
が得られる。これは上記の多項式の合成の一般化である。
また、$\mathbb{A}$ が正方行列の集合でフロベニウス内積 $\langle b, a\rangle = \mathrm{Tr}(b^Ta)$ を用いたとき
\mathrm{Subst}^*(h; a) = \mathrm{Tr}(h^T (I-ax)^{-1}) \mod x^N
が得られる。
多項式除算の剰余
高々$N-1$次多項式$r$と$M$次多項式$\Gamma$について
\mathrm{Rem}(f; \Gamma) := f\mod\Gamma
とする。
転置原理なしで Monomial 基底から Newton 基底への変換 にある多項式除算に関する表現を用いると
\begin{align*}
\langle h, f\bmod\Gamma\rangle &= \left\langle h, [x^{\ge0}]\,\Gamma[x^{<0}]\,\frac{f}{\Gamma}\right\rangle\\
&= \left\langle h, \Gamma[x^{<0}]\,\frac{f}{\Gamma}\right\rangle\\
&= \left\langle \bar{\Gamma}h, [x^{<0}]\,\frac{f}{\Gamma}\right\rangle\\
&= \left\langle [x^{<0}]\, \bar{\Gamma}h, \frac{f}{\Gamma}\right\rangle\\
&= \left\langle \frac1{\bar{\Gamma}}[x^{<0}]\, \bar{\Gamma}h, f\right\rangle
\end{align*}
ここで $\bar{\Gamma}(x):=\Gamma(1/x)$である。双線形形式の右側は $\mathbb{F}((x^{-1}))$の元として扱い、左側は $\mathbb{F}((x))$の元として扱う。
よって、
\begin{align*}
\mathrm{Rem}^*(h;\Gamma) &= \frac1{\Gamma(1/x)}[x^{<0}]\, \Gamma(1/x) h(x) \mod x^N\\
&= \frac1{x^M\Gamma(1/x)}[x^{<M}]\, x^M\Gamma(1/x) h(x)\mod x^N
\end{align*}
が得られる。これは $M$個の初項が $h$、特性方程式が $\Gamma$で与えられる線形漸化的数列の$N$項目までである。
- A. Bostan, G. Lecerf, and É. Schost. 2003. Tellegen's principle into practice. In Proceedings of the 2003 international symposium on Symbolic and algebraic computation (ISSAC '03). Association for Computing Machinery, New York, NY, USA, 37–44. https://doi.org/10.1145/860854.860870
多項式除算の商
\mathrm{Quo}(f;\Gamma) := \text{$f$ を$\Gamma$で割った商}
とする。剰余のときと同様に
\begin{align*}
\langle h, \mathrm{Quo}(f;\Gamma)\rangle &= \left\langle h, [x^{\ge 0}]\, \frac{f}{\Gamma}\right\rangle\\
&= \left\langle h, \frac{f}{\Gamma}\right\rangle\\
&= \left\langle \frac1{\bar{\Gamma}} h, f\right\rangle
\end{align*}
より
\begin{align*}
\mathrm{Quo}^*(h;\Gamma) &= \frac1{\Gamma(1/x)}h(x) \mod x^N\\
&=\frac{x^M h(x)}{x^M \Gamma(1/x)} \mod x^N
\end{align*}
が得られる。 $\mathrm{Quo}$が入力の下位の $M$項を無視するので、$\mathrm{Quo}^*$の出力の下位の$M$項は0で固定される。