Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn pole-swapping algorithms for the eigenvalue problem
218
0
0.0
(
0
)
Added by
David Watkins
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Pole-swapping algorithms, which are generalizations of the QZ algorithm for the generalized eigenvalue problem, are studied. A new modular (and therefore more flexible) convergence theory that applies to all pole-swapping algorithms is developed. A key component of all such algorithms is a procedure that swaps two adjacent eigenvalues in a triangular pencil. An improved swapping routine is developed, and its superiority over existing methods is demonstrated by a backward error analysis and numerical tests. The modularity of the new convergence theory and the generality of the pole-swapping approach shed new light on bi-directional chasing algorithms, optimally packed shifts, and bulge pencils, and allow the design of novel algorithms.
rate research
Read More
Pole-swapping algorithms are generalizations of bulge-chasing algorithms for the generalized eigenvalue problem. Structure-preserving pole-swapping algorithms for the palindromic and alternating eigenvalue problems, which arise in control theory, are derived. A refinement step that guarantees backward stability of the algorithms is included. This refinement can also be applied to bulge-chasing algorithms that had been introduced previously, thereby guaranteeing their backward stability in all cases.
A thorough backward stability analysis of Hotellings deflation, an explicit external deflation procedure through low-rank updates for computing many eigenpairs of a symmetric matrix, is presented. Computable upper bounds of the loss of the orthogonality of the computed eigenvectors and the symmetric backward error norm of the computed eigenpairs are derived. Sufficient conditions for the backward stability of the explicit external deflation procedure are revealed. Based on these theoretical results, the strategy for achieving numerical backward stability by dynamically selecting the shifts is proposed. Numerical results are presented to corroborate the theoretical analysis and to demonstrate the stability of the procedure for computing many eigenpairs of large symmetric matrices arising from applications.
In this paper, based on a domain decomposition (DD) method, we shall propose an efficient two-level preconditioned Helmholtz-Jacobi-Davidson (PHJD) method for solving the algebraic eigenvalue problem resulting from the edge element approximation of the Maxwell eigenvalue problem. In order to eliminate the components in orthogonal complement space of the eigenvalue, we shall solve a parallel preconditioned system and a Helmholtz projection system together in fine space. After one coarse space correction in each iteration and minimizing the Rayleigh quotient in a small dimensional Davidson space, we finally get the error reduction of this two-level PHJD method as $gamma=c(H)(1-Cfrac{delta^{2}}{H^{2}})$, where $C$ is a constant independent of the mesh size $h$ and the diameter of subdomains $H$, $delta$ is the overlapping size among the subdomains, and $c(H)$ decreasing as $Hto 0$, which means the greater the number of subdomains, the better the convergence rate. Numerical results supporting our theory shall be given.
Perturbation analysis has been primarily considered to be one of the main issues in many fields and considerable progress, especially getting involved with matrices, has been made from then to now. In this paper, we pay our attention to the perturbation analysis subject on tensor eigenvalues under tensor-tensor multiplication sense; and also {epsilon}-pseudospectra theory for third-order tensors. The definition of the generalized T-eigenvalue of third-order tensors is given. Several classical results, such as the Bauer-Fike theorem and its general case, Gershgorin circle theorem and Kahan theorem, are extended from matrix to tensor case. The study on {epsilon}-pseudospectra of tensors is presented, together with various pseudospectra properties and numerical examples which show the boundaries of the {epsilon}-pseudospectra of certain tensors under different levels.
Stochastic PDE eigenvalue problems often arise in the field of uncertainty quantification, whereby one seeks to quantify the uncertainty in an eigenvalue, or its eigenfunction. In this paper we present an efficient multilevel quasi-Monte Carlo (MLQMC) algorithm for computing the expectation of the smallest eigenvalue of an elliptic eigenvalue problem with stochastic coefficients. Each sample evaluation requires the solution of a PDE eigenvalue problem, and so tackling this problem in practice is notoriously computationally difficult. We speed up the approximation of this expectation in four ways: 1) we use a multilevel variance reduction scheme to spread the work over a hierarchy of FE meshes and truncation dimensions; 2) we use QMC methods to efficiently compute the expectations on each level; 3) we exploit the smoothness in parameter space and reuse the eigenvector from a nearby QMC point to reduce the number of iterations of the eigensolver; and 4) we utilise a two-grid discretisation scheme to obtain the eigenvalue on the fine mesh with a single linear solve. The full error analysis of a basic MLQMC algorithm is given in the companion paper [Gilbert and Scheichl, 2021], and so in this paper we focus on how to further improve the efficiency and provide theoretical justification of the enhancement strategies 3) and 4). Numerical results are presented that show the efficiency of our algorithm, and also show that the four strategies we employ are complementary.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
