Algoritmy pro řešení soustav lineárních rovnic s řídkou maticí
| Název práce v češtině: | Algoritmy pro řešení soustav lineárních rovnic s řídkou maticí |
|---|---|
| Název v anglickém jazyce: | Algorithms for finding solutions of linear systems with sparse matrices |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | doc. Mgr. Pavel Příhoda, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.08.2018 |
| Datum zadání: | 30.08.2018 |
| Datum potvrzení stud. oddělením: | 20.12.2018 |
| Zásady pro vypracování |
| Práce by měla podat přehled základních metod využívaných v lineární fázi faktorizačních algoritmů, případně algoritmů pro výpočet diskrétního logaritmu metodou index calculus, a jejich modifikací. Zkoumat se budou zejména metody vycházející z Lanczosova a Wiedemannova algoritmu. Jedním z cílů práce by mělo být porovnání jednotlivých metod z hlediska efektivity při nasazení v konkrétních aplikacích. |
| Seznam odborné literatury |
| Don Coppersmith: Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm, Mathematics of Computation 62(1994), pp. 333-350.
Peter L. Montgomery: A Block Lanczos Algorithm for Finding Dependecies over GF(2), in Advances in Cryptology - EUROCRYPT'95, LNCS 921, pp. 106-120. Michael Peterson, Chris Monico: F_2 Lanczos revisited, Linear Algebra and its Applications 428 (2008), pp. 1135 - 1150. Jeremy Teitelbaum: Euclid's algorithm and the Lanczos method over finite fields, Mathematics of Computation 67 (1998), pp. 1665 - 1678. |