Bostan, A., & Schost, É. (2005). Polynomial evaluation and interpolation on special sets of points. Journal of Complexity, 21(4), 420-446. の内容と、FFT で計算したときの計算量のメモ 2023/12/13: 計算量の定数倍を一部訂正(改善)しました Questi…

概要 [1] において解説されている、Newton 基底から Monomial 基底への変換のアルゴリズムを、転置原理無しで説明する。 問題は以下の通り。 体 上の 次未満の多項式 と、 個の値 が与えられる。 を満たす を求めよ *1。 これを の時間計算量で解く *2。 と…