Some Results and Questions as to the Complexity of the (Eigenvalue, Eigenvector) Problem
summary
Proposes a homotopy continuation method that tracks all eigenpairs and proves with probability one it finds approximate zeros in Smale sense for Gaussian random A, using Newton continuation and a condition number mu defined as mu(a,λ,v) = ||(P_{v⊥}(λI−A)|_{v⊥})^{-1}||. Shows average mu^2 on the unit sphere is O(n^3) with a lower bound about n√2, argues practical predictors should use the tangent (long steps), and lists open problems: minimizing summed mu^2 and bounding average curvature of solution curves.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:25Steve Smale’s journey
- 3:30Algebra and complexity
- 8:47Eigenvalue eigenvector problem
- 12:00Gaussian elimination limits
- 14:52Eigenvalue algorithm challenges
- 17:42Condition numbers compared
- 20:14Haystack problem overview
- 23:00Algorithm pitfalls
- 26:07Open problems in curvature
- 28:10Q&A on QR convergence