File:Polynommultiplikation.svg

Deutsch: Schnelle Multiplikation zweier Polynome ${\displaystyle p_{a}(x)=\sum \nolimits _{i=0}^{n}a_{i}x^{i}}$ und ${\displaystyle p_{b}(x)=\sum \nolimits _{i=0}^{n}b_{i}x^{i}}$ zu ${\displaystyle p_{c}(x):=p_{a}(x)\cdot p_{b}(x)=\sum \nolimits _{i=0}^{n}c_{i}x^{i}}$. Dabei werden zunächst die zu den beiden Polynomen ${\displaystyle p_{a}}$ und ${\displaystyle p_{b}}$ korrespondierenden Koeffizientenfolgen durch schnelle Fourier-Transformation in Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$ transformiert, sodass sich die zum Polynom ${\displaystyle p_{c}}$ korrespondierende fouriertransformierte Koeffizientenfolgen durch komponentenweise Multiplikation in Laufzeit ${\displaystyle {\mathcal {O}}(n)}$ ergibt. Diese wird schlussendlich durch schnelle inverse Fourier-Transformation in Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$ rücktransformiert. Die Gesamtlaufzeit liegt in ${\displaystyle {\mathcal {O}}(n\log n)}$ und ist damit asymptotisch effizienter im Vergleich zur klassischen Polynommultiplikation mit Laufzeit ${\displaystyle {\mathcal {O}}(n^{2})}$.