# Presentation: 004634

## Report from LBNL

**TOPS Meeting**
**01-25-2002**

## Investigators

- Staff Members:
- Parry Husbands
- Sherry Li
- Osni Marques
- Esmond G. Ng
- Chao Yang
- New Postdocs:
- Laura Grigori
- Ali Pinar

## Eigenvalue Calculations

- Collaboration with SLAC in electromagnetic simulations
- Parry Husbands, Chao Yang
- Ported Omega3P (a generalized eigensolver) to Cray T3E and IBM SP at NERSC
- Started to analyze and understand the convergence property of “inexact” shift-invert Lanczos (ISIL) algorithm in Omega3P
- Seek ways to improve ISIL
- Compare ISIL with exact shift-invert Lanczos

## Analyzing ISIL

- Yong Sun (Stanford): Implemented “inexact” shift-invert Lanczos algorithm in Omega3P
- Work well on some problems, but not on others.  Why?
- Need to solve Ax = b , where A = K – sM may be indefinite
- Use PCG + localized symmetric Gauss-Seidel to solve Ax = b
- Currently solved using Aztec
- “Local” means matrix splitting on distributed submatrix; splitting yields a matrix B, which is used to construct a preconditioner P
- Apply CG to PAx = Pb
- CG convergence tolerance: 10-2
- Issues to be investigated:
- In terms of eigenvectors of A, is it OK to have large error in the direction associated with the smallest eigenvalues of A?
- Is it OK not to have a Krylov subspace?

## Improving accuracy of ISIL

- Suppose an approximate eigenpair (,q) is computed (perhaps from ISIL)
- One can seek a correction pair (,z) such that (+,q+z) is a better approximation to the generalized eigenvalue problem.
- Yong:  If q and z are orthogonal, the refinement can be obtained by solving a second order corrector equation, which is nonsymmetric.
- If q and z are M-orthogonal, then the second order corrector equation will be symmetric.
- Implementation underway.

## Parallel exact shift-invert Lanczos

- Provide a reference point for other eigenvalue calculation methods
- Effective and reliable for small to medium sized problems (0.5 – 1 M unknowns); possible on NERSC IBM SP
- PARPACK (Sorensen’s Implicitly Restarted Lanczos/Arnoldi)
- Lanczos/Arnoldi vectors are distributed
- Projected problem (tridiagonal/Hessenberg) replicated
- Need sparse LU factorizations
- Incorporated distributed-memory SuperLU
- Symbolic processing is sequential and requires a fully assembled matrix
- Solution vector and right-hand side are not distributed yet
- Considering Raghavan’s DSCPACK for real symmetric matrices
- Use AZTEC to perform parallel (mass) matrix-vector multiplications

## Eigenvalue Opportunities

- Supernovae Project, Tony Mezzacappa (ORNL)
- Large, sparse eigenvalue problems
- Matrices never formed explicitly
- Each matrix is a function of 0-1 matrices
- Fusion Project, Mitch Pindzola (Auburn)
- Currently solving small dense Hermitian eigenvalue problems using ScaLapack from ACTS Toolkit
- Eventually will be dealing with large complex symmetric eigenvalue problems
- A number of chemistry projects
- Piotr Piecuch (Michigan StateU)
- Russ Pitzer (Ohio State U)
- Peter Taylor (UC San Diego)

## Eigenvalue Opportunities

- One-day meeting between TOPS/eigenvalue and apps planned.
- Endorsed by several apps
- Details to be worked out
- All TOPS/eigenvalue folks to be invited
- LBNL, UCB, ANL
- Mitch Pindzola has requested an eigenvalue short course be given in the summer

## Preconditioning

- Scalable preconditioning using incomplete factorization
- Padma Raghavan, Keita Teranishi, Esmond Ng
- Parallel implementation of incomplete Cholesky factorization
- Use of selective inversion to improve scalability of parallel application of incomplete factors during iterations
- Performance studied
- Paper completed and submitted to Numerical Linear Algebra and Applications

## Sparse Direct Methods

- Distributed memory SuperLU (SuperLU_DIST)
- Sherry Li
- Working with Argonne folks to interface distributed-memory SuperLU code with PETSc
- Finishing 2 papers
- One on distributed-memory SuperLU
- Another on on a new ordering algorithm for unsymmetric LU factorization
- Next milestone is to provide distributed matrix input for distributed-memory SuperLU

## Sparse Direct Methods

- Sparse Gaussian elimination with low storage requirements
- Alan George, Esmond Ng
- Attempt to break the storage bottleneck
- Based on “throw-away” ideas
- Discard portion of factors after it is computed
- Recompute missing portion of factors when needed
- Reduce storage requirement substantially, but increase solution time ... can control how much storage to use
- Sequential implementation for symmetric positive definite matrices completed
- Parallel implementation to follow
- Extension to general nonsymmetric matrices to be investigated