Advances in solution of classical generalized eigenvalue problem

P. Chen, Shichao Sun, Qiancheng Zhao, Yu-Cai Gong, Yuer Chen, Mingxuan YuanInteraction 2008 · DOI

TL;DR

This paper introduces an "aggressive shifting" technique for the subspace iteration method to significantly speed up the solution of large-scale generalized eigenvalue problems common in finite element analysis. By combining this aggressive shift with a robust "mode error" convergence criterion, the authors demonstrate substantial improvements in computational efficiency and stability compared to existing methods, including commercial software.

What Problem Does This Paper Address?

Modern engineering simulations, particularly those using the Finite Element Analysis (FEA), often involve solving very large generalized eigenvalue problems of the form $K\phi = \lambda M\phi$. These problems arise when analyzing structural dynamics, vibrations, and stability. As the size of these problems (number of degrees of freedom) and the demand for more eigenvalues increase, traditional direct solution methods become computationally prohibitive due to their high memory and CPU time requirements. Iterative methods offer a more scalable alternative, but they have historically suffered from slow convergence and unreliable convergence criteria, sometimes leading to missing or incorrect eigenvalues and eigenvectors. This paper aims to address these limitations by proposing more efficient and robust iterative algorithms and convergence strategies.

Methods

The paper focuses on three iterative algorithms for solving generalized eigenvalue problems:

  • Subspace Iteration (SIM): An established method that iteratively refines a subspace to capture the desired eigenpairs.
  • Iterative Ritz Vector Method: A method that uses Ritz vectors to approximate eigenvectors, often leading to faster convergence than standard subspace iteration.
  • Iterative Lanczos Method: A powerful technique that transforms the problem into a smaller, tridiagonal form, which is then solved.

The authors introduce several key advancements:

  • Cell Sparse Fast Solver and Loop-Unrolling: These implementation techniques are used to accelerate the core computations, particularly the triangular decomposition of matrices, offering significant speedups over traditional skyline solvers.
  • Mode Error Convergence Criterion: Instead of relying solely on eigenvalue convergence, the paper advocates for a "mode error" criterion. This criterion measures the imbalance in nodal forces (out-of-balance forces relative to maximum elastic or inertial forces), providing a more stable and reliable indicator of convergence for both eigenvalues and eigenvectors.
  • Aggressive Shifting Strategy: For the subspace iteration method, the paper proposes an "aggressive shift" that places the shift parameter closer to the target eigenvalues. This aims to accelerate convergence.
  • Backward Shifting Technique: To mitigate potential issues with aggressive shifting (e.g., the shift being in the wrong region), a backward shifting mechanism is introduced. This allows the algorithm to recover if the aggressive shift proves problematic.

Datasets

The paper uses several real-world structural models for numerical testing. These include:

  • PKUSTK Series: A set of problems previously used in the authors' work (PKUSTK01, PKUSTK03, PKUSTK11, PKUSTK12, PKUSTK13).
  • MM-08: A stadium model.
  • GUIZHEN: A Shijitang model.
  • PALACE: A museum in Shenzhen.
  • WENSHI: A botanical exhibition hall.
  • JIJIAN: A twin tower tall building.

These examples represent mechanical and civil engineering applications and vary in size, from approximately 6,840 to 160,074 equations. The data is generated using SAP84 and transferred to Harwell-Boeing RSA format.

Key Insights and Ideas

  • Mode Error is Crucial: The "mode error" convergence criterion is shown to be significantly more stable and reliable than eigenvalue-only criteria, especially for identifying accurate eigenvectors and avoiding issues like "ghost eigenvalues."
  • Aggressive Shifting Pays Off (Mostly): The aggressive shifting strategy for subspace iteration can dramatically reduce the number of iterations and CPU time, but it's not foolproof.
  • Backward Shifting is a Smart Safety Net: The backward shifting technique is essential for making aggressive shifting robust, allowing the algorithm to recover from problematic shift placements.
  • Cell Sparse Solvers are Fast: Implementing iterative methods with efficient sparse solvers (like their cell sparse solver) and loop-unrolling provides substantial performance gains.
  • Ritz Vector Method is Often Fastest: Among the three iterative methods compared, the iterative Ritz vector method generally shows the best average efficiency.

Key Results

  • Efficiency Gains: The proposed aggressive shifting technique, combined with the mode error criterion, significantly reduces computational effort. For example, the ISIMB0.4 method (aggressive shift with backward option) achieved an average speedup of 1.573 compared to a basic subspace iteration (BSIM) and 1.133 compared to a standard aggressive shift (ISIMG) when extracting 200 eigenpairs.
  • Stability: The mode error criterion leads to more stable convergence characteristics compared to eigenvalue-only criteria.
  • Comparison with ANSYS: The paper's subspace iteration method demonstrated superior efficiency and stability compared to ANSYS's subspace iteration and block Lanczos implementations, particularly for problems with multiple or closely spaced eigenvalues.
  • Storage Improvement: Large size tests showed tremendous improvement in terms of CPU time and storage.

Limitations and Future Work

  • Shift Placement Challenges: While aggressive shifting is beneficial, it can sometimes lead to difficulties if the shift is not optimally placed, potentially causing convergence delays or issues with Sturm's sequence checks. The backward shifting addresses this, but it implies that aggressive shifting isn't always a perfect solution without careful management.
  • Sturm's Sequence Check: The paper notes that Sturm's sequence checks can become problematic for problems with very close eigenvalues, even with the proposed methods.
  • Future Work: The paper implicitly suggests that further refinement of shifting strategies and convergence criteria, especially for complex scenarios like non-positive definite mass matrices or problems with rigid modes, could be areas for future research. The authors also mention that their work will be presented at an upcoming conference, indicating ongoing research and development.

Summary updated

Abstract

Owing to the growing size of the eigenvalue problem and the growing number of eigenvalues desired, solution methods of iterative nature are becoming more popular than ever, which however suffer from low efficiency and lack of proper convergence criteria. In this paper, three efficient iterative eigenvalue algorithms are considered, i.e., subspace iteration method, iterative Ritz vector method and iterative Lanczos method based on the cell sparse fast solver and loop-unrolling. They are examined under the mode error criterion, i.e., the ratio of the out-of-balance nodal forces and the maximum elastic nodal point forces. Averagely speaking, the iterative Ritz vector method is the most efficient one among the three. Based on the mode error convergence criteria, the eigenvalue solvers are shown to be more stable than those based on eigenvalues only. Compared with ANSYS's subspace iteration and block Lanczos approaches, the subspace iteration presented here appears to be more efficient, while the Lanczos approach has roughly equal efficiency. The methods proposed are robust and efficient. Large size tests show that the improvement in terms of CPU time and storage is tremendous. Also reported is an aggressive shifting technique for the subspace iteration method, based on the mode error convergence criteria. A backward technique is introduced when the shift is not located in the right region. The efficiency of such a technique was demonstrated in the numerical tests.
BibTeX
@inproceedings{chen2008advances,
  author = {P. Chen and Shichao Sun and Qiancheng Zhao and Yu-Cai Gong and Yuer Chen and Mingxuan Yuan},
  title = {{Advances in solution of classical generalized eigenvalue problem}},
  booktitle = {Interaction},
  year = {2008},
  doi = {10.12989/imm.2008.1.2.211},
}
Figure