Polynommultiplikation

the*V*oid

Hallo,

ich bin auf der Suche nach einem Algorithmus zur Durchführung von Polynommultiplikation,
der besser als O(N^2) ist. Kann mir jemand etwas auf die Sprünge helfen? Optimal wär's,
wenn der Algorithmus keine Anforderungen an die verwendeten Datenstrukturen stellen würde.

Danke im Voraus!

.filmor

Wie sollte das schneller gehen?

$\bigg(\sum_{i=0}^{n}a\_i x^i\bigg)\cdot\bigg(\sum\_{i=0}^{n}b\_i x^i\bigg) = \sum\_{i=1}^n\sum_{j=1}^n a\_i b\_j x^{i+j}$

Ich seh da nicht, wo man was optimieren könnte. Die Summen musst du beide ausführen, der Speicher muss n^2 groß sein.

the*V*oid

Ich habe bei Wikipedia von einem Algorithmus gelesen, der Fouriertransformation, inverse Fouriertransformation und Polynommultiplikation in O(N log N) ausführt. Dieser Algorithmus nennt sich, so weit mir bekannt ist, "Schnelle Faltung", allerdings finde ich dazu keinerlei nähere Informationen. Möglicherweise ist er so nur bei Wikipedia benannt.

Jester

Polynommultiplikation geht in O(n log n). Die Idee dazu ist folgende:

h(x) := p(x)*q(x) direkt berechnen benötigt O(n^2) Zeit. Um ein Polynom vom Grad n-1 aber eindeutig festzulegen genügt es seinen Wert an n Stellen zu kennen. Sind a_1,...,a_n n verschiedene Stellen, dann gilt: h(a_i) = p(a_i)*q(a_i). In dieser Darstellung kann man demnach in Linearzeit multiplizieren. Wenn man also schnell zwischen der Darstellung Polynom vs. n Punkte auf dem Graphen des Polynoms wechseln kann, dann kann man auch schnell multiplizieren.

Natürlich benötigt das Auswerten eines einzelnen Wertes O(n) Zeit. Aber wenn man die n Stellen geschickt wählt, dann benötigt man nicht O(n^2) Zeit um n Stellen auszuwerten: nämlich die n-ten Einheitswurzeln. Im Endeffekt ergibt das nichts anderes als eine DFT des Vektors, der die Koeffizienten des Polynoms enthält. Mit der FFT lässt sich diese in O(n log n) Zeit berechnen.

In Kürze also:
Vektor der Koeffizienten mit FFT transformieren -- komponentenweises Produkt -- iFFT drauf anwenden. Ergebnis ist das Produkt der beiden Polynome.

Ich hoffe das hilft Dir weiter.

the*V*oid

Vielen Dank, ich muss noch etwas drüber nachdenken, aber das ist im Prinzip was ich gesucht habe, denk ich

Jester

Denk dran, dass du die Vektoren groß genug machst... der Ergebnisvektor braucht schließlich 2n Komponenten.

.filmor

Na toll, Jester, jetzt hab ichs gerade selbst durchschaut gehabt und dann kommst du

http://de.wikipedia.org/wiki/Polynom#Definition_2, letzte Zeile stehts.

Wie Faltung und Fouriertransformation sich zueinander verhalten, steht hier.

Vielleicht hilfts void ja auch noch ein wenig.

Eine Alternative ist Karatsubas Algorithmus. Der ist zwar nur in O(n^log_2(3)) (wobei log_2(3) < 1.6), aber viel einfacher zu implementieren als der Algorithmus von Schönhage-Strassen, der auf der Fourier-Transformation basiert. Wenn deine Polynome sehr gross sind, wird O(n^log_2(3)) allerdings auch zu gross sein.

Der Schönhage-Strassen-Algorithmus ist uebrigens in O(n log n log log n). Wenn ich das richtig in Erinnerung habe kommt der zusaetzliche log log n-Faktor daher, dass du zuerst noch einen passenden Ring finden musst mit n-ten Einheitswurzeln.