Rychlé násobení polynomů

• Název práce v češtině: Rychlé násobení polynomů
• Název v anglickém jazyce: Fast polynomial multiplication
• Akademický rok vypsání: 2007/2008
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. RNDr. David Stanovský, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.11.2007
• Datum zadání: 22.11.2007
• Datum a čas obhajoby: 09.09.2008 00:00
• Datum odevzdání elektronické podoby: 09.09.2008
• Datum proběhlé obhajoby: 09.09.2008
• Oponenti: prof. Mgr. Libor Barto, Ph.D.

Zásady pro vypracování

Základním algoritmem pro rychlé násobení polynomů je převedení problému do modulární reprezentace pomocí rychlé Fourierovy tranformace. Problém je, že v řadě oborů, zejména tedy v racionálních číslech, není k dispozici příslušná primitivní odmocnina z jedné. Student na základě literatury popíše, jak se tato situace efektivně řeší, a především provede pečlivou statistickou analýzu reálné složitosti FFT a algoritmu násobení polynomů implementovaného v knihovně NTL na náhodných datech (v závislosti na stupni polynomu, počtu nenulových koeficientů i velikosti koeficientů). Výsledky budou zpracovány pomocí jednoduché regresní analýzy k získání odhadu střední složitosti. Součástí práce může být i porovnání reálné složitosti FFT s algoritmem Garnerovým a Lagrangeovým pro polynomy nad racionálními čísly.

Seznam odborné literatury

Joachim von zur Gathen, Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge 1999,

K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston 1992,

a další dle pokynů vedoucího práce