Updating an LU Factorization with Pivoting

ABSTRACT

We show how to compute an LU factorization of a matrix when the factors of a leading principle submatrix are already known. The approach incorporates pivoting akin to partial pivoting, a strategy we call incremental pivoting. An implementation using the Formal Linear Algebra Methods Environment (FLAME) application programming interface (API) is described. Experimental results demonstrate practical numerical stability and high performance on an Intel Itanium2 processor-based server.

REFERENCES

• 1: Paolo Bientinesi , John A. Gunnels , Margaret E. Myers , Enrique S. Quintana-Ortí , Robert A. van de Geijn, The science of deriving dense linear algebra algorithms, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.1-26, March 2005 [doi>10.1145/1055531.1055532]
• 2: Bientinesi, P. and van de Geijn, R. 2006. Representing dense linear algebra algorithms: A farewell to indices. Tech. Rep. FLAME Working Note 17, CS-TR-2006-10, Department of Computer Sciences, The University of Texas at Austin.
• 3: Cwik, T., van de Geijn, R., and Patterson, J. 1994. The application of parallel computation to integral equation models of electromagnetic scattering. J. Optic. Soc. Amer. A 11, 4 (Apr.), 1538--1545.
• 4: Demmel, J. and Dongarra, J. 2005. LAPACK 2005 prospectus: Reliable and scalable software for linear algebra computations on high end computers. LAPACK Working Note 164 UT-CS-05-546, University of Tennessee. February.
• 5: Geng, P., Oden, J. T., and van de Geijn, R. 1996. Massively parallel computation for acoustical scattering problems using boundary element methods. J. Sound Vibra. 191, 1, 145--165.
• 6: Goto, K. 2004. TACC software and tools. http://www.tacc.utexas.edu/resources/software/.
• 7: Kazushige Goto , Robert A. van de Geijn, Anatomy of high-performance matrix multiplication, ACM Transactions on Mathematical Software (TOMS), v.34 n.3, p.1-25, May 2008 [doi>10.1145/1356052.1356053]
• 8: John A. Gunnels , Greg M. Henry , Robert A. van de Geijn, A Family of High-Performance Matrix Multiplication Algorithms, Proceedings of the International Conference on Computational Sciences-Part I, p.51-60, May 28-30, 2001
• 9: Brian C. Gunter , Robert A. Van De Geijn, Parallel out-of-core computation and updating of the QR factorization, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.60-78, March 2005 [doi>10.1145/1055531.1055534]
• 10: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Superscalar GEMM-based Level 3 BLAS - The On-going Evolution of a Portable and High-Performance Library, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.207-215, June 14-17, 1998
• 11: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 12: Joffrain, T., Quintana-Ortí, E. S., and van de Geijn, R. A. 2005. Rapid development of high-performance out-of-core solvers. In Proceedings of the Workshop on Applied Parallel Computing (PARA 2004), J. Dongarra et al., eds. Lecture Notes in Computer Science, vol. 3732. Springer, 413--422.
• 13: Kågström, B., Ling, P., and Loan, C. V. 1995. Gemm-Based level 3 blas: High-Performance model, implementations and performance evaluation benchmark. LAPACK Working Note no. 107 CS-95-315, University of Tennessee. November.
• 14: Bo Kågström , Per Ling , Charles van Loan, GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.268-302, Sept. 1998 [doi>10.1145/292395.292412]
• 15: 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. vol. III - Algorithms and Applications, 29--33.
• 16: D. C. Sorensen, Analysis of Pairwise Pivoting in Gaussian Elimination, IEEE Transactions on Computers, v.34 n.3, p.274-278, March 1985 [doi>10.1109/TC.1985.1676570]
• 17: Stewart, G. W. 1998. Matrix Algorithms. Volume I: Basic Decompositions. SIAM, Philadelphia, PA.
• 18: Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]
• 19: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 20: 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]
• 21: Lloyd N. Trefethen , Robert S. Schreiber, Average-case stability of Gaussian elimination, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.335-360, Jul. 1990 [doi>10.1137/0611023]
• 22: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 23: Yip, E. L. 1979. Fortran subroutines for out-of-core solutions of large complex linear systems. Tech. Rep. CR-159142, NASA.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Performance

Keywords:
LU factorization, linear systems, pivoting, updating