Název: Blokově trojúhelníkový tvar a jeho využití pro řídký LU-rozklad
Překlad názvu: The block triangular form and its use for sparse LU-factorization
Autoři: Gálfy, Ivan ; Duintjer Tebbens, Erik Jurjen (vedoucí práce) ; Tůma, Miroslav (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2017
Jazyk: eng
Abstrakt: [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. 1 V 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
Klíčová slova: block triangular form; LU faktorizace; maximum matching; zaplnění; block triangular form; fill-in; LU factorization; maximum matching

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/86220

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-357500


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce