The Hierarchical Subspace Iteration Method for Laplace–Beltrami Eigenproblems
Open Access
- 4 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 41 (2) , 1-14
Abstract
Sparse eigenproblems are important for various applications in computer graphics. The spectrum and eigenfunctions of the Laplace–Beltrami operator, for example, are fundamental for methods in shape analysis and mesh processing. The Subspace Iteration Method is a robust solver for these problems. In practice, however, Lanczos schemes are often faster. In this article, we introduce the Hierarchical Subspace Iteration Method (HSIM) , a novel solver for sparse eigenproblems that operates on a hierarchy of nested vector spaces. The hierarchy is constructed such that on the coarsest space all eigenpairs can be computed with a dense eigensolver. HSIM uses these eigenpairs as initialization and iterates from coarse to fine over the hierarchy. On each level, subspace iterations, initialized with the solution from the previous level, are used to approximate the eigenpairs. This approach substantially reduces the number of iterations needed on the finest grid compared to the non-hierarchical Subspace Iteration Method. Our experiments show that HSIM can solve Laplace–Beltrami eigenproblems on meshes faster than state-of-the-art methods based on Lanczos iterations, preconditioned conjugate gradients, and subspace iterations.Keywords
All Related Versions
Funding Information
- Indonesia Endowment Fund for Education
This publication has 61 references indexed in Scilit:
- The subspace iteration method – RevisitedComputers & Structures, 2013
- An Operator Approach to Tangent Vector Field ProcessingComputer Graphics Forum, 2013
- Practical Anisotropic GeodesyComputer Graphics Forum, 2013
- Acceleration of a two-grid method for eigenvalue problemsMathematics of Computation, 2011
- Shape Decomposition using Modal AnalysisComputer Graphics Forum, 2009
- Accelerated subspace iteration with aggressive shiftComputers & Structures, 2007
- A comparison of eigensolvers for large-scale 3D modal analysis using AMG-preconditioned iterative methodsInternational Journal for Numerical Methods in Engineering, 2005
- Computation of a few smallest eigenvalues of elliptic operators using fast elliptic solversCommunications in Numerical Methods in Engineering, 2001
- A two-grid discretization scheme for eigenvalue problemsMathematics of Computation, 1999
- An eigensolution strategy for large systemsComputers & Structures, 1983