WIAS Preprint No. 816, (2003)

Solution of linear systems with sparse matrices



Authors

  • Grund, Friedrich

2010 Mathematics Subject Classification

  • 65F05 65F50 65Y05

Keywords

  • Direct Linear Solver, Sparse-Matrix-Techniques, Parallel Computation, Circuit Simulation, Chemical Process Simulation

Abstract

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 is applied to solve the linear system. Here, the row permutation is used to provide numerical stability and the column permutation 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.

Appeared in

  • K. Antreich, R. Bulirsch, A. Gilg, and P. Rentrop, editors: Modeling, Simulation and Optimization of Integrated Circuits, volume 146 of International Series of Numerical Mathematics, pages 333-347. Birkhäuser Verlag Basel/Switzerland, 2003

Download Documents