A parallel linear system solver for circuit simulation problems. (English) Zbl 1051.65028
Summary: This paper presents a parallel mixed direct/iterative method for solving linear systems \(Ax = b\) arising from circuit simulation. The systems are solved by a block \(LU\) factorization with an iterative method for the Schur complement. The Schur complement is a small and rather dense matrix. Direct \(LU\) decomposition of the Schur complement takes too much time in order to achieve reasonable speedup results. Our iterative method for the Schur complement is often much faster than the direct \(LU\) approach. Moreover, the iterative method is better parallelizable. This results in a fast sequential and well parallelizable method.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 94C05 | Analytic circuit theory |
| 65Y05 | Parallel numerical computation |
| 65Y20 | Complexity and performance of numerical algorithms |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
preconditioner; parallel iterative method; mixed direct/iterative method; sparse LU factorization; circuit simulation; iterative solution methods; Schur complement; GMRESSoftware:
COLAMDReferences:
| [1] | McQuain, Computational Mathematics and Applications 27 pp 25– (1994) · Zbl 0803.65039 · doi:10.1016/0898-1221(94)90064-7 |
| [2] | Efficient computation of ILU preconditioners. In Super Computing 1999 Conference Proceedings, available at: http://www.sc99.org/proceedings/papers/hysom.pdf |
| [3] | Parallel threshold-based ILU factorization. In Super Computing 1997 Conference Proceedings, available at: http://www.supercomp.org/sc97/proceedings/TECH/KARYPIS/INDEX.HTM |
| [4] | CGS preconditioned with ILUT as a solver for circuit simulation. Nat. Lab Unclassified Report 828/98, Philips Electronics N.V., 1998. |
| [5] | Demmel, SIAM Journal on Matrix Analysis and Applications 20 pp 915– (1999) · Zbl 0939.65036 · doi:10.1137/S0895479897317685 |
| [6] | Silicon Graphics, Inc. Man-page for PSLDU. |
| [7] | Making sparse Gaussian elimination scalable by static pivoting. In Proceedings of Supercomputing 98 Conference, 7-13 November 1998, Orlando, FL. |
| [8] | Efficient sparse factorization with lazy space allocation. In SIAM 1999 Parallel Processing Conference on Scientific Computing, 1999. |
| [9] | Fundamentals of computer-aided Circuit Simulation. Kluwer Academic: Dordrecht, The Netherlands, 1988. |
| [10] | Liu, ACM Transactions on Mathematical Software 11 pp 141– (1985) · Zbl 0568.65015 · doi:10.1145/214392.214398 |
| [11] | Direct Methods for Sparse Matrices. Oxford University Press, Oxford, UK, 1986. · Zbl 0604.65011 |
| [12] | Sparse matrix techniques. In Circuit Analysis, Simulation and Design, (ed.), North-Holland, 1986. |
| [13] | Gilbert, SIAM Journal on Matrix Analysis and Applications 13 pp 333– (1992) · Zbl 0752.65037 · doi:10.1137/0613024 |
| [14] | Saad, SIAM Journal on Scientific and Statistical Computing 7 pp 856– (1986) · Zbl 0599.65018 · doi:10.1137/0907058 |
| [15] | Liu, SIAM Journal on Matrix Analysis and Applications 11 pp 134– (1990) · Zbl 0697.65013 · doi:10.1137/0611010 |
| [16] | Implementation of a parallel mixed direct/iterative linear system solver. PhD thesis, Mathematical Institute, Utrecht University, to appear. |
| [17] | Karypis, SIAM Journal on Scientific Computing 20 pp 359– (1999) · Zbl 0915.68129 · doi:10.1137/S1064827595287997 |
| [18] | Hendrickson, SIAM Journal on Scientific and Statistical Computing 16 pp 452– (1995) · Zbl 0816.68093 · doi:10.1137/0916028 |
| [19] | Duff, SIAM Journal on Matrix Analysis and Applications 20 pp 889– (1999) · Zbl 0947.65048 · doi:10.1137/S0895479897317661 |
| [20] | Matrix Market. Collection of test matrices. Available at: http://math.nist.gov/MatrixMarket/index.html. |
| [21] | An approximate minimum degree column ordering algorithm. MS thesis, CISE Technical Report TR-98-016, University of Florida, 1998. Available at ftp://ftp.cise.ufl.edu/cis/tech-reports/tr98/tr98-016.ps |
| [22] | Gilbert, SIAM Journal on Scientific Computing 9 pp 862– (1988) · Zbl 0656.65036 · doi:10.1137/0909058 |
| [23] | Eisenstat, SIAM Journal on Matrix Analysis and Applications 13 pp 202– (1992) · Zbl 0746.65023 · doi:10.1137/0613017 |
| [24] | Eisenstat, SIAM Journal on Matrix Analysis and Applications 14 pp 253– (1993) · Zbl 0765.65051 · doi:10.1137/0614020 |
| [25] | Demmel, SIAM Journal on Matrix Analysis and Applications 20 pp 720– (1999) · Zbl 0931.65022 · doi:10.1137/S0895479895291765 |
| [26] | Davis, SIAM Journal on Matrix Analysis and Applications 18 pp 140– (1997) · Zbl 0884.65021 · doi:10.1137/S0895479894246905 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
