Complexity of path-following methods for the eigenvalue problem

DOI10.1007/s10208-013-9185-5zbMath1302.65085arXiv1108.2828OpenAlexW2016553765MaRDI QIDQ404275

Diego Armentano

Publication date: 4 September 2014

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

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

zbMATH Keywords

complexityeigenvalue problembasin of attractionhomotopy methodNewton methodill-posed problemapproximate zerocondition metricpath-following methodcondition number theoremmultihomogeneous polynomial systemspredictor-corrector strategySmale \(\gamma\)-theorem

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20)

Related Items

A primal-dual formulation for certifiable computations in Schubert calculus, Probabilistic analyses of condition numbers, A randomized homotopy for the Hermitian eigenpair problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smale's fundamental theorem of algebra reconsidered
• A continuation method to solve polynomial systems and its complexity
• On a problem posed by Steve Smale
• A simple application of the homotopy method to symmetric eigenvalue problems
• Fixed points, zeros and Newton's method
• Rayleigh quotient iteration fails for nonsymmetric matrices
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Complexity of Bezout's theorem. V: Polynomial time
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Note on matrices with a very ill-conditioned eigenproblem
• Matrix Algorithms
• Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze
• Numerical Solution of a Class of Deficient Polynomial Systems
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Rayleigh Quotient Iteration for Nonsymmetric Matrices
• Some open problems in random matrix theory and the theory of integrable systems
• Convexity Properties of the Condition Number
• The Probability That a Numerical Analysis Problem is Difficult
• Complexity of Bezout's Theorem I: Geometric Aspects
• Homotopy Method for the Large, Sparse, Real Nonsymmetric Eigenvalue Problem
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Convexity Properties of the Condition Number II
• Adaptive step-size selection for homotopy methods to solve polynomial equations
• Multihomogeneous Newton methods
• Fast computation of zeros of polynomial systems with bounded degree under finite-precision
• The Matrix Eigenvalue Problem
• The complexity and geometry of numerically solving polynomial systems.