Original title:
Blokově trojúhelníkový tvar a jeho využití pro řídký LU-rozklad
Translated title:
The block triangular form and its use for sparse LU-factorization
Authors:
Gálfy, Ivan ; Duintjer Tebbens, Erik Jurjen (advisor) ; Tůma, Miroslav (referee) Document type: Bachelor's theses
Year:
2017
Language:
eng Abstract:
[eng][cze] In this thesis we will present an effective method for solving systems of linear equations with large sparse matrices using LU factorization. The goal is to avoid filling the matrix by non-zero entries during the computations. Firstly we dis- cuss the use of permutations for the matrix algorithms. Afterwards we present the maximum matching algorithm and Tarjan's algorithm, both based on graph theory. Tarjan's algorithm is used to achieve block triangular form and the max- imum matching gives us the permutation into a matrix with zero free diagonal, which is recommended as a precursor to Tarjan's algorithm. 1V této práci ukážeme efektivní metodu pro řešení systémů lineárních algebraických rovnic s velikými řídkými maticemi pomocí LU rozkladu. Cíl je se vyhnout zaplnění matice nenulovými hodnotami během výpočtu. Na začátku se zaobíráme použitím permutací v průběhu algoritmu. Pak presentujeme algoritmus maxi- mum matching a Tarjanův algoritmus, které jsou oba založeny na teorii grafů. Tarjanův algoritmus slouží na převedení matice do blokově trojúhelníkového tvaru a maximum matching dává permutaci matice na tvar, který nemá nuly na di- agonále. Maximum matching je doporučeno použít před aplikací Tarjanovho algoritmu. 1
Keywords:
block triangular form; fill-in; LU factorization; maximum matching; block triangular form; LU faktorizace; maximum matching; zaplnění
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/86220