Introduction
The Power Method is a cornerstone of numerical linear algebra, used to find the dominant eigenvalue of a matrix. However, its efficiency is heavily dependent on the "spectral gap"—the ratio between the largest and second-largest eigenvalues. When this gap is small, convergence slows to a crawl. While Chebyshev acceleration effectively addresses this for symmetric matrices with real eigenvalues, non-symmetric matrices with complex spectra present a greater challenge. This paper introduces a novel acceleration technique using polynomials derived from mean-zero random walks, which leverage the unique properties of cusped regions in the complex plane to achieve superior growth rates.
Methods and Theoretical Framework
The authors bridge probability and linear algebra by constructing a family of polynomials, $P_n(z)$, whose coefficients are linked to the probabilities of an integer-valued random walk. These are shown to be a class of Faber polynomials, which are particularly well-suited for approximating functions on complex domains.
Hypocycloid Domains and the Power of Cusps
Unlike standard Chebyshev acceleration, which uses smooth elliptical boundaries, these new polynomials are bounded on hypocycloids—regions characterized by sharp "cusps" (e.g., the 3-cusped deltoid or 4-cusped astroid).
A key theoretical insight is that polynomials bounded on regions with cusps can grow significantly faster outside those regions than those bounded on smooth domains. This "rapid growth" property is the engine behind the proposed acceleration. By using higher-order recurrences (3rd, 4th, or 5th order), the resulting algorithms can effectively "wrap" their stability regions around complex subdominant eigenvalues, preventing them from hindering convergence.
Key Results
The effectiveness of these random-walk-based polynomials was validated through both theoretical proofs and empirical tests on diverse datasets, including barbell graphs and large-scale sparse matrices from the SuiteSparse collection (e.g., windtunnel_evap_3d).
Convergence and Growth Rates
The authors prove that their polynomials achieve a growth rate of $O((1 + \sigma^{-1}\sqrt{2\epsilon})^N)$, where $\sigma$ is the standard deviation of the underlying random walk. This theoretical advantage is clearly visible when comparing the growth of different polynomial orders.
In practical tests, such as the "Barbell" graph scenario, the dynamic version of the algorithm (which adaptively estimates the spectral gap) reached a relative error of $10^{-12}$ in approximately 600 iterations. In contrast, standard power methods and lower-order momentum techniques remained stalled at significantly higher error levels.
Conclusion and Future Directions
This work demonstrates that moving beyond second-order momentum and smooth stability regions can unlock significant performance gains for non-symmetric eigenvalue problems. While the current framework assumes a real dominant eigenvalue, it opens the door for future research into complex dominant modes and the application of these polynomials to other iterative solvers like GMRES or BiCGStab.
Summary updated