|
 ABSTRACT
Sparse Gaussian elimination with partial pivoting computes the factorization PAQ = LU of a sparse matrix A, where the row ordering P is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column preordering, Q, based solely on the nonzero pattern of A, that limits the worst-case number of nonzeros in the factorization. The fill-in also depends on P, but Q is selected to reduce an upper bound on the fill-in for any subsequent choice of P. The choice of Q can have a dramatic impact on the number of nonzeros in L and U. One scheme for determining a good column ordering for A is to compute a symmetric ordering that reduces fill-in in the Cholesky factorization of ATA. A conventional minimum degree ordering algorithm would require the sparsity structure of ATA to be computed, which can be expensive both in terms of space and time since ATA may be much denser than A. An alternative is to compute Q directly from the sparsity structure of A; this strategy is used by MATLAB's COLMMD preordering algorithm. A new ordering algorithm, COLAMD, is presented. It is based on the same strategy but uses a better ordering heuristic. COLAMD is faster and computes better orderings, with fewer nonzeros in the factors of the matrix.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
|
| |
4
|
Bai, Z., Day, D., Demmel, J., and Dongarra, J. 1996. Test matrix collection (non-Hermitian eigenvalue problems), Release 1. Tech. rep., University of Kentucky. September. Available at ftp://ftp.ms.uky.edu/pub/misc/bai/Collection.
|
| |
5
|
Berger, A. J., Mulvey, J. M., Rothberg, E., and Vanderbei, R. J. 1995. Solving multistage stochastic programs using tree dissection. Tech. Rep. SOR-95-07, Dept. of Civil Eng. and Operations Research, Princeton Univ., Princeton, NJ. June.
|
| |
6
|
|
| |
7
|
|
| |
8
|
Davis, T. A. 2000. Univ. of Florida sparse matrix collection. http://www.cise.ufl.edu/research/ sparse.
|
| |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
Duff, I. S., Grimes, R. G., and Lewis, J. G. 1992. Users' guide for the Harwell-Boeing sparse matrix collection (Release 1). Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Didcot, Oxon, England. Dec.
|
| |
18
|
|
| |
19
|
Feldmann, P., Melville, R., and Long, D. 1996. Efficient frequency domain analysis of large nonlinear analog circuits. In Proceedings of the IEEE Custom Integrated Circuits Conference (Santa Clara, Calif.). IEEE Computer Society Press, Los Alamitos Calif.
|
| |
20
|
George, A. and Liu, J. W. H. 1980. An optimal algorithm for symbolic factorization of symmetric matrices. SIAM J. Comput. 9, 583--593.
|
| |
21
|
|
| |
22
|
George, A. and McIntyre, D. R. 1978. On the application of the minimum degree algorithm to finite element systems. SIAM J. Numer. Anal. 15, 90--111.
|
| |
23
|
George, A. and Ng, E. 1985. An implementation of Gaussian elimination with partial pivoting for sparse systems. SIAM J. Sci. Statist. Comput. 6, 2, 390--409.
|
| |
24
|
|
| |
25
|
|
| |
26
|
Gilbert, J. R. and Ng, E. G. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, Eds. Volume 56 of the IMA Volumes in Mathematics and Its Applications. Springer-Verlag, New York, 107--139.
|
| |
27
|
|
| |
28
|
Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.
|
| |
29
|
|
| |
30
|
|
| |
31
|
Heggernes, P. and Matstoms, P. 1994. Finding good column orderings for sparse QR factorization. Tech. rep., Dept. of Informatics, Univ. of Bergen, Bergen, Norway.
|
| |
32
|
|
| |
33
|
Kern, J. L. 1999. Approximate deficiency for ordering the columns of a matrix. Tech. rep., Univ. of Florida, Gainesville, Fla. (Senior thesis, see http://www.cise.ufl.edu/colamd/kern.ps.)
|
| |
34
|
Larimore, S. I. 1998. An approximate minimum degree column ordering algorithm. Tech. Rep. TR-98-016, Univ. of Florida, Gainesville, Fla. (Master's thesis, see http://www.cise.ufl.edu/tech-reports/.)
|
| |
35
|
|
| |
36
|
|
| |
37
|
Markowitz, H. M. 1957. The elimination form of the inverse and its application to linear programming. Manage. Sci. 3, 255--269.
|
| |
38
|
Miller, J. J. H. and Wang, S. 1991. An exponentially fitted finite element method for a stationary convection-diffusion problem. In Computational Methods for Boundary and Interior Layers in Several Dimensions, J. J. H. Miller, Ed. Boole Press, Dublin, 120--137.
|
| |
39
|
|
| |
40
|
Resende, M. G. C., Ramakrishnan, K. G., and Drezner, Z. 1995. Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming. Oper, Res. 43, 781--791.
|
| |
41
|
|
| |
42
|
Sherman, A. H. 1975. On the efficient solution of sparse systems of linear and nonlinear equations. Tech. Rep. 46, Yale Univ. Dept. of Computer Science. Dec.
|
| |
43
|
Wright, S. J. 1996. Primal-dual interior-point methods. SIAM Publications, Philadelphia, Pa.
|
| |
44
|
Yannakakis, M. 1981. Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 2, 77--79.
|
| |
45
|
|
| |
46
|
Zitney, S. E., Mallya, J., Davis, T. A., and Stadtherr, M. A. 1996. Multifrontal vs. frontal techniques for chemical process simulation on supercomputers. Comput. Chem. Eng. 20, 6/7, 641--646.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.1