Random Walks, Faber Polynomials and Accelerated Power Methods

2025/10/28 by Cowal, Peter, Marshall, Nicholas F., Pollock, Sara
#65F15 #68Q87 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2510.24608

Abstract

In this paper, we construct families of polynomials defined by recurrence relations related to mean-zero random walks. We show these families of polynomials can be used to approximate zⁿ by a polynomial of degree ∼ √(n) in associated radially convex domains in the complex plane. Moreover, we show that the constructed families of polynomials have a useful rapid growth property and a connection to Faber polynomials. Applications to iterative linear algebra are presented, including the development of arbitrary-order dynamic momentum power iteration methods suitable for classes of non-symmetric matrices.

Citations

• Faber polynomials in a deltoid region and power iteration momentum methods
• Dynamically accelerating the power iteration with momentum
• Extrapolating the Arnoldi Algorithm To Improve Eigenvector Convergence
• A simple extrapolation method for clustered eigenvalues
• Accelerated Stochastic Power Iteration
• Inexact Arnoldi residual estimates and decay properties for functions of\n non-Hermitian matrices
• The university of Florida sparse matrix collection

Related

• Faber polynomials in a deltoid region and power iteration momentum methods
• On Smale's 17th problem over the reals
• Pseudorandom Numbers and Hash Functions from Iterations of Multivariate Polynomials
• Finding polynomial roots by dynamical systems -- a case study
• Polynomials associated to non-convex bodies