Complexity of path-following methods for the eigenvalue problem
From MaRDI portal
approximate zerobasin of attractioncomplexitycondition metriccondition number theoremeigenvalue problemhomotopy methodill-posed problemmultihomogeneous polynomial systemsNewton methodpath-following methodpredictor-corrector strategySmale \(\gamma\)-theorem
General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Complexity and performance of numerical algorithms (65Y20)
Abstract: A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale's -Theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.
Recommendations
- Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
- A note on the homotopy method for linear algebraic eigenvalue problems
- A stable, polynomial-time algorithm for the eigenpair problem
- Homotopy determinant algorithm with multi-initial zeros for solving eigenvalue problems
- Homotopy Method for the Large, Sparse, Real Nonsymmetric Eigenvalue Problem
Cites work
- A continuation method to solve polynomial systems and its complexity
- A simple application of the homotopy method to symmetric eigenvalue problems
- Adaptive step-size selection for homotopy methods to solve polynomial equations
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Convexity properties of the condition number
- Convexity Properties of the Condition Number II
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Fixed points, zeros and Newton's method
- Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
- Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
- Homotopy Method for the Large, Sparse, Real Nonsymmetric Eigenvalue Problem
- How long does it take to compute the eigenvalues of a random symmetric matrix?
- scientific article; zbMATH DE number 3859276 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3554399 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1069614 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Matrix algorithms. Vol. 2: Eigensystems
- Multihomogeneous Newton methods
- Note on matrices with a very ill-conditioned eigenproblem
- Numerical Solution of a Class of Deficient Polynomial Systems
- On a problem posed by Steve Smale
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Rayleigh quotient iteration fails for nonsymmetric matrices
- Rayleigh Quotient Iteration for Nonsymmetric Matrices
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- Smale's fundamental theorem of algebra reconsidered
- Some open problems in random matrix theory and the theory of integrable systems
- The complexity and geometry of numerically solving polynomial systems
- The Matrix Eigenvalue Problem
- The Probability That a Numerical Analysis Problem is Difficult
Cited in
(6)- A randomized homotopy for the Hermitian eigenpair problem
- A primal-dual formulation for certifiable computations in Schubert calculus
- scientific article; zbMATH DE number 3986546 (Why is no real title available?)
- Path-Following Method to Determine the Field of Values of a Matrix with High Accuracy
- Probabilistic analyses of condition numbers
- Branch points of homotopies: distribution and probability of failure
This page was built for publication: Complexity of path-following methods for the eigenvalue problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404275)
