Interface for Eigenvalue Methods

John Wu

Lawrence Berkeley National Laboratory

[email protected]

[email protected]

Outline

• Review eigenvalue methods

• Examine existing schemes

• Explore possible alternatives

Types of Eigenvalue Problems

• Standard: Ax = lx

• Generalized: Ax = lBx

• Polynomial: -Ax+lB1x+l2B2x+…=0

• Constrains: Cx=0

Types of Methods

• QR based methods (direct methods)
  • Need to access the elements of the matrix
  • O(n2) space complexity
  • O(n3) time complexity

• Projection based methods (iterative)
  • Access matrix through MATVEC
  • Problem dependent space and time need

Existing Software

QR methods

• LAPACK

• EISPACK

• ScaLAPACK

• PLAPACK

Projection methods

• ARPACK

• LANSO, LASO, LANZ, LANCZOS …

• Davidson method, JDQZ, …

• RITZIT

• CG,

Specifying an Eigenvalue Problem

• Matrices: A, B, A-1, (A-sB)-1B, B-1A

• Type of eigenvalues: largest, smallest, around a center, in a range

• Number of eigenvalues

• Are eigenvectors needed as well

Specifying an Eigenvalue Problem -- Computing Issues

• Representations of matrices, eigenvalues and eigenvectors

• Interface to MATVEC and preconditioner

• Accuracy (reliability) requirement

• Resource constrains

• Controlling parameters

Case Study I -- LAPACK

netlib.org/lapack

SSYEVX(JOBZ, RANGE, UPLO, N, A, LDA, VL, VU, IL, IU, ABSTOL, M, W, Z, LDZ, WORK, LWORK, IWORK, IFAIL, INFO)

• QR based method

• Representing matrices as arrays (1-D)

• User provide workspace

• User must set all options

Case Study II -- ARPACK

ftp://ftp.caam.rice.edu/

pub/software/ARPACK

DNAUPD(COMM, IDO, BMAT, N, WHICH, NEV, TOL, RESID, NCV, V, LDV, IPARAM, IPNTR, WORKD, WORKL, LWORKL, INFO)

• Implicitly restarted Arnoldi method

• Reverse communication for MATVEC

• Arguments are arrays (1-D)

• User provides workspace

Case Study III -- TRLAN

lbl.gov/~kwu

TRLAN(OP, INFO, NROW, MEV, EVAL, EVEC, LDE)

• thick-restart Lanczos method

• MATVEC (OP) has a prescribed interface

• eigenvalues/eigenvectors are arrays

• use Fortran 90 TYPE (INFO) to store controlling parameters

Case Study IV -- ARPACK++

#include “areig.h”

Nconv = areig(EigValR, EigValI, EigVec, n, nnz, A, inrow, pcol, nev);

• Based on ARPACK

• Simple data structures for matrix, eigenvalues and eigenvectors

ftp://ftp.caam.rice.edu/

pub/software/ARPACK

Case Study V -- RogueWave

#include <rw/deig.h>

DoubleEigDecomp eig(a);

• QR based methods

• Solution stored in eig object

• Eig.eigenValues() for eigenvalues

www.roguewave.com

Two Basic Strategies

Eigenvalue function

• Closer to traditional libraries

• Explicit arguments for eigenvalue and eigenvector

• May be an interface of a matrix class

Decomposition class

• Computation is hidden

• Contains functions to output eigenvalues, etc

• Decomposition is an object

Basic Data Elements

Eigenvalue function

• Matrices

• Eigenvalue and eigenvector are function arguments

• Controlling parameters are function arguments

Decomposition class

• Matrices

• Eigenvalue and eigenvector stored internally

• Controlling parameters set by member function

Interaction With Other Components

Eigenvalue function

• Reverse communication or function pointer or direct access to the matrices

Decomposition class

• Function pointer (functor) or direct access to matrices

• External functions must use prescribed interface

Feature Comparison

Eigenvalue Class always has a decompose

function, but it may not be public

Relation With Equation Solvers

• Share the same basic elements: vector, multi-vector, matrices

• Share the same external/user-supplied functions: MATVEC, preconditioner

• Eigenvalue solver may use equation solver

Relation With Existing Software

• Existing matrix libraries may be used to specify basic data elements

• Existing Fortran/C libraries may be used to perform the actual computations

• Should make it easy to interact with existing frameworks, e.G., POOMA

Future Work

• Reviewing other OO eigenvalue software

• Concrete interface specification

• Data structure of the basic elements

• Interface of MATVEC and preconditioner