Parallel out-of-core computation and updating of the QR factorization

ABSTRACT

This article discusses the high-performance parallel implementation of the computation and updating of QR factorizations of dense matrices, including problems large enough to require out-of-core computation, where the matrix is stored on disk. The algorithms presented here are scalable both in problem size and as the number of processors increases. Implementation using the Parallel Linear Algebra Package (PLAPACK) and the Parallel Out-of-Core Linear Algebra Package (POOCLAPACK) is discussed. The methods are shown to attain excellent performance, in some cases attaining roughly 80&percent; of the “realizable” peak of the architectures on which the experiments were performed.

REFERENCES

• 1: Philip Alpatov , Greg Baker , Carter Edwards , John Gunnels , Greg Morrow , James Overfelt , Robert van de Geijn , Yuan-Jye J. Wu, PLAPACK: parallel linear algebra package design overview, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-16, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509622]
• 2: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 3: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 4: Bjorck, A. 1996. Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.
• 5: Choi, J., Dongarra, J. J., Pozo, R., and Walker, D. W. 1992. ScaLAPACK: A scalable linear algebra library for distributed memory concurrent computers. In Proceedings of the Fourth Symposium on the Frontiers of Massively Parallel Computation. IEEE Computer Society Press, 120--127.
• 6: Coleman, R., Leback, B., Norin, R., Scott, D., and de Houten, K. V. 1992. Soz - a dense, out-of-core solver with partial pivoting for the iPSC/860: A case history. In 1992 Annual Users Conference.
• 7: Condi, F., Gunter, B., Ries, J., and Tapley, B. 2003. Combining sea surface and terrestrial gravity data for global geopotential modelling and geoid determination. In Eos Trans. AGU, 84(46), Fall Meet. Suppl., Abstract G31A-06.
• 8: Jack Dongarra , E. F. D''Azevedo, The Design and Implementation of the Parallel Out-of-coreScaLAPACK LU, QR, and Cholesky Factorization Routines, University of Tennessee, Knoxville, TN, 1997
• 9: Dongarra, J., Kaufmann, L., and Hammarling, S. 1986. Squeezing the most out of eigenvalue solvers on high-performance computers. Linear Algebra and It Applications 77:113--136.
• 10: Jack J. Dongarra , Robert A. van de Geijn , David W. Walker, Scalability issues affecting the design of a dense linear algebra library, Journal of Parallel and Distributed Computing, v.22 n.3, p.523-537, Sept. 1994 [doi>10.1006/jpdc.1994.1108]
• 11: Dongarra, J. J., Bunch, J. R., Moler, C. B., and Stewart, G. W. 1979. LINPACK Users' Guide. SIAM, Philadelphia.
• 12: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 13: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 14: Jack J. Dongarra , Iain S. Duff , Danny C. Sorensen , Henk Van Der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990
• 15: Erik Elmroth , Fred G. Gustavson, New Serial and Parallel Recursive QR Factorization Algorithms for SMP Systems, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.120-128, June 14-17, 1998
• 16: Elmroth, E. and Gustavson, F. G. 2000. Applying recursion to serial and parallel QR factorization leads to better performance. IBM J. Res. Dev. 44, 4 (July), 605--624.
• 17: Elmroth, E. and Gustavson, F. G. 2001. A faster and simpler recursive algorithm for the LAPACK routine DGELS. BIT 41, 5, 936--949.
• 18: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 19: Gropp, W., Lusk, E., and Skjellum, A. 1994. Using MPI. The MIT Press.
• 20: John A. Gunnels , Fred G. Gustavson , Greg M. Henry , Robert A. van de Geijn, FLAME: Formal Linear Algebra Methods Environment, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.422-455, December 2001 [doi>10.1145/504210.504213]
• 21: Gunter, B. C. 2000. Parallel least squares analysis of simulated GRACE data. CSR Technical Memoranda CSR-TM-00-05, The Center for Space Research, The University of Texas at Austin.
• 22: Brian C. Gunter , Wesley C. Reiley , Robert A. van de Geijn, Parallel Out-of-Core Cholesky and QR Factorization with POOCLAPACK, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.179, April 23-27, 2001
• 23: Gunter, B. C., Tapley, B. D., and van de Geijn, R. A. 2001b. Advanced parallel least squares algorithms for GRACE data processing. In Proceedings of the International Association of Geodesy (IAG) Conference. Budapest, Hungary.
• 24: Bruce A. Hendrickson , David E. Womble, The torus-wrap mapping for dense matrix calculations on massively parallel computers, SIAM Journal on Scientific Computing, v.15 n.5, p.1201-1226, Sept. 1994 [doi>10.1137/0915074]
• 25: Klimkowski, K. and van de Geijn, R. 1995. Anatomy of an out-of-core dense linear solver. In Proceedings of the International Conference on Parallel Processing 1995. Vol. III---Algorithms and Applications. 29--33.
• 26: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 27: Lichtenstein, W. and Johnsson, S. L. 1992. Block-cyclic dense linear algebra. Tech. Rep. TR-04-92, Harvard University, Center for Research in Computing Technology. Jan.
• 28: Enrique S. Quintana-Ortí , Robert A. van de Geijn, Formal derivation of algorithms: The triangular sylvester equation, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.218-243, June 2003 [doi>10.1145/779359.779365]
• 29: Rabani, E. and Toledo, S. 2001. Out-of-core SVD and QR decompositions. In Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing (PARA). Norfolk, Virginia.
• 30: Wesley C. Reiley, Efficient Parallel Out-of-Core Implementation of the Cholesky Factorization, University of Texas at Austin, Austin, TX, 1999
• 31: Wesley C. Reiley , Robert A. van de Geijn, POOCLAPACK: Parallel Out-of-Core Linear Algebra Package, University of Texas at Austin, Austin, TX, 1999
• 32: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 33: Scott, D. S. 1993. Parallel I/O and solving out-of-core systems of linear equations. In Proceedings of the 1993 DAGS/PC Symposium. Dartmouth Institute for Advanced Graduate Studies, Hanover, NH, 123--130.
• 34: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 35: Stewart, G. 1990. Communication and matrix computations on large message passing systems. Parallel Computing 16, 27--40.
• 36: Strazdins, P. 1998. Optimal load balancing techniques for block-cyclic decompositions for matrix factorization. Tech. Rep. TR-CS-98-10, Canberra 0200 ACT, Australia.
• 37: Sivan Toledo , Fred G. Gustavson, The design and implementation of SOLAR, a portable library for scalable out-of-core linear algebra computations, Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.28-40, May 27-27, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/236017.236029]
• 38: Sivan Toledo , Eran Rabani, Very large electronic structure calculations using an out-of-core filter-diagonalization method, Journal of Computational Physics, v.180 n.1, p.256-269, July 20, 2002 [doi>10.1006/jcph.2002.7090]
• 39: Robert A. van de Geijn , Philip Alpatou , Greg Baker , Carter Edwards , John Gunnels , Greg Morrow , James Overfelt, Using PLAPACK: parallel linear algebra package, MIT Press, Cambridge, MA, 1997
• 40: David S. Watkins, Fundamentals of matrix computations, John Wiley & Sons, Inc., New York, NY, 1991

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Earth and atmospheric sciences

General Terms:
Algorithms, Performance, Theory

Keywords:
Linear algebra, dense systems, linear least squares