szybkie mnożenie wielomianów

[Fibik]

Mnożenie wielomianów wymaga: \(\displaystyle{ n \cdot m}\) mnożeń współczynników, czyli \(\displaystyle{ n^2}\) dla \(\displaystyle{ n = m}\).

Przykładowo - \(\displaystyle{ n = 2}\):
\(\displaystyle{ (a_1x + a_0)(b_1x+b_0)=a_1b_1x^2 + (a_1b_0 + a_0b_1)x + a_0b_0=c_2x^2+c_1x+c_0}\)
\(\displaystyle{ 2 \cdot 2 =}\) cztery mnożenia.
ale można to zredukować do \(\displaystyle{ 2n-1}\) mnożeń, co w tym przypadku daje \(\displaystyle{ 3}\), zamiast \(\displaystyle{ 4}\).

Zysk niewielki, ale dla większych \(\displaystyle{ n}\) będzie już istotny:

\(\displaystyle{ n = 3}\), wymagałoby \(\displaystyle{ 9}\) mnożeń, a to minimum wynosi: \(\displaystyle{ 2 \cdot 3-1 = 5}\).
\(\displaystyle{ n = 4 \to 16}\), i \(\displaystyle{ 7}\) = minimum - ponad 50% mniej
\(\displaystyle{ n = 8 \to 64}\), i \(\displaystyle{ 15}\) - już ponad 4 razy mniej!
itd.

Jak takie coś praktycznie realizować?

Weźmy przypadek \(\displaystyle{ n = 2}\), wówczas należy to obliczać np. tak:

\(\displaystyle{ z_2 = a_1\cdot b_1\\z_1 = (a_1 - a_0)\cdot (b_1 - b_0) ,\, [=a_1b_1-a_1b_0-a_0b_1+a_0b_0]\\z_0 = a_0\cdot b_0}\)

Jak widać są tu tylko trzy mnożenia, a nie \(\displaystyle{ 4}\).
Teraz musimy jedynie wyznaczyć za pomocą tych \(\displaystyle{ 3}\) mnożeń, czyli: \(\displaystyle{ z_i,\ 3}\) współczynniki wielomianu 2-go stopnia - \(\displaystyle{ c_i}\);

Pierwszy i ostatni jest już dany jawnie: \(\displaystyle{ z_2}\) i \(\displaystyle{ z_0}\);

Natomiast ten środkowy musimy wyznaczamy za pomocą kombinacji tych trzech z-etów, co jest łatwe w tym przypadku:
\(\displaystyle{ c_1 =z_2 + z_0 - z_1 = a_1b_0 + a_0b_1}\)

zatem tym sposobem możemy wymnażać sobie wielomiany 1-go stopnia przy użyciu 3 mnożeń zaledwie, zamiast 4.

Podobnie można wykombinować mnożenie wielomianów 2-go stopnia w \(\displaystyle{ 2\cdot 3-1=5}\)-ciu mnożeniach zamiast w \(\displaystyle{ 3\cdot 3=9}\)-ciu.
Niestety, ale schemat będzie już bardziej skomplikowany.
Dla 3-go stopnia będzie jeszcze gorzej, a wyżej to już w ogóle masakra.


Dlatego mnie interesuje nieco inna sprawa:
mnożenie wielomianów 3-go stopnia wymaga: \(\displaystyle{ 4\cdot 4 = 16}\) mnożeń prostych, a minimum wynosi tu 7.

\(\displaystyle{ (a_3x^3+a_2x^2+a_1x+a_0)\cdot(b_3x^3+b_2x^2+b_1x+b_0)=\\(a_3b_3)x^6+\\(a_3b_2+a_2b_3)x^5+\\(a_3b_1+a_1b_3+a_2b_2)x^4+\\(a_3b_0+a_0b_3+a_2b_1+a_1b_2)x^3+\\(a_2b_0+a_0b_2+a_1b_1)x^2+\\(a_1b_0+a_0b_1)x+\\(a_0b_0)}\)

Jak to zrobić za pomocą \(\displaystyle{ 8}\) mnożeń (o jeden więcej od minimum)?-- 11 sierpnia 2018, 18:19 --Brak pomysłów?
To jest chyba zwyczajna kombinacja liniowa wektorów, czyli transformacja: baza -> baza, co zwykle reprezentuje macierz transformacji wsp.