The block triangular form and its use for sparse LU-factorization

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.