Complexity of path-following methods for the eigenvalue problem
From MaRDI portal
complexityeigenvalue problembasin of attractionill-posed problemNewton methodcondition metricpath-following methodhomotopy methodapproximate zerocondition number theoremmultihomogeneous polynomial systemspredictor-corrector strategySmale \(\gamma\)-theorem
General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)
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
- 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?)
- 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. 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
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Convexity Properties of the Condition Number II
- Convexity properties of the condition number
- 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 the Large, Sparse, Real Nonsymmetric Eigenvalue Problem
- Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
- How long does it take to compute the eigenvalues of a random symmetric matrix?
- 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 for Nonsymmetric Matrices
- Rayleigh quotient iteration fails 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 Matrix Eigenvalue Problem
- The Probability That a Numerical Analysis Problem is Difficult
- The complexity and geometry of numerically solving polynomial systems
Cited in
(5)- Path-Following Method to Determine the Field of Values of a Matrix with High Accuracy
- A primal-dual formulation for certifiable computations in Schubert calculus
- Probabilistic analyses of condition numbers
- scientific article; zbMATH DE number 3986546 (Why is no real title available?)
- A randomized homotopy for the Hermitian eigenpair problem
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)
