Accurate Solutions of Polynomial Eigenvalue Problems
For researchers and practitioners dealing with polynomial eigenvalue problems, this method offers a more accurate and certifiable alternative to standard linearization approaches.
This paper introduces a homotopy continuation method for solving polynomial eigenvalue problems (PEP) directly without linearization, achieving substantially more accurate results and certifying correctness via Smale's α-theory. Numerical experiments show the method outperforms the QZ algorithm in accuracy and stability.
Quadratic eigenvalue problems (QEP) and more generally polynomial eigenvalue problems (PEP) are among the most common types of nonlinear eigenvalue problems. Both problems, especially the QEP, have extensive applications. A typical approach to solve QEP and PEP is to use a linearization method to reformulate the problem as a higher dimensional linear eigenvalue problem. In this article, we use homotopy continuation to solve these nonlinear eigenvalue problems without passing to higher dimensions. Our main contribution is to show that our method produces substantially more accurate results, and finds all eigenvalues with a certificate of correctness via Smale's $α$-theory. To explain the superior accuracy, we show that the nonlinear eigenvalue problem we solve is better conditioned than its reformulated linear eigenvalue problem, and our homotopy continuation algorithm is more stable than QZ algorithm - theoretical findings that are borne out by our numerical experiments. Our studies provide yet another illustration of the dictum in numerical analysis that, for reasons of conditioning and stability, it is sometimes better to solve a nonlinear problem directly even when it could be transformed into a linear problem with the same solution mathematically.