Scientific Computing Seminar

Date:

Friday, April 1, 2005

Time:

1:00pm-2:00pm

Location:

50A-5132

Seminar Speaker:

Weiguo Gao
Scientific Computing Group
CRD, LBNL
WGGao (at) lbl (dot) gov

Title:

An Algebraic-Substructuring Method for Large-Scale Eigenvalue Calculation

Abstract:

This talk is concerned with solving large-scale eigenvalue problems by algebraic sub-structuring. Algebraic sub-structuring refers to the process of applying matrix reordering and partitioning algorithms to divide a large sparse matrix into smaller submatrices from which a subset of spectral components are extracted and combined to form approximate solutions to the original problem. Through an algebraic analysis, we identified the critical conditions under which algebraic sub-structuring works well. In particular, we observe an interesting connection between the accuracy of an approximate eigenpair obtained through sub-structuring and the distribution of the components of eigenvectors of a canonical matrix pencil congruent to the original problem. A priori error bounds for the smallest eigenpair approximation are developed, which lead to a simple heuristic for choosing spectral components (modes) from each sub-structure. The effectiveness of such a heuristic is demonstrated with numerical examples. We show that algebraic sub-structuring can be effectively used to solve a generalized eigenvalue problem arising from the finite element analysis of an accelerator structure. One interesting characteristic of this application is that the stiffness matrix contains a null space of large dimension. An efficient scheme to deflate this null space in the algebraic sub-structuring process is presented. We implemented a multilevel algorithm which deals with the presence of the null space. We also demonstrate the performance of this algorithm, and compare it with the shift-and-invert Lanczos algorithm.

This is joint work with Chao Yang, Zhaojun Bai, Xiaoye Li, Lie-quan Lee, Parry Husbands, Esmond Ng.

Sponsor of Seminar:

Sherry Li

Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov