FPS合成・power projection

概要

FPSの合成は、内側の級数を固定すると外側の係数についての線形変換になる。その転置であるpower projectionを有理関数の係数抽出として高速に解き、計算手順を転置して合成へ戻す。

考え方

合成をそのまま展開すると、内側の級数の冪を何本も扱うことになる。ここでは「各冪を係数付きで足して合成を作る」と「出力の次数に付けた重みを冪ごとに集める」を同じ行列の二つの作用として捉える。後者を先に高速化できれば、転置によって前者の合成も高速化できる。

精度を  mod xN+1\bmod x^{N+1}、つまり 0,…,N0,\ldots,N 次までとし、内側の級数 gg は g(0)=0g(0)=0 を満たすものに固定する。外側の級数を f(x)=∑k=0Nfkxkf(x)=\sum_{k=0}^N f_kx^k とすると、

f(g(x))=∑k=0Nfkg(x)k(modxN+1)f(g(x))=\sum_{k=0}^N f_k g(x)^k\pmod{x^{N+1}}

である。gg が固定されているので、これは入力 fkf_k の線形結合である。行を出力の次数 jj、列を冪の指数 kk として、

Aj,k=[xj]g(x)k(0≤j,k≤N)A_{j,k}=[x^j]g(x)^k\qquad(0\leq j,k\leq N)

と置く。以下、配列は低次数から並べ、行列を掛けるときは列ベクトルとして読む。

同じ行列で合成と重みの集約を見る

N=3N=3、g=x+x2g=x+x^2 とする。精度  mod x4\bmod x^4 で各列を作ると、

g0=1,g1=x+x2,g2=x2+2x3,g3=x3\begin{aligned} g^0&=1, & g^1&=x+x^2,\\ g^2&=x^2+2x^3, & g^3&=x^3 \end{aligned}

なので、対応する行列は

A=(1000010001100021)A=\begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&1&1&0\\ 0&0&2&1 \end{pmatrix}

となる。例えば f=(1,2,3,4)f=(1,2,3,4)、すなわち f(x)=1+2x+3x2+4x3f(x)=1+2x+3x^2+4x^3 を入力すると、

Af=(1,2,5,10)Af=(1,2,5,10)

を得る。これは f(g)=1+2g+3g2+4g3f(g)=1+2g+3g^2+4g^3 の係数列である。例えば x3x^3 の係数は、行列の j=3j=3 の行と ff の積 2⋅3+1⋅4=102\cdot3+1\cdot4=10 で求まる。

今度は、出力の各次数に付ける重みを w=(5,6,7,8)w=(5,6,7,8) とする。同じ行列の列ごとに重み付き和を取ると、

qk=∑j=0Nwj[xj]g(x)kq_k=\sum_{j=0}^N w_j[x^j]g(x)^k

となる。これが q=ATwq=A^T w、すなわちpower projectionである。上の4列に ww を掛けると、

q0=5,q1=6+7=13,q2=7+2⋅8=23,q3=8\begin{aligned} q_0&=5,\\ q_1&=6+7=13,\\ q_2&=7+2\cdot8=23,\\ q_3&=8 \end{aligned}

より ATw=(5,13,23,8)A^T w=(5,13,23,8) を得る。合成では ff が入力、power projectionでは ww が入力であり、どちらでも gg は固定する。

転置の意味は、内積(同じ位置の積の総和)でも確認できる。

(Af)⋅w=5+12+35+80=132,f⋅(ATw)=5+26+69+32=132\begin{aligned} (Af)\cdot w&=5+12+35+80\\ &=132,\\ f\cdot(A^T w)&=5+26+69+32\\ &=132 \end{aligned}

一般にも両辺は ∑j,kwjAj,kfk\sum_{j,k}w_j A_{j,k}f_k である。「出力へ掛けた重みを、各入力が寄与した倍率に沿って集め直す」のが転置だと読める。

転置と合成逆関数は目的が異なる。合成逆関数は s(0)=0s(0)=0、g(s(x))=xg(s(x))=x を満たす級数 ss で、gg の一次係数が可逆なときに存在する。この例では s=x−x2+2x3(modx4)s=x-x^2+2x^3\pmod{x^4} となり、これを使えば合成済みの f(g)f(g) から ff を復元できる。一方、ATwA^T w は重みの集約であり、合成の入力を復元してはいない。転置自体には gg の一次係数の可逆性も要らない。

有理関数の係数抽出へ移す

重み付き和を多項式積の一つの係数へ移すには、重みの並びを反転する。gg の冪の xjx^j 係数と掛けたい wjw_j を xN−jx^{N-j} に置けば、積で次数が NN にそろう。

h(x)=∑j=0NwjxN−j,qk=[xN](h(x)g(x)k)\begin{aligned} h(x)&=\sum_{j=0}^N w_jx^{N-j},\\ q_k&=[x^N](h(x)g(x)^k) \end{aligned}

先ほどの w=(5,6,7,8)w=(5,6,7,8) なら、hh の係数列は (8,7,6,5)(8,7,6,5)、つまり h=8+7x+6x2+5x3h=8+7x+6x^2+5x^3 である。同じ例で x3x^3 の係数を拾うと、

[x3]h=5,[x3]hg=6⋅1+7⋅1=13,[x3]hg2=7⋅1+8⋅2=23,[x3]hg3=8⋅1=8\begin{aligned} [x^3]h&=5,\\ [x^3]hg&=6\cdot1+7\cdot1=13,\\ [x^3]hg^2&=7\cdot1+8\cdot2=23,\\ [x^3]hg^3&=8\cdot1=8 \end{aligned}

となり、ATwA^T w と一致する。この反転は、重み付き和を係数抽出に書き直すための並べ替えである。行列の行と列を入れ替える転置とは区別する。

次に、冪の指数 kk を記録する変数 yy を導入する。幾何級数としてまとめると、求める列は

∑k≥0qkyk=[xN]h(x)1−yg(x)\sum_{k\geq0}q_ky^k=[x^N]\frac{h(x)}{1-yg(x)}

となる。g(0)=0g(0)=0 なら gkg^k の最小次数は kk 以上なので、k>Nk>N の係数は0である。これで多数の冪を別々に計算する要求を、一つの有理関数の係数抽出へ移せた。小行列はこの対応を確認するためのものであり、高速算法では行列や全ての冪を明示的に作らない。

Bostan–Moriの係数抽出を、係数環が yy の多項式である場合へ拡張する。初期値 P(x,y)=h(x)P(x,y)=h(x)、Q(x,y)=1−yg(x)Q(x,y)=1-yg(x)、n=Nn=N から、n>0n>0 の間、次を繰り返す。

  1. R(x,y)=Q(−x,y)R(x,y)=Q(-x,y) を作り、U=PRU=PR、V=QRV=QR を計算する。VV は xx の偶数次数だけを持つ。

  2. nn の偶奇を ε=n mod 2\varepsilon=n\bmod2 とし、分子からその偶奇の係数、分母から偶数次数の係数を取り出す。

    Pnew(x,y)=∑i≥0([x2i+ε]U)xi,Qnew(x,y)=∑i≥0([x2i]V)xi\begin{aligned} P_{\mathrm{new}}(x,y)&=\sum_{i\geq0}([x^{2i+\varepsilon}]U)x^i,\\ Q_{\mathrm{new}}(x,y)&=\sum_{i\geq0}([x^{2i}]V)x^i \end{aligned}
  3. n←⌊n/2⌋n\leftarrow\lfloor n/2\rfloor として、更新した P,QP,Q の xx 次数を nn 以下へ切り詰める。yy 次数も NN 以下へ切り詰めてよい。

P/Q=PR/(QR)P/Q=PR/(QR) で分母が xx について偶数になるため、欲しい係数の偶奇だけを残して xx 添字を半分にできる。各段で求める値 [xn](P/Q)[x^n](P/Q) が保たれる。n=0n=0 になったら P(0,y)/Q(0,y) mod yN+1P(0,y)/Q(0,y)\bmod y^{N+1} を返す。これが全ての qkq_k を格納する列である。

転置して合成を得る

上の算法で Q,RQ,R は gg だけから決まる。入力 hh に依存する PP の処理は、固定した RR との積、係数の抽出・切詰め、最後の固定級数 Q(0,y)−1Q(0,y)^{-1} による乗算という線形操作である。入力の反転 w↦hw\mapsto h も含めた手順が ATA^T を表すので、実行順を逆にし、各操作を転置すると (AT)T=A(A^T)^T=A、すなわち合成が得られる。

まず固定列 r=(2,3)r=(2,3) との積を、小配列で見る。入力 v=(v0,v1)v=(v_0,v_1) の積の係数列は

u=(2v0, 3v0+2v1, 3v1)u=(2v_0,\ 3v_0+2v_1,\ 3v_1)

である。出力に重み z=(5,6,7)z=(5,6,7) を掛けると、v0v_0 に戻る重みは 2⋅5+3⋅6=282\cdot5+3\cdot6=28、v1v_1 に戻る重みは 2⋅6+3⋅7=332\cdot6+3\cdot7=33 となる。転置後の出力を bb と書けば、積とその転置は次の式で対応する。配列の範囲外の値は0とする。

uk=∑ivirk−i,bi=∑kzkrk−i\begin{aligned} u_k&=\sum_i v_i r_{k-i},\\ b_i&=\sum_k z_k r_{k-i} \end{aligned}

後者は相互相関であり、固定列を反転して畳み込めば計算できる。上の例では反転列 (3,2)(3,2) と zz の畳み込みが (15,28,33,14)(15,28,33,14) になり、その添字1,2を取ればよい。一般に rr の長さを LL とすると、反転列との積の添字 i+L−1i+L-1 が転置後の第 ii 成分になる。二変数の固定多項式との積も、両方向の添字について同じように転置する。

次に、偶奇抽出 ui=v2i+εu_i=v_{2i+\varepsilon} を考える。奇数側を取る操作は

(v0,v1,v2,v3)⟼(v1,v3)(v_0,v_1,v_2,v_3)\longmapsto(v_1,v_3)

で、その転置は重みの配列を

(z0,z1)⟼(0,z0,0,z1)(z_0,z_1)\longmapsto(0,z_0,0,z_1)

へ移す操作になる。

抽出先の重みを、抽出元の位置 2i+ε2i+\varepsilon へ戻す「散布」である。偶数側なら (z0,0,z1,0)(z_0,0,z_1,0) に散布する。どちらも元の長さの配列を0で初期化する。捨てた係数を復元する逆演算ではなく、使った位置だけに重みを戻している。切詰めの転置も同じ理由で、切詰め前の長さへの0埋めとなる。

一般の基本更新 u←u+αvu\leftarrow u+\alpha v を転置すると、対応する重みの更新は v←v+αuv\leftarrow v+\alpha u になる。倍率 α\alpha はそのままであり、逆元を取って割る操作にはならない。

合成を実装するときは、まず gg から各段の RR、次数、抽出する偶奇と配列の形を保存する。合成の入力 ff を最後の yy 方向の乗算の転置へ渡し、切詰めの転置、散布、固定 RR との積の転置を、段の逆順に行う。最後に得た hh の各係数への重みを反転すると、合成の係数列 AfAf になる。これは入力の反転 w↦hw\mapsto h の転置も反転だからである。gg 自身は固定係数なので、その分母更新へ入力の重みを流してはいけない。

成立条件と計算量

段 tt では xx 次数が O(N/2t)O(N/2^t)、yy 次数が O(2t)O(2^t)。保持する長方形配列の面積は O(N)O(N) で、積の一時配列も定数倍の面積になる。二変数積は、単項式 xiyjx^iy^j を一次元の添字 iS+jiS+j へ埋め込むなどして計算できる。ここでstride(xx 添字が1増えるときの間隔)SS は、積の yy 次数より大きく取る。これにより yy 添字の和が隣の xx の領域へ入り込むことを防ぐ。さらにNTT長を、埋め込み後の積が折り返さない長さまで確保する。

各段の積は長さ O(N)O(N) の畳み込みなので O(Nlog⁡N)O(N\log N) 時間。段数は O(log⁡N)O(\log N)、最後の yy 方向の級数除算も O(Nlog⁡N)O(N\log N) なので、power projectionも転置した合成も全体で O(Nlog⁡2N)O(N\log^2 N) 時間となる。各段を保存する素直な合成実装の空間は O(Nlog⁡N)O(N\log N) である。N=0N=0 なら縮約を行わず、定数項だけを返す。

g(0)≠0g(0)\ne0 では、外側の一般の無限FPSの高次項も合成結果の低次へ寄与するため、有限精度の入力だけでは結果が定まらない。ff が有限多項式なら別途Taylor shiftで定数項を処理する。高速積に使う法が必要なNTT長に対応すること、最終除算の分母の定数項が可逆であることも確認する。この還元と転置の対応はABC387 G公式解説を参照できる。上の小行列・小配列と合成逆関数の例は、本書で対応を確かめるために補った例である。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 赤色(2800以上)。FPS合成と転置の対応を理解し、block分割や有理関数への還元を扱う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-fps-composition-power-projection

FPS合成・power projection

習得する技能

  • 多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: FPS基本演算と多項式の多点評価を行う。

このUnitを直接前提とする単元: なし。

形式的べき級数の基本演算で得た考え方と実装を再利用し、FPS合成・power projectionの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • FPS合成・power projectionの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠