Solution of Linear Systems with Sparse Matrices
F. Grund · Birkhäuser Basel eBooks · 2003
For large scale problems in electric circuit simulation as well as in chemical process simulation, the linear solver often needs about 50-80% of the total amount of computing time. For that purpose, we consider direct methods for the numerical solution of linear systems of equations with unsymmetric sparse coefficient matrices. The Gaussian elimination method PAQ = LU Ly = Pb,UQ -1 x = y is applied to solve the linear system Ax = b. Here, the row permutation matrix P is used to provide numerical stability and the column permutation matrix Q is chosen to control sparsity. In a new approach, implemented in the solver GSPAR2, the determination of the pivot columns is done with a modified algorithm, which has only a complexity of O(n). A partial pivoting technique is used to maintain numerical stability. For solving several linear systems with the same pattern structure of the coefficient matrix efficiently, we generate a list of pseudo-code instructions for the factorization of the matrices. With it, the solver GSPAR2 has been proven successful within the simulation of several real life problems. For a number of linear systems arising from different technical problems, the computing times of GSPAR2 are compared to that of some recently released linear solvers.