Metody verifikace maticového součinu

Maticové násobení hraje klíčovou roli v lineární algebře a v numerické matematice. Proto je mu v informatice věnovana velká pozornost z hlediska návrhu efektivních algoritmů. S naším prohlubujícím se poznáním a s vývojem výpočetní techniky trvá snaha o nalezení stále efektivnějších algoritmů násobení matic. Asymptotická složitost násobení matic postupně klesá, je rovna O(n^t) aritmetických operací, kde 2 < t < 3 a t se stále více blíží dvěma. Bohužel, odpovídající algoritmy jsou z technického hlediska stále náročnější a v praxi zatím nepoužitelné kvůli velké konstantě ukryté v notaci O.

Problémy maticového násobení se studují z různých úhlů pohledu:

• Lze uvažovat matice reálné, celočíselné, v modulární aritmetice, booleovské a jiné.
• Je možné zkoumat deterministické a nedeterministické algoritmy, pravděpodobnostní atd.
• Rozlišuje se mezi různými výpočetními modely: aritmetické obvody, real RAM, unit-cost RAM, log-cost RAM, p-RAM, BSS atd.
• Dále se může úloha zúžit na verifikaci maticového součinu či korekci maticového součinu.

Tato práce bude zaměřena právě na složitost verifikace maticového součinu.

Rešeršní část práce

1. Nastudování prací týkajících se historie verifikace maticového součinu -- postupná eliminace náhodných kroků ve Freivaldsově algoritmu.
2. Nastudování různých výpočetních modelů a výsledků pro složitost verifikace odpovídající takovým modelům.

Výzkumná část práce

1. Porovnání známých výsledků v závislosti na použitém modelu a na třídě matic, s níž se pracuje (reálné, celočíselné, v modulární aritmetice, booleovské atd.)
2. Identifikace nových problémů.

1. Aho, A., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms, Addison--Wesley (1974), 470 p.
2. Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation, Springer (1998), 452 p.
3. Korec, I., Wiedermann, J.: Deterministic Verification of Integer Matrix Multiplication in Quadratic Time, V. Geffert at al. (Eds.): SOFSEM 2014, LNCS 8327, Springer International Publishing Switzerland (2014), 375--382
4. Wiedermann, J.: Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds Algorithm, preprint (2014)