Adaptive eigenvalue computation: Complexity estimates

DOI10.1007/S00211-008-0159-5MaRDI QIDQ958152zbMATH OpenOpenAlexFDO

Authors Wolfgang Dahmen, Thorsten Rohwedder, Reinhold Schneider, Andreas Zeiser

Publication date 2 December 2008

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.1070

zbMATH Keywords

adaptive algorithmadaptive eigenvalue solveralgorithm MINIEIGalgorithm MINITcomplexity estimateseigenvalue problem in abstract spacefinite differencesfinite elementsHilbert spacelinear symmetric,boundedpreconditioningRayleigh quotientSchrödinger equationsteepest descent methodstrongly positive operator

Mathematics Subject Classification ID

PDEs in connection with quantum mechanics (35Q40) Spectrum, resolvent (47A10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to equations with linear operators (65J10) Finite difference methods for boundary value problems involving PDEs (65N06) Numerical methods for eigenvalue problems for boundary value problems involving PDEs (65N25) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)

Abstract: This paper is concerned with the design and analysis of a fully adaptive eigenvalue solver for linear symmetric operators. After transforming the original problem into an equivalent one formulated on $el{l}_2$, the space of square summable sequences, the problem becomes sufficiently well conditioned so that a gradient type iteration can be shown to reduce the error by some fixed factor per step. It then remains to realize these (ideal) iterations within suitable dynamically updated error tolerances. It is shown under which circumstances the adaptive scheme exhibits in some sense asymptotically optimal complexity.

Review text

For a linear symmetric bounded and strongly positive operator in Hilbert space, an eigenvalue problem in the weak sense is considered. By discretizing this problem using finite elements or finite differences, an equivalent finite dimensional problem can be obtained. The authors apply the analysis to the finite dimensional problem, but in the same time an abstract iteration scheme that solves the original infinite dimensional problem is proposed. The authors are focused on developing and analyzing a convergent adaptive algorithm and yield complexity estimates to prove the (asymptotic ) optimality of the scheme. The basic algorithm MINIT, that is used in analysis of the adaptive algorithm, is proposed. This algorithm can be viewed as a preconditioned steepest descent method for minimizing the Rayleigh quotient. In fact, this basic algorithm resembles the preconditioned Richardson iteration. The main adaptive algorithm named MINIEIG, solves iteratively the eigenvalue problem. As the authors show, the results proved in this paper can be applied to solve the Schrödinger equation.

Recommendations

• Convergence and optimal complexity of adaptive finite element eigenvalue computations
• An adaptive finite element eigenvalue solver of asymptotic quasi-optimal computational complexity
• Adaptive algorithms for solving eigenvalue problems in the variable computer environment of supercomputers
• Adaptive algorithms for first principal eigenvector computation
• scientific article; zbMATH DE number 503390
• Convergence and quasi-optimal complexity of adaptive finite element computations for multiple eigenvalues
• Fast adaptive algorithms using eigenspace projections
• Adaptive computation of smallest eigenvalues of self-adjoint elliptic partial differential equations.
• scientific article; zbMATH DE number 3880066
• Performances analysis of a Givens parametrized adaptive eigenspace algorithm

Cites work

• A convergent adaptive method for elliptic eigenvalue problems
• A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems
• A subspace preconditioning algorithm for eigenvector/eigenvalue computation
• Adaptive methods for boundary integral equations: complexity and convergence estimates
• Adaptive wavelet methods for elliptic operator equations: Convergence rates
• Adaptive wavelet methods. II: Beyond the elliptic case
• Adaptive Wavelet Schemes for Nonlinear Variational Problems
• Computation of differential operators in wavelet coordinates
• Finite element methods (Part 1)
• scientific article; zbMATH DE number 3622441 (Why is no real title available?)
• scientific article; zbMATH DE number 1215245 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 1069611 (Why is no real title available?)
• scientific article; zbMATH DE number 2001584 (Why is no real title available?)
• scientific article; zbMATH DE number 3239038 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Introduction to spectral theory. With applications to Schrödinger operators
• On the Compressibility of Operators in Wavelet Coordinates
• Perturbed preconditioned inverse iteration for operator eigenvalue problems with applications to adaptive wavelet discretization

Cited in

(19)

• An adaptive nonconforming finite element algorithm for Laplace eigenvalue problem
• Smoothed-adaptive perturbed inverse iteration for elliptic eigenvalue problems
• Adaptive wavelet methods for elliptic partial differential equations with random operators
• Adaptive eigenvalue computations using Newton's method on the Grassmann manifold
• An adaptive algorithm based on the shifted inverse iteration for the Steklov eigenvalue problem
• Adaptive computation of smallest eigenvalues of self-adjoint elliptic partial differential equations.
• Strategies for \(h\)-adaptive refinement for a finite element treatment of harmonic oscillator Schrödinger eigenproblem
• Guaranteed lower bounds for eigenvalues
• The shifted-inverse iteration based on the multigrid discretizations for eigenvalue problems
• Improving projection‐based eigensolvers via adaptive techniques
• scientific article; zbMATH DE number 4115829 (Why is no real title available?)
• Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction
• Adaptive algorithms for solving eigenvalue problems in the variable computer environment of supercomputers
• Perturbed preconditioned inverse iteration for operator eigenvalue problems with applications to adaptive wavelet discretization
• Convergence and Complexity of an Adaptive Planewave Method for Eigenvalue Computations
• An adaptive homotopy approach for non-selfadjoint eigenvalue problems
• Finite element approximations of nonlinear eigenvalue problems in quantum physics
• Introduction: Wolfgang Dahmen's mathematical work (as of 2009)
• Fast adaptive algorithms using eigenspace projections

This page was built for publication: Adaptive eigenvalue computation: Complexity estimates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q958152)