Paralelní přímé metody pro řešení řídkých soustav lineárních rovnic

Místo
Anotace

Ř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í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 cuSolverSuperLU nebo MUMPS.

Přínos pro studenta:

  1. Získá hluboké porozumění algoritmům pro faktorizaci řídkých matic.
  2. Naučí se návrh paralelních algoritmů pro nerovnoměrně zatížené výpočty.
  3. Získá zkušenosti s efektivním programováním v jazuce C++ včetně jeho moderních vlastností.
  4. Práce má přímé využití v numerických simulacích, FEM/FVM, i HPC.

Zdroje:

  1. Timothy A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006.
  2. 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.
KOS