Rychlé násobení matic

• Thesis title in Czech: Rychlé násobení matic
• Thesis title in English: Fast matrix 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. Mgr. Libor Barto, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 07.11.2007
• Date of assignment: 19.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. Pavel Růžička, Ph.D.

Guidelines

Práce se bude zabývat asymptoticky rychlými algoritmy pro násobení matic. Bude obsahovat přehled dosažených výsledků a zaměří se na popis některých z nich. Práce je vhodná pro OM a MMIB.

References

[1] Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
[2] Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv:math. GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
[3] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251–280, 1990.
[4] Sandeep Murthy. The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication. arXiv:cs. CS/0703145. 3 April 2007.