FPS合成・power projection
概要
FPSの合成は、内側の級数を固定すると外側の係数についての線形変換になる。その転置であるpower projectionを有理関数の係数抽出として高速に解き、計算手順を転置して合成へ戻す。
考え方
合成をそのまま展開すると、内側の級数の冪を何本も扱うことになる。ここでは「各冪を係数付きで足して合成を作る」と「出力の次数に付けた重みを冪ごとに集める」を同じ行列の二つの作用として捉える。後者を先に高速化できれば、転置によって前者の合成も高速化できる。
精度を 、つまり 次までとし、内側の級数 は を満たすものに固定する。外側の級数を とすると、
である。 が固定されているので、これは入力 の線形結合である。行を出力の次数 、列を冪の指数 として、
と置く。以下、配列は低次数から並べ、行列を掛けるときは列ベクトルとして読む。
同じ行列で合成と重みの集約を見る
、 とする。精度 で各列を作ると、
なので、対応する行列は
となる。例えば 、すなわち を入力すると、
を得る。これは の係数列である。例えば の係数は、行列の の行と の積 で求まる。
今度は、出力の各次数に付ける重みを とする。同じ行列の列ごとに重み付き和を取ると、
となる。これが 、すなわちpower projectionである。上の4列に を掛けると、
より を得る。合成では が入力、power projectionでは が入力であり、どちらでも は固定する。
転置の意味は、内積(同じ位置の積の総和)でも確認できる。
一般にも両辺は である。「出力へ掛けた重みを、各入力が寄与した倍率に沿って集め直す」のが転置だと読める。
転置と合成逆関数は目的が異なる。合成逆関数は 、 を満たす級数 で、 の一次係数が可逆なときに存在する。この例では となり、これを使えば合成済みの から を復元できる。一方、 は重みの集約であり、合成の入力を復元してはいない。転置自体には の一次係数の可逆性も要らない。
有理関数の係数抽出へ移す
重み付き和を多項式積の一つの係数へ移すには、重みの並びを反転する。 の冪の 係数と掛けたい を に置けば、積で次数が にそろう。
先ほどの なら、 の係数列は 、つまり である。同じ例で の係数を拾うと、
となり、 と一致する。この反転は、重み付き和を係数抽出に書き直すための並べ替えである。行列の行と列を入れ替える転置とは区別する。
次に、冪の指数 を記録する変数 を導入する。幾何級数としてまとめると、求める列は
となる。 なら の最小次数は 以上なので、 の係数は0である。これで多数の冪を別々に計算する要求を、一つの有理関数の係数抽出へ移せた。小行列はこの対応を確認するためのものであり、高速算法では行列や全ての冪を明示的に作らない。
Bostan–Moriの係数抽出を、係数環が の多項式である場合へ拡張する。初期値 、、 から、 の間、次を繰り返す。
-
を作り、、 を計算する。 は の偶数次数だけを持つ。
-
の偶奇を とし、分子からその偶奇の係数、分母から偶数次数の係数を取り出す。
-
として、更新した の 次数を 以下へ切り詰める。 次数も 以下へ切り詰めてよい。
で分母が について偶数になるため、欲しい係数の偶奇だけを残して 添字を半分にできる。各段で求める値 が保たれる。 になったら を返す。これが全ての を格納する列である。
転置して合成を得る
上の算法で は だけから決まる。入力 に依存する の処理は、固定した との積、係数の抽出・切詰め、最後の固定級数 による乗算という線形操作である。入力の反転 も含めた手順が を表すので、実行順を逆にし、各操作を転置すると 、すなわち合成が得られる。
まず固定列 との積を、小配列で見る。入力 の積の係数列は
である。出力に重み を掛けると、 に戻る重みは 、 に戻る重みは となる。転置後の出力を と書けば、積とその転置は次の式で対応する。配列の範囲外の値は0とする。
後者は相互相関であり、固定列を反転して畳み込めば計算できる。上の例では反転列 と の畳み込みが になり、その添字1,2を取ればよい。一般に の長さを とすると、反転列との積の添字 が転置後の第 成分になる。二変数の固定多項式との積も、両方向の添字について同じように転置する。
次に、偶奇抽出 を考える。奇数側を取る操作は
で、その転置は重みの配列を
へ移す操作になる。
抽出先の重みを、抽出元の位置 へ戻す「散布」である。偶数側なら に散布する。どちらも元の長さの配列を0で初期化する。捨てた係数を復元する逆演算ではなく、使った位置だけに重みを戻している。切詰めの転置も同じ理由で、切詰め前の長さへの0埋めとなる。
一般の基本更新 を転置すると、対応する重みの更新は になる。倍率 はそのままであり、逆元を取って割る操作にはならない。
合成を実装するときは、まず から各段の 、次数、抽出する偶奇と配列の形を保存する。合成の入力 を最後の 方向の乗算の転置へ渡し、切詰めの転置、散布、固定 との積の転置を、段の逆順に行う。最後に得た の各係数への重みを反転すると、合成の係数列 になる。これは入力の反転 の転置も反転だからである。 自身は固定係数なので、その分母更新へ入力の重みを流してはいけない。
成立条件と計算量
段 では 次数が 、 次数が 。保持する長方形配列の面積は で、積の一時配列も定数倍の面積になる。二変数積は、単項式 を一次元の添字 へ埋め込むなどして計算できる。ここでstride( 添字が1増えるときの間隔) は、積の 次数より大きく取る。これにより 添字の和が隣の の領域へ入り込むことを防ぐ。さらにNTT長を、埋め込み後の積が折り返さない長さまで確保する。
各段の積は長さ の畳み込みなので 時間。段数は 、最後の 方向の級数除算も なので、power projectionも転置した合成も全体で 時間となる。各段を保存する素直な合成実装の空間は である。 なら縮約を行わず、定数項だけを返す。
では、外側の一般の無限FPSの高次項も合成結果の低次へ寄与するため、有限精度の入力だけでは結果が定まらない。 が有限多項式なら別途Taylor shiftで定数項を処理する。高速積に使う法が必要なNTT長に対応すること、最終除算の分母の定数項が可逆であることも確認する。この還元と転置の対応はABC387 G公式解説を参照できる。上の小行列・小配列と合成逆関数の例は、本書で対応を確かめるために補った例である。
問題一覧
- ABC387 G「Prime Circuit」 公式問題
技能・出典
主題: FPS合成・power projection(多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: FPS基本演算と多項式の多点評価を行う(定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関
- ABC439 G「Sugoroku 6」 公式問題
技能・出典
主題: FPS合成・power projection(多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: FPS基本演算と多項式の多点評価を行う(定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 赤色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。