Porting a sphere optimization program from LAPACK to ScaLAPACK

Abstract

The sphere optimization program sphopt was originally written as a sequential program using LAPACK, and was converted to use ScaLAPACK, primarily to overcome memory limitations. The conversion was relatively straightforward, using a small number of organizing principles which are widely applicable to the ScaLAPACK parallelization of serial code. The main innovation is the use of a compressed block cyclic storage scheme to store two symmetric matrices in little more than the storage needed for one matrix. The resulting sphopt program scales at least as well as the ScaLAPACK Cholesky decomposition routine which it uses. References

• E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. E. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. LAPACK Users' Guide (third ed.). SIAM, Philadelphia, 1999. http://www.netlib.org/lapack/lug/
• G. E. Andrews, R. Askey, and R. Roy. Special Functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2000.
• L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley. ScaLAPACK Users' Guide. SIAM, Philadelphia, 1997. http://www.netlib.org/scalapack/slug/
• J. Choi, J. J. Dongarra, L. S. Ostrouchov, A. P. Petitet, D. W. Walker, and R. C. Whaley. The design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Technical Report 80, LAPACK Working Note, Knoxville, September 1994. http://www.netlib.org/lapack/lawnspdf/lawn80.pdf
• J. Choi, J. J. Dongarra, R. Pozo, and D. W. Walker. ScaLAPACK: A scalable linear algebra for distributed memory concurrent computers. Technical Report 55, LAPACK Working Note, Knoxville, November 1992. http://www.netlib.org/lapack/lawnspdf/lawn55.pdf
• E. F. D'Azevedo and J. J. Dongarra. Packed storage extensions for ScaLAPACK. Technical Report 135, LAPACK Working Note, Knoxville, April 1998. http://www.netlib.org/lapack/lawnspdf/lawn135.pdf
• J. J. Dongarra, R. A. Vandegeijn, and D. W. Walker. Scalability issues affecting the design of a dense linear algebra library, Journal of Parallel and Distributed Computing 22 (3):523--537, September 1994. doi:10.1006/jpdc.1994.1108
• J. J. Dongarra and R. C. Whaley. A user's guide to the BLACS v1.1. Technical Report 94, LAPACK Working Note, Knoxville, May 1997. originally released March 1995. http://www.netlib.org/lapack/lawnspdf/lawn94.pdf
• P. Leopardi. Converting a sphere optimization program from LAPACK to ScaLAPACK, 2004. http://wwwmaths.anu.edu.au/ leopardi/conversion-LAPACK-ScaLAPACK.pdf
• D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Math. Programming, 45(3, (Ser. B)):503--528, 1989. doi:10.1007/BF01589116
• M. Reimer. Multivariate Polynomial Approximation, volume 144 of International Series of Numerical Mathematics. {Birkhauser} Verlag, Basel, 2003.
• I. H. Sloan and R. S. Womersley. Extremal systems of points and numerical integration on the sphere. Advances in Computational Mathematics, 21:107--125, 2004. doi:10.1023/B:ACOM.0000016428.25905.da
• D. W. Walker and J. J. Dongarra. MPI: a standard Message Passing Interface. Supercomputer, 12(1):56--68, 1996. http://users.cs.cf.ac.uk/David.W.Walker/MPI/supercomputer96.html
• C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal. Algorithm 778 L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization. ACM Transactions on Mathematical Software (TOMS), 23 (4): 550--560, December 1997. doi:10.1145/279232.279236