Metody verifikace maticového součinu

školitel: Ing. Ľubomíra Dvořáková, Ph.D.
e-mail: zobrazit e-mail
typ práce: bakalářská práce, diplomová práce
zaměření: MI_MM, MI_AMSM, II_SIMI
klíčová slova: maticové násobení, součin matic, verifikace, korekce
popis:

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ů.

literatura:
  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)
poznámka: Na tématu pracuje Jan Legerský.
naposledy změněno: 06.10.2014 11:54:08

za obsah této stránky zodpovídá: Ľubomíra Dvořáková | naposledy změněno: 12.9.2011
Trojanova 13, 120 00 Praha 2, tel. 224 358 540, pevná linka 224 923 098, fax 234 358 643
České vysoké učení technické v Praze | Fakulta jaderná a fyzikálně inženýrská | Katedra matematiky