Paralelní přímé metody pro řešení řídkých soustav lineárních rovnic
| advisor: | doc. Ing. Tomáš Oberhuber, Ph.D. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MI_MM, MI_AMSM, MINF |
| key words: | numerická matematika, paralelni algoritmy |
| description: | Ř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: 1. Prostudovat základní přímé metody pro řídké systémy (např. LU, Cholesky, multifrontal). 2. 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). 3. Porovnat výkonnost se sériovou implementací a s knihovnami jako cuSolver, SuperLU 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. |
| references: | 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. |
| last update: | 20.05.2025 09:32:15 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011