計算機数学I (2019) 第15回：高速フーリエ変換 (FFT) を用いた1変数多項式の高速乗算法

今回は、この授業の最終回で、離散フーリエ変換 (Discrete Fourier Transform, DFT) と高速フーリエ変換 (Fast Fourier Transform, FFT) に基づく1変数多項式の高速乗算アルゴリズムを紹介しました。

以上で春学期の講義が一通り終わりました。今回は、整数や多項式を主な対象にした代数的なアルゴリズムの構成や計算量評価を中心に行いました。この授業が、構成的な数学を知る上での一助になることを望みます。