Forward stable eigenvalue decomposition of rank-one modifications of diagonal matrices

DOI10.1016/J.LAA.2015.09.025zbMATH Open1325.65053arXiv1405.7537OpenAlexW1827065324MaRDI QIDQ890573FDOQ890573

Authors: Nevena Jakovčević Stor, Ivan Slapničar, Jesse L. Barlow 

Publication date: 10 November 2015

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We present a new algorithm for solving an eigenvalue problem for a real symmetric matrix which is a rank-one modification of a diagonal matrix. The algorithm computes each eigenvalue and all components of the corresponding eigenvector with high relative accuracy in $O(n)$ operations. The algorithm is based on a shift-and-invert approach. Only a single element of the inverse of the shifted matrix eventually needs to be computed with double the working precision. Each eigenvalue and the corresponding eigenvector can be computed separately, which makes the algorithm adaptable for parallel computing. Our results extend to the complex Hermitian case. The algorithm is similar to the algorithm for solving the eigenvalue problem for real symmetric arrowhead matrices from: N. Jakovv{c}evi'{c}~Stor, I. Slapniv{c}ar and J. L. Barlow, {Accurate eigenvalue decomposition of real symmetric arrowhead matrices and applications}, Lin. Alg. Appl., 464 (2015).

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

Recommendations

• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Accurate eigenvalue decomposition of real symmetric arrowhead matrices and applications
• Computing the eigenvalues of modified symmetric matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• On the Spectral Decomposition of Hermitian Matrices Modified by Low Rank Perturbations with Applications

zbMATH Keywords

eigenvalue decompositionreal symmetric matrixarrowhead matrixhigh relative accuracydiagonal-plus-rank-one matrixforward stability

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Roundoff error (65G50) Special matrices (15B99) Software, source code, etc. for problems pertaining to linear algebra (15-04)

Cites Work

• Title not available (Why is that?)
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Title not available (Why is that?)
• Matrix algorithms. Vol. 2: Eigensystems
• Matrix mathematics. Theory, facts, and formulas
• Accuracy and Stability of Numerical Algorithms
• Rank-one modification of the symmetric eigenproblem
• Title not available (Why is that?)
• Matrix computations and semiseparable matrices. Vol. 1: Linear systems.
• Title not available (Why is that?)
• Title not available (Why is that?)
• A floating-point technique for extending the available precision
• A Divide and Conquer method for the symmetric tridiagonal eigenproblem
• A Fully Parallel Algorithm for the Symmetric Eigenvalue Problem
• Structures preserved by matrix inversion
• Numerical solution of a secular equation
• A Divide-and-Conquer Algorithm for the Bidiagonal SVD
• Accurate eigenvalue decomposition of real symmetric arrowhead matrices and applications
• Error Analysis of Update Methods for the Symmetric Eigenvalue Problem
• Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices
• On eigenvectors and adjoints of modified matrices
• N Roots of the Secular Equation in O(N) Operations

Cited In (8)

• Deflation for the Symmetric Arrowhead and Diagonal-Plus-Rank-One Eigenvalue Problems
• Über die Falksche ECP-Transformation und Verallgemeinerungen
• Randomized greedy magic point selection schemes for nonlinear model reduction
• A new method to improve the efficiency and accuracy of incremental singular value decomposition
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Fast optimization of viscosities for frequency‐weighted damping of second‐order systems
• Note on a rank-one modification of the singular value decomposition
• On anti-pentadiagonal persymmetric Hankel matrices with perturbed corners

Uses Software

• LAPACK
• Maple
• Matlab
• mctoolbox
• MKL
• Julia

This page was built for publication: Forward stable eigenvalue decomposition of rank-one modifications of diagonal matrices

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