Sparse Linear Algebra Algorithms for MPPs

Research Objectives

Our goal is to develop a scalable parallel library to solve large sparse symmetric eigenproblems on distributed memory machines. Our research addresses several crucial issues such as robustness, scalability, and portability.

Computational Approach

A block-shifted and inverted Lanczos algorithm for sparse generalized eigenvalue problems is being implemented. Software components of this algorithm developed elsewhere are being integrated with newly developed software. Although our development platform is the Cray T3E at NERSC, the software will be developed in MPI and ported to other platforms.

Accomplishments

We ported and parallelized the scalar LANSO code by Beresford Parlett to run efficiently on the 512-processor Cray T3E at NERSC. We ported the new PLANSO code to a cluster of SMPs, where we studied the trade-off between shared memory (threads) and distributed memory (MPI) parallelism. We developed a new technique called "thick restart" and found that PLANSO runs consistently faster than competing software called PARPACK.

Scalable approximate inverse preconditioners based on the SPAI (sparse approximate inverse) approach by Barnard, Grote, and Huckle were investigated for their potential to speed up the Lanczos process. In collaboration with Steve Barnard at NASA Ames, the SPAI software was ported and tested successfully on the T3E. We believe this is the first preconditioner that can be scaled to 512 processors.

We investigated a number of applications of the Lanczos algorithm:

1. We applied the algorithm to large text retrieval using latent semantic indexing. In collaboration with the Web search engine Inktomi (HotBot), we used our algorithm to compute the first 5 singular values of a data matrix of 100,000 terms by 2,559,430 documents. To our knowledge this is the first time that the singular value decomposition of such a large matrix has been computed.

2. In collaboration with Don Vasco of the Berkeley Lab Earth Sciences Division, our algorithms were used to solve inverse problems arising in the study of the Earth's interior structure (see figure). The resulting matrices were of the order 1,500,000 by 200,000.

3. With the Cohen-Louie group at UC Berkeley, we considered the application of the new Lanczos algorithm to electronic structure calculations in materials science. In this case the direct application of the Lanczos code proved to be less effective than a conjugate-gradient minimization.

Significance

Scalable sparse linear algebra algorithms can provide efficient solutions to common problems in computational chemistry, physics, earth sciences, materials science, and information retrieval on a previously unknown scale. The software library under development will be easily portable to other platforms and emerging new architectures.

Publications

Pfrommer, B., S. Louie, and H. Simon. 1997. Conjugate gradient based electronic structure calculations on the Cray T3E and SGI PowerChallenge. Proc. of the 8th SIAM Conference on Parallel Processing, Minneapolis, March 1997.

Simon, H. D., and H. Zha. 1997. Low rank matrix approximation using the Lanczos bidiagonalization process. LBNL-40767. Submitted to SIAM J. Scientific Computing.

Barnard, S. T., L. Bernardo, and H. D. Simon. 1997. An MPI implementation of the SPAI preconditioner on the T3E. LBNL-40794. Submitted to Int. J. of Supercomputer Applications.

New images of deep geological structures were revealed when innovative algorithms and NERSC's Cray T3E were used to transform seismic data from around the world into models of the three-dimensional seismic structure of the earth's crust, mantle, and core. Velocity variations in the uppermost mantle are correlated with surface tectonics, while variations at greater depths coincide with regions of past and present subduction. (Don Vasco and Osni Marques, Berkeley Lab)