Paralelní metody pro výpočet spektra matic
| 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: | spektrum matric, numerická matematika, GPU, paralelní algoritmy |
| description: | Výpočet spektra matic – tedy jejich vlastních čísel a vlastních vektorů – je zásadní součástí mnoha algoritmů a vědeckých aplikací. Tato úloha má mnoho aplikací např. v: 1. Kvantové a jaderné fyzice (řešení operátorů, spektrální rozklady), 2. analýze stability dynamických systémů (např. lineární aproximace), 3. strojovém učení (např. PCA, kernelové metody, spektrální klasifikace), 4. strukturální mechanice (vlastní módy vibrací), 5. grafové analýze (např. Laplaceovo spektrum, Fiedlerův vektor). V oblasti semidefinitního programování (SDP) je klíčové ověřování, zda matice splňuje podmínku pozitivní semidefinitnosti, což znamená, že všechna její vlastní čísla musí být nezáporná. Pro velké řídké matice je výpočet spektra výpočetně velmi náročný a bez efektivní paralelizace prakticky neřešitelný. To platí zejména pro úlohy v oblasti SDP, kde se pozitivně semidefinitní podmínky uplatňují nad maticemi o rozměrech stovky až tisíce – často v rámci iterativního algoritmu. Cíle práce: 1. Prostudovat základní a pokročilé metody pro výpočet spektra: Jacobiho metoda, QR algoritmus, Lanczosova metoda, divide-and-conquer, Jacobi–Davidson apod. 2. Zaměřit se na metody vhodné pro kompletní spektrum středně velkých hermitovských/symetrických matic. 3. Implementovat paralelní variantu vybrané metody (např. na CPU pomocí OpenMP nebo na GPU pomocí CUDA/TNL). 4. Ověřit výkonnost na testovacích maticích ze SDP úloh (např. ze solverů nebo testovacích sad). 5. Porovnat s referenčními knihovnami (např. LAPACK, Eigen, cuSolver, SLEPc). Přínosy pro studenta: 1. Získá hluboké znalosti v oblasti lineární algebry a numerických metod. 2. Naučí se vytvářet efektivní kód v jazyce C++ včetně využití moderních vlastností tohoto jazyka, včetně programování s pomocí knihovny TNL s možností využití počítání na GPU. 3. Vyzkouší si práci se spektrálními daty v reálných aplikacích (SDP, ML, výpočetní fyzika). |
| references: | 1. Saad, Yousef. Numerical methods for large eigenvalue problems: revised edition. Society for Industrial and Applied Mathematics, 2011. 2. Golub, Gene H., and Charles F. Van Loan. Matrix computations. JHU press, 2013. 3. Gu, Ming, and Stanley C. Eisenstat. \"A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem.\" SIAM Journal on Matrix Analysis and Applications 16.1 (1995): 172-191. |
| last update: | 20.05.2025 09:07:57 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011