noshi91のメモ

データ構造のある風景

多項式の基底変換　メモ

Bostan, A., & Schost, É. (2005). Polynomial evaluation and interpolation on special sets of points. Journal of Complexity, 21(4), 420-446. の内容と、FFT で計算したときの計算量のメモ

2023/12/13: 計算量の定数倍を一部訂正(改善)しました

Question	General	Arithmetic	Geometric
Newton → Monomial	自然な分割統治	General と同じ	q-二項定理で展開すると q-exp
Monomial → Newton	noshi91のメモ	General と同じ	q-exp の逆元
Monomial evaluation	hly1204's blog	General と同じ。Newton 基底経由でも可	ア辞典
Monomial interpolation	ei1333の日記	微分の多点評価を $\mathrm{O}(n)$ で計算できる。Newton 基底経由でも可	ア辞典, Newton 基底経由でも可
Newton evaluation	Monomial 基底を経由	式変形すると exp	式変形すると q-exp
Newton interpolation	Monomial 基底を経由	exp の逆元	q-exp の逆元

支配的でない項は書かない。
長さ $n ~ (2$ 冪 $)$ の DFT が $n \log _ 2 (n) = n \operatorname{lb} (n)$ で計算できるとする。
$\mathrm{O}(n \operatorname{lb}(n) )$ になっている部分は、 $n$ が $2$ 冪だとして定数倍を評価している
subproduct tree の計算は $n \operatorname{lb}(n) ^ 2$

Question	General	Arithmetic	Geometric
Newton → Monomial	$2 ~ n \operatorname{lb}(n) ^ 2$	$2 ~ n \operatorname{lb}(n) ^ 2$	$6 ~ n \operatorname{lb}(n)$
Monomial → Newton	$2 ~ n \operatorname{lb}(n) ^ 2$	$2 ~ n \operatorname{lb}(n) ^ 2$	$6 ~ n \operatorname{lb}(n)$
Monomial evaluation	$2 ~ n \operatorname{lb}(n) ^ 2$	$2 ~ n \operatorname{lb}(n) ^ 2$	$6 ~ n \operatorname{lb}(n)$
Monomial interpolation	$3 ~ n \operatorname{lb}(n) ^ 2$	$2 ~ n \operatorname{lb}(n) ^ 2$	$12 ~ n \operatorname{lb}(n)$
Newton evaluation	$3 ~ n \operatorname{lb}(n) ^ 2$	$6 ~ n \operatorname{lb}(n)$	$6 ~ n \operatorname{lb}(n)$
Newton interpolation	$4 ~ n \operatorname{lb}(n) ^ 2$	$6 ~ n \operatorname{lb}(n)$	$6 ~ n \operatorname{lb}(n)$