Rychlé násobení polynomů

• Thesis title in Czech: Rychlé násobení polynomů
• Thesis title in English: Fast polynomial multiplication
• Academic year of topic announcement: 2007/2008
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Algebra (32-KA)
• Supervisor: doc. RNDr. David Stanovský, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 14.11.2007
• Date of assignment: 22.11.2007
• Date and time of defence: 09.09.2008 00:00
• Date of electronic submission: 09.09.2008
• Date of proceeded defence: 09.09.2008
• Opponents: doc. Mgr. Libor Barto, Ph.D.

Guidelines

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.

References

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