Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions

DOI10.1137/140990334zbMath1383.15012OpenAlexW2275630370MaRDI QIDQ3186101

Roland W. Freund, Yuji Nakatsukasa

Publication date: 8 August 2016

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: http://eprints.maths.manchester.ac.uk/2414/1/papersirevrevrevf_tosiam.pdf

zbMATH Keywords

singular value decompositionpolar decompositionsymmetric eigenvalue problemminimizing communicationrational approximation of the sign functionZolotarev function

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Roundoff error (65G50)

Related Items (21)

On semilocal convergence analysis for two-step Newton method under generalized Lipschitz conditions in Banach spaces ⋮ Generalised rational approximation and its application to improve deep learning classifiers ⋮ Rational Minimax Approximation via Adaptive Barycentric Representations ⋮ Complexity of quantum impurity problems ⋮ Stable and Efficient Computation of Generalized Polar Decompositions ⋮ On the Singular Values of Matrices with Displacement Structure ⋮ A Structure-Preserving Divide-and-Conquer Method for Pseudosymmetric Matrices ⋮ Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time ⋮ Fast Computation of Spectral Projectors of Banded Matrices ⋮ On Chebyshev-Davidson method for symmetric generalized eigenvalue problems ⋮ High-Order Retractions on Matrix Manifolds Using Projected Polynomials ⋮ Frame completion with prescribed norms via alternating projection method ⋮ Exponential node clustering at singularities for rational approximation, quadrature, and PDEs ⋮ Multiscale S-Fraction Reduced-Order Models for Massive Wavefield Simulations ⋮ Approximating the \(p\)th root by composite rational functions ⋮ A Backward Stable Algorithm for Computing the CS Decomposition via the Polar Decomposition ⋮ Rational minimax iterations for computing the matrix \(p\)th root ⋮ Matrix Inverse Trigonometric and Inverse Hyperbolic Functions: Theory and Algorithms ⋮ Zolotarev Iterations for the Matrix Square Root ⋮ Bounds on the Singular Values of Matrices with Displacement Structure ⋮ Bounding Zolotarev numbers using Faber rational functions

Uses Software

• JDQR
• FEAST
• JDQZ
• mftoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A computational method for eigenvalues and eigenvectors of a matrix with real eigenvalues
• A hyperbolic tangent identity and the geometry of Padé sign function iterations
• A parallel algorithm for computing the polar decomposition
• The matrix sign decomposition and its relation to the polar decomposition
• An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems
• Numerical methods for the QCDd overlap operator. I: Sign-function and error bounds
• Numerical experiments with algorithms for the ADI and Zolotarev coefficients
• Talbot quadratures and rational approximations
• A Jacobi-Davidson type method for the product eigenvalue problem
• Betrachtungen zur Quadratwurzeliteration
• PARALLEL SPECTRAL DIVISION USING THE MATRIX SIGN FUNCTION FOR THE GENERALIZED EIGENPROBLEM
• Near-Optimal Perfectly Matched Layers for Indefinite Helmholtz Problems
• Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD
• Backward Stability of Iterations for Computing the Polar Decomposition
• The Exponentially Convergent Trapezoidal Rule
• Zolotarev Quadrature Rules and Load Balancing for the FEAST Eigensolver
• Error Estimates and Evaluation of Matrix Functions via the Faber Transform
• Optimizing Halley's Iteration for Computing the Matrix Polar Decomposition
• Minimizing Communication in Numerical Linear Algebra
• Addendum: Is The Polar Decomposition Finitely Computable?
• Probabilistic Bounds for the Matrix Condition Number with Extended Lanczos Bidiagonalization
• A New Scaling for Newton's Iteration for the Polar Decomposition and its Backward Stability
• Computing $A^\alpha, \log(A)$, and Related Matrix Functions by Contour Integrals
• Asymptotic Expansion of the First Elliptic Integral
• Optimal orthonormalization of the strapdown matrix by using singular value decomposition
• Computing the Polar Decomposition—with Applications
• Linear model reduction and solution of the algebraic Riccati equation by use of the sign function†
• A Divide-and-Conquer Algorithm for the Bidiagonal SVD
• A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
• Using the Matrix Sign Function to Compute Invariant Subspaces
• Procrustes Problems
• Templates for the Solution of Algebraic Eigenvalue Problems
• Empirical Arithmetic Averaging Over the Compact Stiefel Manifold
• Orthogonal Eigenvectors and Relative Gaps
• The matrix sign function
• Is the Polar Decomposition Finitely Computable?
• Restructuring the Tridiagonal and Bidiagonal QR Algorithms for Performance
• A High Performance QDWH-SVD Solver Using Hardware Accelerators
• Functions of Matrices
• ZOLOTAREV PROBLEMS CONNECTED WITH RATIONAL FUNCTIONS
• Best Rational Starting Approximations and Improved Newton Iteration for the Square Root
• The geometric mean of two matrices from a computational viewpoint

This page was built for publication: Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions