Predicting fill for sparse orthogonal factorization

ABSTRACT

In solving large sparse linear least squares problems A x ≃ b, several different numeric methods involve computing the same upper triangular factor R of A. It is of interest to be able to compute the nonzero structure of R, given only the structure of A. The solution to this problem comes from the theory of matchings in bipartite graphs. The structure of A is modeled with a bipartite graph, and it is shown how the rows and columns of A can be rearranged into a structure from which the structure of its upper triangular factor can be correctly computed. Also, a new method for solving sparse least squares problems, called block back-substitution, is presented. This method assures that no unnecessary space is allocated for fill, and that no unnecessary space is needed for intermediate fill.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BRAYTON, R. K., GUST AVSON, F. G., AND WILLOUGHBY, R.A. Some results on sparse matrices. Math. Comput. 24 (1970), 937-954.
• 3: BUNCH, J. R., AND ROSE, D. J., EDS. Sparse Matrix Computations. Academic Press, Orlando, Fla., 1976.
• 4: 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]
• 5: DULMAGE, A. L., AND MENDELSOHN, N.S. Coverings of bipartite graphs. Canad. J. Math. 10 (1958), 517-534.
• 6: DULMAGE, A. L., AND MENDELSOHN, N.S. A structure theory of bipartite graphs of finite exterior dimension. Trans. Roy. Soc. Can. 53, Ill (1959), 1-13.
• 7: DULMAGE, A. L., AND MENDELSOHN, N. S. Two algorithms for bipartite graphs. J. SIAM !I (1963), 183-194.
• 8: FEDERER, H. Geometric Measure Theory. Springer-Verlag, Berlin, 1969.
• 9: FORD, L. R., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.
• 10: GENTLEMAN, W.M. Row elimination for solving sparse linear systems and least squares problems. In Proceedings of the Dundee Conference on Numerical Analysis (1975), G. A. Watson, Ed., Lecture Notes in Mathematics, vol. 506. Springer-Verlag, New York, 1976, pp. 122-123.
• 11: GEORGE, A., AND HEATH, M.T. Solution of sparse linear least squares problems using Givens rotations. Linear Alg. Appl. 34 (1980), 69-83.
• 12: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 13: GEORGE, A., AND NG., E. An implementation of Gaussian elimination with partial pivoting for sparse systems. SIAM J. Sci. Stat. Comput. 6 (1985), 390-409.
• 14: GEORGE, A., LIU, J., AND NG, E. Row ordering schemes for sparse Givens transformations. I: Bipartite graph model. Linear Alg. Appl. 61 (1984), 55-81.
• 15: GOLUB, G. H., AND BUSINGER, P. Linear least squares solutions by Householder transformations. Numerische Mathematik, 7, Hand Book Series on Linear Algebra. (1965), 269-276.
• 16: GUST AVSON, F. Finding the block lower triangular form of a sparse matrix. In Sparse Matrix Computations, J. R. Bunch and D. J. Rose, Eds. Academic Press, Orlando, Fla., 1976, pp. 275- 289.
• 17: HALL, P. On representatives of subsets. J. Lond. Math. Soc. l0 (1935), 26-30.
• 18: HEATH, M.T. Some extensions of an algorithm for sparse linear least squares problems. SIAM J. Sci. Stat. Comput. 3 (1982), 223-237.
• 19: HEATH, M.T. Numerical methods for large sparse linear least squares problems. SIAM J. Sci. Star. Comput. 5 (1984), 497-513.
• 20: HOPCROFT, J. E., AND KARP, R. M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 (1973), 225-231.
• 21: HOWELL, T.D. Partitioning using PAQ. In Sparse Matrix Computations, J. R. Bunch and D. J. Rose, Eds. Academic Press, Orlando, Fla., 1976, pp. 23-37.
• 22: JOHNSON, D. M., DULMAGE, A. L., AND MENDELSOHN, N. S. Connectivity and reducibility of graphs. Canad. J. Math. 14 (1962), 529-539.
• 23: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 24: ROSE, D. J., TARJAN, R. E., AND LUEKER, G. S. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5 (1976), 266-283.
• 25: TARJAN, R. Depth-first search and linear graph algorithms. SIAM J. Comput. I (1972), 146-160.

INDEX TERMS

Primary 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)

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

General Terms:
Algorithms, Performance, Theory, Verification