NERSC Initiative for Scientific Exploration (NISE) 2011 Awards

Sparse Lanczos and GMRES Solvers in Co-Array Fortran (CAF)

Pierre Carrier, University of Minnesota - Twin Cities

Associated NERSC Project: Pseudopotential Algorithm for Real Space Electronic Calculations (m684)
Principal Investigator: Yousef Saad, University of Minnesota

The goal of this research is to implement a co-array fortran (CAF) sparse Lanczos computer program. A first implementation of the Lanczos algorithm will be applied to eigenvalue problems, the standard application used for Lanczos, and will take full advantage of the CAF language. A typical Lanczos algorithm requires sparse matrix-vector operations, partial or full re-orthogonalization of the Lanczos vectors (i.e., Gram-Schmidt), and multiple dot products [implying communication between processors for a reduction.

This new algorithm adds to a standard Lanczos algorithm an iterative solver based on preconditioned-GMRES, and a domain decomposition. Domain decomposition is perfectly well-suited for a parallel CAF environment of this algorithm, as described in this talk.

Once the structure of the standard Lanczos, the new Low-rank Lanczos, and the GMRES algorithms are completed using CAF, several reduction [similar to MPI_Reduce(SUM)] will be tested for the dot-products (e.g., tree-like reductions, such as the "butterfly" algorithm as used by FFT's), especially necessary in the more costly re-orthogonalization part of Lanczos.

Very few algorithms using CAF have been developed so far. CAF is part of the new fortran08 compiler, and it is thus imperative that computer programs based on this language become available to the scientific community. The Lanczos algorithm is used in many fields of quantum physics (e.g., for solving the Schroedinger equation, and recently for solving the Dyson equation, etc), as well as in computer science, in data mining and pattern recognition. The GMRES algorithm is at the heart of iterative linear system solves.