Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time

DOI10.1007/s10208-022-09577-5zbMath1530.65039arXiv1912.08805OpenAlexW2995471005WikidataQ114228255 ScholiaQ114228255MaRDI QIDQ6142334

Jess Banks, Archit Kulkarni, Jorge Garza Vargas, Nikhil Srivastava

Publication date: 21 December 2023

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityrandom matrix theorylinear algebranumerical analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extreme gaps between eigenvalues of random matrices
• Random matrices: tail bounds for gaps between eigenvalues
• Perturbation bounds for the Cholesky and QR factorizations
• Fast matrix multiplication is stable
• The beta-Jacobi matrix model, the CS decomposition, and generalized singular value problems
• On condition numbers and the distance to the nearest ill-posed problem
• On estimating the condition of eigenvalues and eigenvectors
• Condition numbers of random matrices
• A computational method for eigenvalues and eigenvectors of a matrix with real eigenvalues
• The matrix sign function and computations in systems
• Parallel algorithm for solving some spectral problems of linear algebra
• The matrix sign decomposition and its relation to the polar decomposition
• An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems
• Brown's spectral distribution measure for \(R\)-diagonal elements in finite von Neumann algebras
• A stable, polynomial-time algorithm for the eigenpair problem
• On the Lambert \(w\) function
• A new similarity transformation method for eigenvalues and eigenvectors
• Random regularization of Brown spectral measure
• Fast linear algebra is stable
• The shifted QR algorithm for Hermitian matrices
• Global convergence of tridiagonal QR algorithm with origin shifts
• The complexity of the matrix eigenproblem
• Smallest eigenvalue distributions for two classes of β-Jacobi ensembles
• Backward Stability of Iterations for Computing the Polar Decomposition
• Matrix regularizing effects of Gaussian perturbations
• Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
• Random matrix theory
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Approximate Diagonalization
• Smoothed analysis of algorithms
• A New Scaling for Newton's Iteration for the Polar Decomposition and its Backward Stability
• On the efficiency of algorithms of analysis
• The Probability That a Numerical Analysis Problem is Difficult
• Eigenvalues and Condition Numbers of Random Matrices
• Linear model reduction and solution of the algebraic Riccati equation by use of the sign function†
• A New Proof of Global Convergence for the Tridiagonal $QL$ Algorithm
• The Matrix Sign Function Method and the Computation of Invariant Subspaces
• Using the Matrix Sign Function to Compute Invariant Subspaces
• Accuracy and Stability of Numerical Algorithms
• The matrix sign function
• COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• First-Order Perturbation Theory for Eigenvalues and Eigenvectors
• Functions of Matrices
• Numerical inverting of matrices of high order

This page was built for publication: Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time