×

Solution of linear systems with sparse matrices. (English) Zbl 1043.65057

Antreich, K. (ed.) et al., Modeling, simulation, and optimization of integrated circuits. Proceedings of a conference, Oberwolfach, Germany, November 25–December 1, 2001. Basel: Birkhäuser (ISBN 3-7643-2192-X/hbk). ISNM, Int. Ser. Numer. Math. 146, 333-347 (2003).
Summary: 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,\quad 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 efficently, 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.
For the entire collection see [Zbl 1029.00036].

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
94C05 Analytic circuit theory
80A32 Chemically reacting flows
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation

Software:

BOP; SparseMatrix
PDFBibTeX XMLCite