×

The design and implementation of the parallel out-of-core scaLAPACK LU, QR, and Cholesky factorization routines. (English) Zbl 1008.68577

Summary: This paper describes the design and implementation of three core factorization routines – LU, QR, and Cholesky – included in the out-of-core extension of ScaLAPACK. These routines allow the factorization and solution of a dense system that is too large to fit entirely in physical memory. The full matrix is stored on disk and the factorization routines transfer sub-matrice panels into memory. The ‘left-looking’ column-oriented variant of the factorization algorithm is implemented to reduce the disk I/O traffic. The routines are implemented using a portable I/O interface and utilize high-performance ScaLAPACK factorization routines as in-core computational kernels.
We present the details of the implementation for the out-of-core ScaLAPACK factorization routines, as well as performance and scalability results on a Beowulf Linux cluster.

MSC:

68U99 Computing methodologies and applications
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berry, Physics Review Letters 82 (1999)
[2] Jaeger, Physics of Plasmas 7 (2000)
[3] Jaeger, Physics of Plasmas 7 pp 3319– (2000)
[4] Cwik, Journal of the Optical Society of America A 11 (1994)
[5] Demkowicz, Computer Methods in Applied Mechanics and Engineering (1992)
[6] Geng, Journal of Sound and Vibration 191 (1996) · Zbl 1232.76033
[7] Semeraro, Engineering Analysis with Boundary Elements 19 (1997)
[8] Fu, International Journal of Numerical Methods in Engineering 42 (1998) · Zbl 0904.73072
[9] A proposal for a set of parallel basic linear algebra subprograms. Technical Report CS-95-292, University of Tennessee, Knoxville, TN, May 1995 (also available as LAPACK Working Note #100).
[10] Choi, Concurrency: Practice and Experience 8 pp 517– (1996)
[11] Algorithmic redistribution methods for block cyclic decompositions. PhD Thesis, University of Tennessee, Knoxville, Tennessee, 1996 (also available as LAPACK Working Note # 128 and #133).
[12] Two dimensional basic linear algebra communication subprograms. Technical Report CS-91-138, University of Tennessee, Knoxville, Tennessee, 1991 (also available as LAPACK Working Note #37).
[13] Two dimensional basic linear algebra communication subprograms. Environments and Tools for Parallel Scientific Computing, Vol 6. Elsevier Science Publishers B.V., 1993; 31-40.
[14] Load-balanced LU and QR factor and solve routines for scalable processors with scalable I/O. Proceedings of the 17th IMACS World Congress, 1994.
[15] Anatomy of a parallel out-of-core dense linear solver. Proceedings of the International Conference on Parallel Processing, 1995.
[16] Out of core dense solvers on Intel parallel supercomputers. Proceedings of the Fourth Symposium on the Frontiers of Massively Parallel Computation, 1992; 484.
[17] Parallel I/O and solving out-of-core systems of linear equations. Proceedings of the 1993 DAGS/PC Symposium, Darmouth Institute for Advanced Graduate Studies, 1993; 123.
[18] POOCLAPACK: Parallel out-of-core linear algebra package. Technical Report 99-33, Department of Computer Science, The University of Texas, Austin, Texas, 1999 (also available as PLAPACK Working Note #10).
[19] Dongarra, Computers and Mathematics with Applications 35 pp 13– (1998) · Zbl 1010.68539
[20] Locality of reference in LU decomposition with partial pivoting. Technical Report RC 20344(1/19/96), IBM Research Division, T. J. Watson Research Center, Yorktown Heights, New York, 1996.
[21] The design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Technical Report ORNL/TM-12470, Oak Ridge National Laboratory, 1994.
[22] The design and implementation of SOLAR, a portable library for scalable out-of-core linear algebra computations. IOPADS Fourth Annual Workshop on Parallel and Distributed I/O. ACM Press, 1996; 28-40.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.