Řešení soustav lineárních rovnic je základním krokem v celé řadě numerických algoritmů – od simulací fyzikálních jevů přes optimalizaci až po strojové učení. V případech, kdy matice má řídkou strukturu, je efektivní řešení klíčové jak z hlediska výpočetní náročnosti, tak paměťových nároků.
Zatímco iterativní metody jsou často preferované pro velmi velké systémy, přímé metody (např. LU, Cholesky, QR rozklad) mají výhodu robustnosti, přesnosti a předvídatelnosti. Jejich paralelizace je však náročná kvůli nepravidelné závislosti mezi prvky a proměnné struktuře výplně během faktorizace.
Moderní přístupy – včetně eliminačních stromů, blokového rozdělení a task-based paralelizace – umožňují efektivní implementaci přímých metod i na víceprocesorových nebo GPU architekturách.
Cíle práce (konkrétní zadání se domluví individuálně se studentem):
Prostudovat základní přímé metody pro řídké systémy (např. LU, Cholesky, multifrontal).
- Seznámit se s technikami paralelizace (např. nested dissection, tree-based scheduling).
- Implementovat zjednodušenou paralelní variantu zvolené metody v knihovně TNL (např. LU rozklad s řídkou strukturou).
- Porovnat výkonnost se sériovou implementací a s knihovnami jako cuSolver, SuperLU nebo MUMPS.
Přínos pro studenta:
- Získá hluboké porozumění algoritmům pro faktorizaci řídkých matic.
- Naučí se návrh paralelních algoritmů pro nerovnoměrně zatížené výpočty.
- Získá zkušenosti s efektivním programováním v jazuce C++ včetně jeho moderních vlastností.
- Práce má přímé využití v numerických simulacích, FEM/FVM, i HPC.
Zdroje:
- Timothy A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006.
- Timothy A. Davis, Sivasankaran Rajamanickam, Wissam M. Sid-Lakhdar, A survey of direct methods for sparse linear systems, Acta Numerica, no.25, pp. 383-566, 2016, doi:10.1017/S0962492916000076.
