math - 高速フーリエ変換多項式評価の「ツリー」?

Question

FFT を使用した分割統治アルゴリズムによって多項式 A(x) を評価しようとしています。基本的に、多項式を奇数根と偶数根に分割し、2 つの小さい多項式を再帰します (再帰ごとに 2 倍の数値を評価できるようにします)。

これを視覚化するために、アルゴリズムを通る多項式のパスを示すツリーを作成しようとしています。どのように始めたらよいかよくわかりません。どなたか始めていただけませんか？完全なツリーが正しい道に進むための簡単な例であるとは思っていません。

Answer 1

これはAlgorithmsの Chapter 2 からの簡単な例です:

A(x) = 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5
     = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4)
     = E(x^2) + x*O(x^2)

どこ

E(x) = 3 + 6x + x^2
O(x) = 4 + 2x + 10x^2

多項式のサイズが 2 分の 1 に縮小されていることに注意してください。また、同様の値になるため、でxの評価をリサイクルできます。-x

A(x) = E(x^2) + x*O(x^2)
A(-x) = E(x^2) - x*O(x^2)

この再帰的なプロセスがどのようにツリーになるかがわかると思います。