拡張された形式の方程式乗算のFFT

Question

FFTを使用して2つの方程式を$ o（n 、log 、n）$ timeで乗算する方法を知っていますが、単純化する前に拡張された方程式を計算するためにFFTを使用する方法はありますか？

たとえば、$ a（x）= 1 + 2x + 6x^2 $および$ b（x）= 4 + 5x + 3x^2 $を乗算している場合、$ c（x）= a（x）を取得するように cdot b（x）= 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4 $は、単純化された答えに直接行くことなく？

さらに、FFTを使用して、$ o（n 、log 、n）$ timeでこの拡張されたフォームの乗算を行うことは可能ですか？もしそうなら、このシナリオにFFTを適用する方法を教えていただけますか？

Answer 1

すべてのモノミアルにすべてのモノマリアルを$ b $のすべてのモノマリアルを乗算する些細なアルゴリズムには、時間$ o（| a | cdot | b |）$（$ | a | $は$ a $または表現に応じて$ deg a + 1 $）。これは、出力のサイズと同じ桁で、非常に最適です。製品$ ab $を実際に計算する場合にのみ、FFTが必要です。特に、あります ありえない $ o（n log n）$の時間で関数を計算するには、単に出力の長さが$ omega（n^2）$であるという理由だけです。