A software package for sparse orthogonal factorization and updating

ABSTRACT

Although there is good software for sparse QR factorization, there is little support for updating and downdating, something that is absolutely essential in some linear programming algorithms, for example. This article describes an implementation of sparse LQ factorization, including block triangularization, approximate minimum degree ordering, symbolic factorization, multifrontal factorization, and updating and downdating. The factor Q is not retained. The updating algorithm expands the nonzero pattern of the factor L, which is reflected in dynamic representation of L. The block triangularization is used as an "ordering for sparsity" rather than as a prerequisite for block backward substitution. In symbolic factorization, something called "element counters" is introduced to reduce the overestimation of the number of nonzeros that the commonly used methods do. Both the approximate minimum degree ordering and the symbolic factorization are done without explicitly forming the nonzero pattern of the symmetric matrix in the corresponding normal equations. Tests show that the average time used for a single update or downdate is essentially the same as the time used for a single forward or backward substitution. Other parts of the implementation show the same range of performance as existing code, but cannot be replaced because of the special character of the systems that are solved.

REFERENCES

• 1: Adlers, M. 2000. PhD Dissertation. PhD Thesis, Department of Mathematics, Linköping University, S-581 83 Linköping, Sweden.
• 2: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 3: Björk, Å. 1987. Stability analysis of the method of semi-normal equations for least squares problems. Linear Algebra Appl. 88/89, 31--48.
• 4: Thomas F. Coleman , Anders Edenbrandt , John R. Gilbert, Predicting fill for sparse orthogonal factorization, Journal of the ACM (JACM), v.33 n.3, p.517-532, July 1986 [doi>10.1145/5925.5932]
• 5: Timothy A. Davis , William W. Hager, Modifying a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.606-627, July 1999 [doi>10.1137/S0895479897321076]
• 6: Timothy A. Davis , William W. Hager, Multiple-Rank Modifications of a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.997-1013, 2000 [doi>10.1137/S0895479899357346]
• 7: I. S. Duff, On Algorithms for Obtaining a Maximum Transversal, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.315-330, Sept. 1981 [doi>10.1145/355958.355963]
• 8: Iain S. Duff , Torbjörn Wiberg, Remarks on implementation of O(n^1/2τ) assignment algorithms, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.267-287, Sept. 1988 [doi>10.1145/44128.44131]
• 9: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 10: Edlund, O., Madsen, K., and Nielsen, H. B. 1999. A piecewise quadratic approach for solving sparse linear programming problems (to be submitted).
• 11: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 12: John R. Gilbert , Cleve Moler , Robert Schreiber, Sparse matrices in matlab: design and implementation, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.333-356, Jan. 1992 [doi>10.1137/0613024]
• 13: Gill, P. E. and Murray, W. 1973. A numerically stable form of the simplex method. Linear Algebra Appl. 7, 99--138.
• 14: Golub, G. H. and Van Loan, C. F. 1989. Matrix Computations, second ed. Johns Hopkins University Press, Baltimore.
• 15: Hopcroft, J. E. and Karp, R. M. 1973. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225--231.
• 16: Larimore, S. I. 1998. An approximate minimum degree column ordering algorithm. CISE Tech Rep. TR-98-016, Dept. of Computer and Information Science and Engineering, University of Florida, Gainesville, Fla. MS Thesis.
• 17: K. Madsen , H. Bruun Nielsen, Finite algorithms for robust linear regression, BIT, v.30 n.4, p.682-699, 1990 [doi>10.1007/BF01933216]
• 18: Madsen, K. and Nielsen, H. B. 1993. A finite smoothing algorithm for linear ℓ1 estimation. SIAM J. Optim. 3, 2, 223--235.
• 19: Kaj Madsen , Hans Bruun Nielsen , Mustafa Ç. Pinar, A New Finite Continuation Algorithm for Linear Programming, SIAM Journal on Optimization, v.6 n.3, p.600-616, 1996 [doi>10.1137/S1052623493258556]
• 20: Matstoms, P. 1994. Sparse QR factorization with applications to linear least squares problems. PhD Thesis, Department of Mathematics, Linköping University, S-581 83 Linköping, Sweden.
• 21: Pontus Matstoms, Sparse Linear Least Squares Problems in Optimization, Computational Optimization and Applications, v.7 n.1, p.89-110, Jan. 1997 [doi>10.1023/A:1008680131271]
• 22: Nielsen, H. B. 1990. AAFAC, a package of Fortran77 subprograms for solving ATAx = c. Tech. Rep. NI-90-01, Institute for Numerical Analysis, Technical University of Denmark, Lyngby 2800, Denmark.
• 23: M. Ç. Pinar, Piecewise-linear pathways to the optimal solution set in linear programming, Journal of Optimization Theory and Applications, v.93 n.3, p.619-634, June 1997 [doi>10.1023/A:1022651331550]
• 24: Alex Pothen , Chin-Ju Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.303-324, Dec. 1990 [doi>10.1145/98267.98287]
• 25: Michael A. Saunders, Large-scale linear programming using the Cholesky factorization., Stanford University, Stanford, CA, 1972

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms

Keywords:
Sparse matrix, downdating, orthogonal factorization, software, updating