×

Fast algorithms for placing large entries along the diagonal of a sparse matrix. (English) Zbl 1206.65149

Summary: Solving a sparse system of linear equations \(Ax=b\) is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix \(A\) are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix \(A\) so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). I. S. Duff and J. Koster [SIAM J. Matrix Anal. Appl. 22, No. 4, 973–996 (2001; Zbl 0979.05087)] have formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper, we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from \(O(|V|+|E|)\) to \(O(|V|)\), where \(|V|\) is the order of the matrix \(A\) and \(|E|\) is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.

MSC:

65F50 Computational methods for sparse matrices

Citations:

Zbl 0979.05087

Software:

SuperLU-DIST
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Li, Xiaoye S.; Demmel, James W., Superlu dist: a scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software, 29, 110-140 (2003) · Zbl 1068.90591
[3] Duff, I. S.; Koster, J., On algorithms for permuting large entries to the diagonal of a sparse matrix, SIAM Journal on Matrix Analysis and Applications, 22, 4, 973-996 (2001) · Zbl 0979.05087
[4] Fredman, Michael L.; Tarjan, Robert E., Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34, 3, 596-615 (1987) · Zbl 1412.68048
[5] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97 (1955) · Zbl 0143.41905
[6] Munkres, James, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5, 1, 32-38 (1957) · Zbl 0083.15302
[7] Kuhn, H. W., Variants of the Hungarian method for assignment problems, Naval Research Logistics Quarterly, 3, 253-258 (1956) · Zbl 0143.42001
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.