research-article

Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems

Authors:

Timothy A. Davis,

Ekanathan Palamadai NatarajanAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 3

Article No.: 36, Pages 1 - 17

https://doi.org/10.1145/1824801.1824814

Published: 01 September 2010 Publication History

Abstract

KLU is a software package for solving sparse unsymmetric linear systems of equations that arise in circuit simulation applications. It relies on a permutation to Block Triangular Form (BTF), several methods for finding a fill-reducing ordering (variants of approximate minimum degree and nested dissection), and Gilbert/Peierls’ sparse left-looking LU factorization algorithm to factorize each block. The package is written in C and includes a MATLAB interface. Performance results comparing KLU with SuperLU, Sparse 1.3, and UMFPACK on circuit simulation matrices are presented. KLU is the default sparse direct solver in the Xyce^TMcircuit simulation package developed by Sandia National Laboratories.

Supplementary Material

Zip (907.zip)

Software for KLU, A Direct Sparse Solver for Circuit Simulation Problems

Download
999.20 KB

References

[1]

}}Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 4, 886--905.

Digital Library

[2]

}}Amestoy, P. R., Davis, T. A., and Duff, I. S. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 381--388.

Digital Library

[3]

}}Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3, 1--14.

Digital Library

[4]

}}Davis, T. A. 2002. Algorithm 832: UMFPACK V4.3, an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2, 196--199.

Digital Library

[5]

}}Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA.

Digital Library

[6]

}}Davis, T. A. and Duff, I. S. 1997. An unsymmetric-pattern multifrontal method for sparse LU factorization. SIAM J. Matrix Anal. Appl. 18, 1, 140--158.

Digital Library

[7]

}}Davis, T. A. and Duff, I. S. 1999. A combined unifrontal/multifrontal method for unsymmetric sparse matrices. ACM Trans. Math. Softw. 25, 1, 1--19.

Digital Library

[8]

}}Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004a. Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 377--380.

Digital Library

[9]

}}Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004b. A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 353--376.

Digital Library

[10]

}}Davis, T. A. and Hu, Y. To appear. University of Florida sparse matrix collection. ACM Trans. Math. Softw. To appear; (see also http://www.cise.ufl.edu/sparse/matrices).

Digital Library

[11]

}}Davis, T. A. and Palamadai Natarajan, E. To appear. Sparse matrix methods for circuit simulation problems. In Proceedings of the Conference on Scientific Computing in Electrical Engineering (SCEE’10).

[12]

}}Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., and Liu, J. W. H. 1999. A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Appl. 20, 3, 720--755.

Digital Library

[13]

}}Dongarra, J. J., Du Croz, J., Duff, I. S., and Hammarling, S. 1990. A set of level-3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16, 1, 1--17.

Digital Library

[14]

}}Duff, I. S. 1981a. Algorithm 575: Permutations for a zero-free diagonal. ACM Trans. Math. Softw. 7, 1, 387--390.

Digital Library

[15]

}}Duff, I. S. 1981b. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Softw. 7, 1, 315--330.

Digital Library

[16]

}}Duff, I. S. and Reid, J. K. 1978a. Algorithm 529: Permutations to block triangular form. ACM Trans. Math. Softw. 4, 2, 189--192.

Digital Library

[17]

}}Duff, I. S. and Reid, J. K. 1978b. An implementation of Tarjan’s algorithm for the block triangularization of a matrix. ACM Trans. Math. Softw. 4, 2, 137--147.

Digital Library

[18]

}}Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.

Digital Library

[19]

}}Hager, W. W. 1984. Condition estimates. SIAM J. Sci. Statist. Comput. 5, 2, 311--316.

Digital Library

[20]

}}Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms, 2nd Ed. SIAM, Philadelphia, PA.

Digital Library

[21]

}}Hutchinson, S. A., Keiter, E. R., Hoekstra, R. J., Waters, L. J., Russo, T., Rankin, E., Wix, S. D., and Bogdan, C. 2002. The Xyce^TMparallel electronic simulator -- An overview. In Proceedings of the Parallel Computing: Advances and Current Issues, G. R. Joubert, A. Murli, F. J. Peters, and M. Vanneschi Eds., Imperial College Press, London, 165--172.

[22]

}}Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392.

Digital Library

[23]

}}Kundert, K. S. 1986. Sparse matrix techniques and their applications to circuit simulation. In Circuit Analysis, Simulation, and Design, A. E. Ruehli Ed. North-Holland, New York.

[24]

}}Kundert, K. S. and Sangiovanni-Vincentelli, A. 1988. User’s guide: Sparse 1.3. Tech. rep., Department of Electrical Engineering and Computer Science. University of California, Berkeley.

[25]

}}Nichols, K., Kazmierski, T., Zwolinski, M., and Brown, A. 1994. Overview of SPICE-like circuit simulation algorithms. IEEE Proc. Circ. Devices Syst. 141, 4, 242--250.

[26]

}}Palamadai Natarajan, E. 2005. KLU - A high performance sparse linear system solver for circuit simulation problems. M.S. Thesis, CISE Department, University of Florida.

[27]

}}Sipics, M. 2007. Sparse matrix algorithm drives SPICE performance gains. SIAM News 40, 4, 1.

[28]

}}Tarjan, R. E. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 146--160.

Digital Library

Cited By

Joseph FGurrala G(2025)Adaptive Homotopy Based Coarse Solver for Parareal-in-Time Transient Stability SimulationsIEEE Transactions on Power Systems10.1109/TPWRS.2024.342455540:2(1401-1413)Online publication date: Mar-2025
https://doi.org/10.1109/TPWRS.2024.3424555
Wang XYang KGeng GJiang Q(2025)Convergence Enhancement for Neural Network Integrated Power System Time Domain SimulationIEEE Transactions on Power Systems10.1109/TPWRS.2024.342190240:2(1481-1491)Online publication date: Mar-2025
https://doi.org/10.1109/TPWRS.2024.3421902
Świrydowicz KKoukpaizan NAlam MRegev SSaunders MPeleš S(2025)Iterative methods in GPU-resident linear solvers for nonlinear constrained optimizationParallel Computing10.1016/j.parco.2024.103123123(103123)Online publication date: Mar-2025
https://doi.org/10.1016/j.parco.2024.103123
Show More Cited By

Index Terms

Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Mathematical software

Recommendations

Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AA^T, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, ...
Incomplete LU Preconditioner Based on Max-Plus Approximation of LU Factorization

We present a new method for the a priori approximation of the orders of magnitude of the entries in the LU factors of a complex or real matrix $A$. This approximation is used to determine the positions of the largest entries in the LU factors of $A$, and ...
O(log² n) time efficient parallel factorization of dense, sparse separable, and banded matrices
SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures
Known polylog parallel algorithms for the solution of linear systems and related problems require computation of the characteristic polynomial or related forms, which are known to be highly unstable in practice. However, matrix factorizations of various ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 3

September 2010

296 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1824801

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2010

Accepted: 01 May 2010

Revised: 01 April 2010

Received: 01 April 2009

Published in TOMS Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

221
Total Citations
View Citations
2,184
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)9

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Joseph FGurrala G(2025)Adaptive Homotopy Based Coarse Solver for Parareal-in-Time Transient Stability SimulationsIEEE Transactions on Power Systems10.1109/TPWRS.2024.342455540:2(1401-1413)Online publication date: Mar-2025
https://doi.org/10.1109/TPWRS.2024.3424555
Wang XYang KGeng GJiang Q(2025)Convergence Enhancement for Neural Network Integrated Power System Time Domain SimulationIEEE Transactions on Power Systems10.1109/TPWRS.2024.342190240:2(1481-1491)Online publication date: Mar-2025
https://doi.org/10.1109/TPWRS.2024.3421902
Świrydowicz KKoukpaizan NAlam MRegev SSaunders MPeleš S(2025)Iterative methods in GPU-resident linear solvers for nonlinear constrained optimizationParallel Computing10.1016/j.parco.2024.103123123(103123)Online publication date: Mar-2025
https://doi.org/10.1016/j.parco.2024.103123
Li YZhang CZhou XChen LChu F(2025)A scalable method with synchronous parallelization for computing selected eigenvalues of large-scale power system modelElectric Power Systems Research10.1016/j.epsr.2024.111085238(111085)Online publication date: Jan-2025
https://doi.org/10.1016/j.epsr.2024.111085
Yu QYang XXu ZWu X(2024)Seismic Electromagnetic Radiation Simulation Using Finite-Element Time-Domain MethodBulletin of the Seismological Society of America10.1785/0120240089Online publication date: 10-Oct-2024
https://doi.org/10.1785/0120240089
Zhou JYang WDong FLin SCai QLi K(2024)NUMA-aware parallel sparse LU factorization for SPICE-based circuit simulators on ARM multi-core processorsThe International Journal of High Performance Computing Applications10.1177/10943420241241491Online publication date: 23-Oct-2024
https://doi.org/10.1177/10943420241241491
Deakin MMontenegro D(2024)Demonstrating Almost Linear Time Complexity of Bus Admittance Matrix-Based Distribution Network Power Flow: An Empirical Approach2024 IEEE Power & Energy Society General Meeting (PESGM)10.1109/PESGM51994.2024.10761076(1-5)Online publication date: 21-Jul-2024
https://doi.org/10.1109/PESGM51994.2024.10761076
Chevalier SParker R(2024)Towards Perturbation-Induced Static Pivoting on GPU-Based Linear Solvers2024 IEEE Power & Energy Society General Meeting (PESGM)10.1109/PESGM51994.2024.10689118(1-5)Online publication date: 21-Jul-2024
https://doi.org/10.1109/PESGM51994.2024.10689118
Castelli ALara J(2024)Improved evaluation of large network matrices for linear power flow within optimization problems2024 IEEE Power & Energy Society General Meeting (PESGM)10.1109/PESGM51994.2024.10688992(1-5)Online publication date: 21-Jul-2024
https://doi.org/10.1109/PESGM51994.2024.10688992
Cui H(2024)Bus Admittance Matrix Revisited: Performance Challenges on Modern ComputersIEEE Open Access Journal of Power and Energy10.1109/OAJPE.2024.336611711(83-93)Online publication date: 2024
https://doi.org/10.1109/OAJPE.2024.3366117
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents