Při počítání praktických úloh např. z fyziky se často setkáváme s potřebou
řešit soustavy rovnic s velkými řídkými maticemi. Tyto se mohou řešit klasicky např. pomocí iteračních metod, kdy matice soustavy zůstává po celou dobu výpočtu nezměněná a využívá se pouze jejího součinu s vektorem. Druhou možností jsou metody založené na rozkladech matic, kde je ovšem potřeba pracovat chytře se zaplněním matice v průběhu úprav. Moderní přístup k těmto metodám mohou zprostředkovat tzv. hierarchické formáty uložení matice.
Tato diplomová práce si klade za cíl stručně zrekapitulovat základní manipulaci
s hierarchickými maticemi a ukázat jak lze řešit soustavu rovnic s takovou
maticí pomocí rozkladových metod. Zaměříme se zejména na Gaussovu eliminaci,
přesněji řečeno na její variantu pro symetrickou pozitivně definitní matici, tzv. Choleského rozklad.
Anotace v angličtině
While dealing with practical real-world problems in, e.g., physics, it is often required to solve a large system of linear equations with a sparse matrix. Such linear problems can be solved in a classical way: By using iterative methods. In such methods, the matrix stays unchanged during the whole calculation, and it is employed repetitively only in evaluation matrix-vector products. The other way is represented by a bunch of methods based on matrix decompositions. During such decompositions, however, the matrix is changing and we have to use clever methods to avoid its ll-in with nonzeros. Hierarchical format for storing matrices is one of the modern approaches to do that. The goals of this diploma thesis are to summarize basic arithmetics of hierarchical matrices, and to show how to solve a linear system with such matrix by using decompositions. We focus in particular on the Gauian elimination method, more specically, on its variant applicable to symmetric positive denite matrices, socalled Cholesky decomposition. Finally, we also show how to employ hierarchical approach to explicitely assemble an inverse to a large sparse matrix.
Klíčová slova
hierarchická matice, symetrická pozitivně denitní matice; LU rozklad; Gaussova
eliminace; Choleského rozklad; maticové rovnice
Při počítání praktických úloh např. z fyziky se často setkáváme s potřebou
řešit soustavy rovnic s velkými řídkými maticemi. Tyto se mohou řešit klasicky např. pomocí iteračních metod, kdy matice soustavy zůstává po celou dobu výpočtu nezměněná a využívá se pouze jejího součinu s vektorem. Druhou možností jsou metody založené na rozkladech matic, kde je ovšem potřeba pracovat chytře se zaplněním matice v průběhu úprav. Moderní přístup k těmto metodám mohou zprostředkovat tzv. hierarchické formáty uložení matice.
Tato diplomová práce si klade za cíl stručně zrekapitulovat základní manipulaci
s hierarchickými maticemi a ukázat jak lze řešit soustavu rovnic s takovou
maticí pomocí rozkladových metod. Zaměříme se zejména na Gaussovu eliminaci,
přesněji řečeno na její variantu pro symetrickou pozitivně definitní matici, tzv. Choleského rozklad.
Anotace v angličtině
While dealing with practical real-world problems in, e.g., physics, it is often required to solve a large system of linear equations with a sparse matrix. Such linear problems can be solved in a classical way: By using iterative methods. In such methods, the matrix stays unchanged during the whole calculation, and it is employed repetitively only in evaluation matrix-vector products. The other way is represented by a bunch of methods based on matrix decompositions. During such decompositions, however, the matrix is changing and we have to use clever methods to avoid its ll-in with nonzeros. Hierarchical format for storing matrices is one of the modern approaches to do that. The goals of this diploma thesis are to summarize basic arithmetics of hierarchical matrices, and to show how to solve a linear system with such matrix by using decompositions. We focus in particular on the Gauian elimination method, more specically, on its variant applicable to symmetric positive denite matrices, socalled Cholesky decomposition. Finally, we also show how to employ hierarchical approach to explicitely assemble an inverse to a large sparse matrix.
Klíčová slova
hierarchická matice, symetrická pozitivně denitní matice; LU rozklad; Gaussova
eliminace; Choleského rozklad; maticové rovnice
Abstrakt: Při počítání praktických úloh např. z fyziky se často setkáváme s potřebou řešit soustavy rovnic s velkými řídkými maticemi. Ty se mohou řešit klasicky např. pomocí iteračních metod, kdy matice soustavy zůstává po celou dobu výpočtu nezmněněná a využívá se pouze jejího součinu s vektorem. Druhou možností jsou metody založené na rozkladech matic, kde je ovšem potřeba pracovat chytře se zaplněním matice v průběhu úprav. Moderní přístup k těmto metodám mohou zprostředkovat tzv. hierarchické formáty uložení matice.
Tato diplomová práce si klade za cíl stručně zrekapitulovat základní manipulaci s hierarchickými maticemi a ukázat, jak lze řešit soustavu rovnic s takovou maticí pomocí rozkladových metod. Zaměříme se zejména na Gaussovu eliminaci, přesněji řečeno na její variantu pro symetrickou pozitivně definitní matici, tzv. Choleského rozklad.
Požadavky: Základní znalosti z lineární algebry, základní znalost anglického jazyka. Práce by měla být psána tak, aby mohla celá, nebo její části, sloužit jako materiál pro úvod studia dané problematiky. Práce by měla být psaná v LaTeXu, bude-li to v možnostech studenta.
Zásady pro vypracování
Abstrakt: Při počítání praktických úloh např. z fyziky se často setkáváme s potřebou řešit soustavy rovnic s velkými řídkými maticemi. Ty se mohou řešit klasicky např. pomocí iteračních metod, kdy matice soustavy zůstává po celou dobu výpočtu nezmněněná a využívá se pouze jejího součinu s vektorem. Druhou možností jsou metody založené na rozkladech matic, kde je ovšem potřeba pracovat chytře se zaplněním matice v průběhu úprav. Moderní přístup k těmto metodám mohou zprostředkovat tzv. hierarchické formáty uložení matice.
Tato diplomová práce si klade za cíl stručně zrekapitulovat základní manipulaci s hierarchickými maticemi a ukázat, jak lze řešit soustavu rovnic s takovou maticí pomocí rozkladových metod. Zaměříme se zejména na Gaussovu eliminaci, přesněji řečeno na její variantu pro symetrickou pozitivně definitní matici, tzv. Choleského rozklad.
Požadavky: Základní znalosti z lineární algebry, základní znalost anglického jazyka. Práce by měla být psána tak, aby mohla celá, nebo její části, sloužit jako materiál pro úvod studia dané problematiky. Práce by měla být psaná v LaTeXu, bude-li to v možnostech studenta.
Seznam doporučené literatury
M. Bebendorf:
Hierarchical Matrices,
Edice Lecture notes in computational science and engineering (LCNSE) 63,
Springer-Verlag, Berlin, Heidelberg, 2008.
http://www.springer.com/la/book/9783540771463
http://dx.doi.org/10.1007/978-3-540-77147-0
S. Börm:
Efficient Numerical Methods for Non-local Operators: H^2-Matrix Compression, Algorithms and Analysis,
Edice EMS Tracts in Mathematics 14,
European Mathematical Society, Zürich, 2010.
http://www.ems-ph.org/books/book.php?proj_nr=125
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, T. Pals:
A fast solver for HSS representations via sparse matrices,
SIAM Journal on Matrix Analysis and Applications,
Volume 29, Number 1 (2006), pp. 67-81. (15 pages)
http://epubs.siam.org/doi/abs/10.1137/050639028
http://dx.doi.org/10.1137/050639028
G. H. Golub, C. F. Van Loan:
Matrix Computations (Fourth Edition),
Johns Hopkins University Press, Baltimore, MD, 2012.
https://jhupbooks.press.jhu.edu/content/matrix-computations-0
W. Hackbusch:
Hierarchische Matrizen: Algorithmen und Analysis,
Springer-Verlag, Berlin, Heidelberg, 2009.
http://www.springer.com/la/book/9783642002212
http://dx.doi.org/10.1007/978-3-642-00222-9
S. Pauli:
A numerical solver for Lyapunov equations based on the matrix sign function iteration in HSS arithmetic,
Semester Thesis, SAM, ETH Zurich, 2010.
Seznam doporučené literatury
M. Bebendorf:
Hierarchical Matrices,
Edice Lecture notes in computational science and engineering (LCNSE) 63,
Springer-Verlag, Berlin, Heidelberg, 2008.
http://www.springer.com/la/book/9783540771463
http://dx.doi.org/10.1007/978-3-540-77147-0
S. Börm:
Efficient Numerical Methods for Non-local Operators: H^2-Matrix Compression, Algorithms and Analysis,
Edice EMS Tracts in Mathematics 14,
European Mathematical Society, Zürich, 2010.
http://www.ems-ph.org/books/book.php?proj_nr=125
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, T. Pals:
A fast solver for HSS representations via sparse matrices,
SIAM Journal on Matrix Analysis and Applications,
Volume 29, Number 1 (2006), pp. 67-81. (15 pages)
http://epubs.siam.org/doi/abs/10.1137/050639028
http://dx.doi.org/10.1137/050639028
G. H. Golub, C. F. Van Loan:
Matrix Computations (Fourth Edition),
Johns Hopkins University Press, Baltimore, MD, 2012.
https://jhupbooks.press.jhu.edu/content/matrix-computations-0
W. Hackbusch:
Hierarchische Matrizen: Algorithmen und Analysis,
Springer-Verlag, Berlin, Heidelberg, 2009.
http://www.springer.com/la/book/9783642002212
http://dx.doi.org/10.1007/978-3-642-00222-9
S. Pauli:
A numerical solver for Lyapunov equations based on the matrix sign function iteration in HSS arithmetic,
Semester Thesis, SAM, ETH Zurich, 2010.