Bostan–Mori のアルゴリズム

Bostan–Mori のアルゴリズム（発展）

多項式・形式的べき級数 線形漸化的数列 C-recursive Fiduccia のアルゴリズム Bostan–Mori のアルゴリズム 転置原理 FFT

1. 概要 本記事では，Bostan–Mori のアルゴリズムに関する発展的な話題を扱います． 前回の記事では，線形漸化的数列の第 $K$ 項を高速に求める方法として，Fiduccia のアルゴリズムと Bostan–Mori のアルゴリズムを解説しました．本記事ではこのうち Bostan…

線形漸化的数列の第 K 項

多項式・形式的べき級数 線形代数 線形漸化的数列 C-recursive Fiduccia のアルゴリズム Bostan–Mori のアルゴリズム

1. 概要 単位的可換環 $R$ 上の数列 $A = (A_0,A_1,A_2,\ldots)$ が，定数 $c_1, c_2, \ldots, c_d$ について $$ A _ i = c_1 A _ {i-1} + c _ 2A _ {i-2} + \cdots + c _ dA _ {i-d}\qquad(i\geq d) $$ を満たすとします．このような数列を線形漸化的数列と…