Author(s) :
Matthias Bollhöfer
,
Olaf Schenk
Preprint series :
Preprint CS 2004-006, Department of Computer Science, University of Basel
MSC 2000
- 65F05 Direct methods for linear systems and matrix inversion
-
65F50 Sparse matrices
-
05C50 Graphs and matrices
-
05C85 Graph algorithms
Abstract :
In this paper we will give an overview on combinatorial algorithms in sparse elimination methods. Beside well established techniques that have been developed in the last twenty years a modern viewpoint of LU decomposition is presented that illustrates how the evolution of techniques in the last decade improved the performance of sparse direct solvers.
Keywords :
sparse direct methods, LU decomposition, sparse matrices, reordering techniques, elimination tree, maximum weight matching, supernodes
Notes :
To appear in GAMM Mitteilungen, Themenheft "Applied and Numerical Linear Algebra", Part II.