Sparse QR factorization in MATLAB

ABSTRACT

In the recently presented sparse matrix extension of MATLAB, there is no routine for sparse QR factorization. Sparse linear least-squares problems are instead solved by the augmented system method. The accuracy in computed solutions is strongly dependent on a scaling parameter &dgr;. Its optimal value is expensive to compute, and it must therefore be approximated by a simple heuristic. We describe a multifrontal method for sparse QR factorization and its implementation in MATLAB. It is well known that the multifrontal approach is suitable for vector machines. We show that it is also attractive in MATLAB. In both cases, scalar operations are expensive, and the reformulation of the sparse problem into dense subproblems is advantageous. Using the new routine, we implement two methods for the solution of sparse linear least-squares problems and compare these with the built-in MATLAB function. We show that the QR-based methods normally are much faster and more accurate than the MATLAB implementation of the augmented system method. A better choice of the parameter &dgr; or iterative refinement must be used to make the augmented system method as accurate as the methods based on QR factorization.

REFERENCES

• 1: AmOLI, M, DUFF, I. S., AND DE RIJK, P. 1989. On the augmented system approach to sparse least-squares problems. Numer. Math. 55, 6, 667-684.
• 2: BJORCK, A. 1978. Comments on the iterative refinement of least squares solutions. J. Am. Stat. Assoc. 73, 161 166.
• 3: B,JORCK, A. 1987. Stability analysis of the method of semi-normal equations for least squares problems. Linear Algebra Appl. 88 89, 31-48.
• 4: BJ?}RCK, A. 1991. Pivoting and stability in the augmented system method. Tech. Rep. L~TH- MAT-R-1991-30, Dept. of Mathematics, LinkSplng Univ, Sweden, June
• 5: 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]
• 6: DUFF, I. S., AND REID, J. K. 1982. MA27 A set of Fortran subroutines for solving sparse symmetric sets of linear equations. Tech. Rep. R.10533, AERE, Harwell, England.
• 7: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 8: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 9: 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]
• 10: 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]
• 11: GOLUB, G.H. 1965. Numerical methods for solving least squares problems. Numer. Math. 7, 206 216.
• 12: GOLUB, G. H., AND WILKINSON, J. $. 1966. Note on the iterative refinement of least squares solution. Numer. Math. 9, 139 148.
• 13: HACHTEL, G.D. 1974. Extended applications of the sparse tableau approach--finite elements and least squares. In Basic Questions in Design Theory, W. Spillers, Ed. North-Holland, Amsterdam.
• 14: LEWIS, J. G., PIERCE, D. J., AND WAH, D.K. 1989. Multifrontal Householder QR factorization. Tech. Rep. ECA-TR-127, Boeing Computer Services, Seattle, Wash. Nov.
• 15: Joseph W H Liu, On general row merging schemes for sparse given transformations, SIAM Journal on Scientific and Statistical Computing, v.7 n.4, p.1190-1211, Oct. 1986 [doi>10.1137/0907081]
• 16: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 17: MATSTOMS, P. 1991. The multifrontal solution of sparse linear least squares problems. Licentiat thesis, Dept. of Mathematics, LinkSping Univ., Sweden.
• 18: MATSTOMS, P. 1992. QR27--Specification sheet. Dept. of Mathematics, Univ. of LinkSping, LinkSping, Sweden, Mar.
• 19: 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]
• 20: Robert Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.256-276, Sept. 1982 [doi>10.1145/356004.356006]
• 21: THE MATH WORKS 1992. MATLAB User's Gude. South Natick, Mass. WED~r~, P.-A. 1973. Perburbation theory for pseudo-inverse. BIT 13, 2, 217-232.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE

      Nouns: MATLAB

General Terms:
Algorithms, Measurement, Performance

Keywords:
MATLAB, linear least-squares problem, mathematical software, multifrontal method, orthogonal decomposition, sparse matrix