Tato bakalářská práce se zabývá problematikou práce s hustými maticemi pomocí konceptu tzv. hierarchických matic. Takové husté matice často vznikají např. jako inverze matic řídkých. Na příkladu třídiagonálních matic a s využitím jejich spektrálních vlastností ukážeme, že jejich hustá inverze má veškeré mimodiagonální bloky hodnosti nejvýše jedna. Toto pozorování lze v jistém smyslu zobecnit na řadu dalších řídkých matic, které můžeme nalézt v mnoha úlohách z reálného světa, fyzikálních, inženýrských, atd.
V práci zavedeme koncept hierarchických matic, jejichž základním kamenem je stromová struktura (typicky např. binární strom, jak jej známe z teorie grafů), která popisuje rekurzivní členění matice na bloky. Dále se v práci soustředíme na základní operace s takovými maticemi. Ukážeme, v jakém smyslu je lze zejména sčítat a násobit. Hlavní nástroj, který při popisu operací používáme, je tzv. low-rank aritmetika matic. Ta využívá maticových rozkladů (zejména QR rozklad a singulární rozklad (SVD)) k chytré manipulaci s bloky nízké hodnosti a ke kompresi výsledku operací.
Anotace v angličtině
The bachelor thesis focuses on a work and manipulation with dense matrices using the concept of so-called hierarchical matrices. Such dense matrices often appear, e.g., as inversions of sparse matrices. On the example of tridiagonal matrices and by employing their spectral properties, we demonstrate that their dense inverses have off-diagonal blocks of a low rank (not more than one). This observation can be generalized to a lot of other cases of sparse matrices, which can be found in many real-world problems in physics, engineering, etc.
In the thesis we introduce the concept of hierarchical matrices, where the key idea is the tree structure (e.g., a binary tree, which we know from graph theory) that describes a recursive partitioning of the matrix into blocks. We also focus on basic operations with these matrices. We show in which way it is possible to do the matrix addition and multiplication. The main tool that we use for describing these operations is so-called low-rank arithmetic of matrices. It employs matrix decompositions (especially the QR decomposition and singular value decomposition (SVD)) for smart manipulation with low-rank blocks and for compression of the result of operations.
tridiagonal matices, eigenvalues, dense matrices, dense inverses of sparse matrices, hierarchical matrices, low-rank arithmetic of matrices, trees (graph theory)
Rozsah průvodní práce
49 s.
Jazyk
CZ
Anotace
Tato bakalářská práce se zabývá problematikou práce s hustými maticemi pomocí konceptu tzv. hierarchických matic. Takové husté matice často vznikají např. jako inverze matic řídkých. Na příkladu třídiagonálních matic a s využitím jejich spektrálních vlastností ukážeme, že jejich hustá inverze má veškeré mimodiagonální bloky hodnosti nejvýše jedna. Toto pozorování lze v jistém smyslu zobecnit na řadu dalších řídkých matic, které můžeme nalézt v mnoha úlohách z reálného světa, fyzikálních, inženýrských, atd.
V práci zavedeme koncept hierarchických matic, jejichž základním kamenem je stromová struktura (typicky např. binární strom, jak jej známe z teorie grafů), která popisuje rekurzivní členění matice na bloky. Dále se v práci soustředíme na základní operace s takovými maticemi. Ukážeme, v jakém smyslu je lze zejména sčítat a násobit. Hlavní nástroj, který při popisu operací používáme, je tzv. low-rank aritmetika matic. Ta využívá maticových rozkladů (zejména QR rozklad a singulární rozklad (SVD)) k chytré manipulaci s bloky nízké hodnosti a ke kompresi výsledku operací.
Anotace v angličtině
The bachelor thesis focuses on a work and manipulation with dense matrices using the concept of so-called hierarchical matrices. Such dense matrices often appear, e.g., as inversions of sparse matrices. On the example of tridiagonal matrices and by employing their spectral properties, we demonstrate that their dense inverses have off-diagonal blocks of a low rank (not more than one). This observation can be generalized to a lot of other cases of sparse matrices, which can be found in many real-world problems in physics, engineering, etc.
In the thesis we introduce the concept of hierarchical matrices, where the key idea is the tree structure (e.g., a binary tree, which we know from graph theory) that describes a recursive partitioning of the matrix into blocks. We also focus on basic operations with these matrices. We show in which way it is possible to do the matrix addition and multiplication. The main tool that we use for describing these operations is so-called low-rank arithmetic of matrices. It employs matrix decompositions (especially the QR decomposition and singular value decomposition (SVD)) for smart manipulation with low-rank blocks and for compression of the result of operations.
tridiagonal matices, eigenvalues, dense matrices, dense inverses of sparse matrices, hierarchical matrices, low-rank arithmetic of matrices, trees (graph theory)
Zásady pro vypracování
Řešení reálných, např. fyzikálních nebo inženýrských problémů často vede na úlohy řešení rozsáhlé soustavy lineárních rovnic s řídkou maticí. Principy práce s řídkými maticemi jsou dlouho studované a dobře známé. Je též dobře známé, že inverzí řídké matice dostaneme matici obecně hustou. Reálné úlohy se samozřejmě neřeší hledáním inverzní matice, nicméně její aproximace (v nějakém smyslu) bývá užitečná např. při konstrukci předpodmiňovače pro krylovovské iterační metody. Snaha pracovat s velkou a přitom hustou maticí vedla ke konceptu tzv. hierarchických matic.
Tato bakalářská práce si klade za cíl objasnit čtenáři základní motivaci
k hierarchickému přístupu k práci s hustými maticemi. Prezentovat jednoduché (malé) příklady použití hierarchického přístupu a prodiskutovat základní operace (např. sčítání a násobení matic) prováděné s hierarchickými maticemi.
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 do 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í
Řešení reálných, např. fyzikálních nebo inženýrských problémů často vede na úlohy řešení rozsáhlé soustavy lineárních rovnic s řídkou maticí. Principy práce s řídkými maticemi jsou dlouho studované a dobře známé. Je též dobře známé, že inverzí řídké matice dostaneme matici obecně hustou. Reálné úlohy se samozřejmě neřeší hledáním inverzní matice, nicméně její aproximace (v nějakém smyslu) bývá užitečná např. při konstrukci předpodmiňovače pro krylovovské iterační metody. Snaha pracovat s velkou a přitom hustou maticí vedla ke konceptu tzv. hierarchických matic.
Tato bakalářská práce si klade za cíl objasnit čtenáři základní motivaci
k hierarchickému přístupu k práci s hustými maticemi. Prezentovat jednoduché (malé) příklady použití hierarchického přístupu a prodiskutovat základní operace (např. sčítání a násobení matic) prováděné s hierarchickými maticemi.
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 do 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
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
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
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
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
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
S. Pauli:
A numerical solver for Lyapunov equations based on the matrix sign function iteration in HSS arithmetic,
Semester Thesis, SAM, ETH Zurich, 2010.