Random Walks, Faber Polynomials and Accelerated Power Methods

Nicholas F. Marshall; Peter Cowal; Sara Pollock

arxiv: 2510.24608 · v3 · submitted 2025-10-28 · 🧮 math.NA · cs.NA

Random Walks, Faber Polynomials and Accelerated Power Methods

Peter Cowal , Nicholas F. Marshall , Sara Pollock This is my paper

Pith reviewed 2026-05-18 02:56 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords random walksFaber polynomialspower methodspolynomial approximationnon-symmetric matricesmomentum iterationradially convex domainsrecurrence relations

0 comments

The pith

Families of polynomials from mean-zero random walks approximate z^n by a polynomial of degree roughly the square root of n inside radially convex domains.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines families of polynomials via recurrence relations that track the position of a mean-zero random walk. It establishes that these polynomials can replace the monomial z^n with one whose degree scales like the square root of n, uniformly on domains that remain convex under radial scaling from the origin. The same families exhibit rapid growth outside those domains and relate directly to Faber polynomials. The construction supplies concrete acceleration techniques for power iteration on non-symmetric matrices, including methods whose momentum order can be set arbitrarily. A sympathetic reader would care because the approach ties a probabilistic recurrence to both approximation theory and practical linear-algebra iteration without requiring prior spectral data.

Core claim

The authors construct polynomial families by recurrence relations associated to mean-zero random walks and prove that, for radially convex domains in the complex plane, a member of degree approximately sqrt(n) approximates z^n with controlled error; the same families possess a rapid growth property outside the domain and coincide with or relate to the Faber polynomials of the domain, which in turn yields arbitrary-order dynamic momentum power iteration schemes for classes of non-symmetric matrices.

What carries the argument

Polynomial families generated by recurrence relations tied to mean-zero random walks, which produce the low-degree approximation to z^n and the rapid growth property.

Load-bearing premise

The domains of approximation must be radially convex and the underlying random walks must have strictly zero mean.

What would settle it

For a radially convex domain and a mean-zero random walk, compute the smallest degree m such that the corresponding polynomial approximates z^n to within a fixed relative error; if m grows faster than order sqrt(n) for large n, the central approximation claim fails.

Figures

Figures reproduced from arXiv: 2510.24608 by Nicholas F. Marshall, Peter Cowal, Sara Pollock.

**Figure 1.** Figure 1: The curve (13) for p = ( 7 12 , 0, 3 12 , 2 12 ), ( 2 3 , 0, 0, 1 3 ), and ( 5 8 , 0, 2 8 , 0, 1 8 ) (ordered left to right). 1.4.2. Hypocycloids. In the special case where p0 and pm are the only non-zero entries of the probability vector p = (p0, . . . , pm), for m ≥ 2, the condition (7) implies p0 = m − 1 m and pm = 1 m . We denote the family of polynomials corresponding to these probabilities as P (m) n… view at source ↗

**Figure 2.** Figure 2: The curve (13) for p = ( 2 3 , 0, 1 3 ), ( 3 4 , 0, 0, 1 4 ), and ( 4 5 , 0, 0, 0, 1 5 ) (ordered left to right). These curves are called a 3- cusped hypocycloid (deltoid), a 4-cusped hypocycloid (astroid), and a 5-cusped hypocycloid, respectively. Remark 1.2. In the remainder, we will make the assumption that p1 = 0. As can be observed from (6), this parameter serves essentially as a “shift,” and its [PI… view at source ↗

**Figure 3.** Figure 3: P (m) n (1+ε) for ε = 10−5 for n ∈ {1, . . . , 1000} and m ∈ {2, 3, 4, 5}, along with the rates predicted by Theorem 1.2, where P (m) n is the hypocycloid polynomial defined in (16) and associated with the hypocycloid curves illustrated in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: As a consequence of Theorem 1.4, if a polynomial is bounded on the deltoid region, then rapid growth in the sense of (5) is possible at 1 but impossible at −1/3, since there is an ellipse contained in the deltoid region tangent to this point. 2. Momentum accelerated power iterations In this section, we generalize the algorithm presented in [1] to the polynomial family Pk given by (6)-(7) with p1 = 0. This … view at source ↗

**Figure 5.** Figure 5: Left: convergence of hypocycloid momentum methods for varying degrees of hypocycloid for the toy example. Right: convergence of the dynamic momentum method with various probability distributions. 2.4.2. Barbell example. We construct a random directed barbell graph with 2N vertices, separated into two halves of N vertices with a single edge bridging both halves. Within each half of the graph, we randomly … view at source ↗

**Figure 6.** Figure 6: Left: the 100 largest eigenvalues (marked with a cross) of the barbell adjacency matrix (N = 1000, p = 1/250), alongside hypocycloids of degrees 3, 4, 5, 6. Right: convergence of the dynamic momentum method applied to the barbell problem. 2.4.3. Application to large sparse matrices. To test Algorithm 3 on larger examples, we generate a larger barbell adjacency matrix (N = 16000, p = 1/4000) with a simila… view at source ↗

**Figure 7.** Figure 7: Left: convergence of the dynamic momentum method applied to a larger barbell matrix (N = 16000, p = 1/4000). Right: convergence of the dynamic momentum method applied to the matrix windtunnel evap 3d from [5]. The probability parameters are given in [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗

**Figure 8.** Figure 8: Left to right: we plot (28) for p = ( 2 3 , 0, 0, 1 3 ), p = ( 5 6 , 0, 0, 0, 0, 0, 1 6 ), p = ( 9 12 , , 0, 0, 1 6 , 0, 0, 1 12 ). By Lemma 3.1 these curves have 3, 6, and 3 = gcd(3, 6) cusps, respectively [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗

read the original 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^n$ by a polynomial of degree $\sim \sqrt{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Mean-zero random walk recurrences produce sqrt(n)-degree polynomial approximations to z^n on radially convex domains, with a Faber connection and arbitrary-order momentum for non-symmetric power iteration.

read the letter

Hi, the main takeaway is that the authors define polynomial families through recurrences drawn from mean-zero random walks, prove these can approximate z^n to good accuracy with degree only about sqrt(n) inside associated radially convex regions of the complex plane, establish a link to Faber polynomials plus a rapid-growth property outside the region, and then turn the growth into dynamic momentum terms of arbitrary order for power methods on non-symmetric matrices. The specific route from the walk recurrences to the sqrt(n) rate and the Faber identification, followed by the momentum extension, is the fresh piece; it is not a direct restatement of the earlier literature referenced in the abstract. The construction itself is presented cleanly and the rapid-growth claim is a natural fit for accelerating iterations without symmetry. The applications section sketches how the same polynomials can be reused inside power iteration, which keeps the work grounded in a concrete computational setting. The soft spots sit mainly in the central approximation step. The rate and the growth property both require the walks to be strictly mean-zero and the domains to be radially convex; any small drift introduces a bias term that can accumulate across the sqrt(n) steps and spoil the cancellation needed for small error, while loss of radial convexity can break the generating-function identity that connects the walk to the polynomial family. The abstract asserts proofs for the approximation and growth, yet the quantitative passage from the recurrence to an explicit uniform error bound of the stated order is the load-bearing part and will need careful verification for gaps or extra restrictions on the domains. Numerical checks comparing the new momentum scheme against existing accelerators on non-symmetric test matrices would also help show whether the theoretical gain translates to practice. This paper is aimed at numerical analysts working on polynomial methods or iterative eigensolvers. A reader who already follows Faber polynomials or accelerated power methods will get the most out of it. I would send the manuscript to peer review rather than desk-reject it; the construction is original enough and the claims are specific enough that referees can give useful comments on the derivations and the linear-algebra experiments.

Referee Report

2 major / 2 minor

Summary. The manuscript constructs families of polynomials defined by recurrence relations related to mean-zero random walks. It claims these families approximate z^n by a polynomial of degree ~sqrt(n) in associated radially convex domains in the complex plane, establishes a rapid growth property outside the domain, and connects the construction to Faber polynomials. Applications to iterative linear algebra are presented, including arbitrary-order dynamic momentum power iteration methods for classes of non-symmetric matrices.

Significance. If the approximation rate and growth property hold with explicit bounds, the work would provide a novel bridge between stochastic processes, complex approximation theory, and numerical linear algebra. The sublinear degree growth for power approximation could enable new acceleration strategies for power methods on non-normal matrices, while the Faber connection may yield broader tools for polynomial expansions in non-disk domains.

major comments (2)

[§3] §3 (Approximation theorem): The central claim that the mean-zero recurrence produces polynomials p_m of degree m~sqrt(n) satisfying p_m(z)≈z^n uniformly on the radially convex domain requires an explicit error bound. The manuscript states the association and the role of the mean-zero condition but does not supply the quantitative estimate controlling bias accumulation over the sqrt(n) steps; this step is load-bearing for the claimed rate.
[§5] §5 (Growth property and Faber link): The rapid-growth property outside the domain and the identification with Faber polynomials are asserted via the generating-function identity, yet the proof that radial convexity is necessary and sufficient for the identity to hold with the stated growth is not detailed; without this, the domain restriction remains formal.

minor comments (2)

[§2] The notation for the random-walk recurrence (Eq. (2.3)) could be clarified by explicitly separating the step distribution from the polynomial coefficients.
[§4] A concrete numerical example or figure illustrating a radially convex domain and the corresponding level sets would help readers verify the geometric assumptions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable suggestions. We address each of the major comments in detail below and will revise the manuscript accordingly to improve clarity and rigor.

read point-by-point responses

Referee: [§3] §3 (Approximation theorem): The central claim that the mean-zero recurrence produces polynomials p_m of degree m~sqrt(n) satisfying p_m(z)≈z^n uniformly on the radially convex domain requires an explicit error bound. The manuscript states the association and the role of the mean-zero condition but does not supply the quantitative estimate controlling bias accumulation over the sqrt(n) steps; this step is load-bearing for the claimed rate.

Authors: We agree with the referee that an explicit error bound is essential for substantiating the approximation rate. The manuscript outlines the recurrence and the mean-zero condition's role in controlling the walk, but we acknowledge the need for a quantitative estimate. In the revised version, we will add a detailed proof in §3 providing an explicit bound on the approximation error, derived from the variance of the random walk steps and the radial convexity, showing that the error is bounded by C / sqrt(n) uniformly on the domain for some constant C depending on the domain. revision: yes
Referee: [§5] §5 (Growth property and Faber link): The rapid-growth property outside the domain and the identification with Faber polynomials are asserted via the generating-function identity, yet the proof that radial convexity is necessary and sufficient for the identity to hold with the stated growth is not detailed; without this, the domain restriction remains formal.

Authors: We appreciate this observation. The generating-function identity is used to link the polynomials to Faber polynomials and establish the growth property. However, the necessity and sufficiency of radial convexity for this to hold with the rapid growth is indeed only sketched. We will revise §5 to include a complete proof demonstrating that radial convexity is necessary and sufficient for the identity and the associated growth bound outside the domain. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation starts from external random-walk recurrences and connects to established Faber polynomials

full rationale

The paper defines polynomial families via recurrence relations built from mean-zero random walks, then proves approximation properties for z^n in radially convex domains and a link to Faber polynomials. These steps rely on external objects (random walks, radial convexity, Faber theory) rather than self-definition or fitted inputs renamed as predictions. No load-bearing claim reduces to a self-citation chain or ansatz smuggled from prior work by the same authors; the central approximation rate is derived from the recurrence properties, not presupposed by the result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the definition of mean-zero random walks and the geometric property of radial convexity; no free parameters or new entities are introduced in the abstract.

axioms (2)

domain assumption Mean-zero random walks generate recurrence relations that define polynomial families with the stated approximation and growth properties.
Invoked to construct the families and derive the approximation result.
domain assumption The target sets in the complex plane are radially convex.
Required for the degree ~sqrt(n) approximation to hold.

pith-pipeline@v0.9.0 · 5609 in / 1265 out tokens · 39230 ms · 2026-05-18T02:56:16.750583+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We construct families of polynomials defined by recurrence relations related to mean-zero random walks... Pn+1(z) = z/p0 Pn(z) - sum pj/p0 Pn+1-j(z) ... p0>0 and sum (1-j)pj=0
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

the region enclosed by gamma is radially convex... cusps located at e^{2 pi i k / n} where n=gcd({j: pj>0})
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_strictMono_of_one_lt unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.3 ... zn approximated by polynomial of degree ~sqrt(n) ... Ce^{-c t^2}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Dynami cally accelerating the power iter- ation with momentum

Christian Austin, Sara Pollock, and Yunrong Zhu. Dynami cally accelerating the power iter- ation with momentum. Numerical Linear Algebra with Applications , 31(6):e2584, 2024

work page 2024
[2]

W eighted sums of certain dependent rando m variables

Kazuoki Azuma. W eighted sums of certain dependent rando m variables. Tohoku Mathemat- ical Journal , 19(3), January 1967

work page 1967
[3]

An ad aptive Chebyshev iterative method\ newline for nonsymmetric linear systems based on modiﬁed mo ments

Daniela Calvetti, Gene H Golub, and Lothar Reichel. An ad aptive Chebyshev iterative method\ newline for nonsymmetric linear systems based on modiﬁed mo ments. Numerische Mathematik, 67:21–40, 1994

work page 1994
[4]

Fabe r polynomials in a deltoid region and power iteration momentum methods

Peter Cowal, Nicholas F Marshall, and Sara Pollock. Fabe r polynomials in a deltoid region and power iteration momentum methods. arXiv preprint arXiv:2507.01885 , 2025

work page arXiv 2025
[5]

The university of ﬂorida spa rse matrix collection

Timothy A Davis and Yifan Hu. The university of ﬂorida spa rse matrix collection. ACM Transactions on Mathematical Software (TOMS) , 38(1):1–25, 2011

work page 2011
[6]

On semiiterative methods generated b y Faber polynomials

Michael Eiermann. On semiiterative methods generated b y Faber polynomials. Numerische Mathematik, 56(2):139–156, 1989

work page 1989
[7]

On hybrid semi-iter ative methods

Michael Eiermann, X Li, and RS Varga. On hybrid semi-iter ative methods. SIAM journal on numerical analysis , 26(1):152–168, 1989

work page 1989
[8]

An introduction to diﬀerence equations

Saber Elaydi. An introduction to diﬀerence equations . Undergraduate Texts in Mathematics. Springer, New York, NY, 3 edition, March 2005

work page 2005
[9]

A ﬁltered Lanczos procedur e for extreme and interior eigen- value problems

Haw-ren Fang and Yousef Saad. A ﬁltered Lanczos procedur e for extreme and interior eigen- value problems. SIAM Journal on Scientiﬁc Computing , 34(4):A2220–A2246, 2012

work page 2012
[10]

Chebyshev polynomial s are not always optimal

Bernd Fischer and Roland Freund. Chebyshev polynomial s are not always optimal. Journal of Approximation Theory , 65(3):261–272, 1991

work page 1991
[11]

On tail probabilities for martingale s

David A Freedman. On tail probabilities for martingale s. the Annals of Probability , pages 100–118, 1975

work page 1975
[12]

An Arnoldi-type algorithm f or computing page rank

Gene H Golub and Chen Greif. An Arnoldi-type algorithm f or computing page rank. BIT Numerical Mathematics , 46:759–771, 2006

work page 2006
[13]

Chebyshev semi-iterat ive methods, successive over- relaxation iterative methods, and second order richardson iterative methods

Gene H Golub and Richard S Varga. Chebyshev semi-iterat ive methods, successive over- relaxation iterative methods, and second order richardson iterative methods. Numerische Mathematik, 3(1):157–168, 1961

work page 1961
[14]

Methods of con jugate gradients for solving linear systems

Magnus R Hestenes, Eduard Stiefel, et al. Methods of con jugate gradients for solving linear systems. Journal of research of the National Bureau of Standards , 49(6):409–436, 1952

work page 1952
[15]

Tchebychev acceleration technique for large s cale nonsymmetric matrices

Diem Ho. Tchebychev acceleration technique for large s cale nonsymmetric matrices. Numer. Math., 56:721–734, 1989

work page 1989
[16]

Arnol di-tchebychev procedure for large scale nonsymmetric matrices

Diem Ho, Fran¸ coise Chatelin, and Maria Bennani. Arnol di-tchebychev procedure for large scale nonsymmetric matrices. ESAIM: M2AN , 24:53–65, 1990

work page 1990
[17]

The suites parse matrix collection web- site interface

Scott P Kolodziej, Mohsen Aznaveh, Matthew Bullock, Ja rrett David, Timothy A Davis, Matthew Henderson, Yifan Hu, and Read Sandstrom. The suites parse matrix collection web- site interface. Journal of Open Source Software , 4(35):1244, 2019

work page 2019
[18]

An iteration method for the solutio n of the eigenvalue problem of linear diﬀerential and integral operators

Cornelius Lanczos. An iteration method for the solutio n of the eigenvalue problem of linear diﬀerential and integral operators. Journal of research of the National Bureau of Standards , 45(4):255–282, 1950

work page 1950
[19]

The Tchebychev iteration for nonsy mmetric linear systems

Thomas A Manteuﬀel. The Tchebychev iteration for nonsy mmetric linear systems. Nu- merische Mathematik , 28:307–327, 1977

work page 1977
[20]

Approximation of monomials by l ower degree polynomials

DJ Newman and TJ Rivlin. Approximation of monomials by l ower degree polynomials. ae- quationes mathematicae , 14:451–455, 1976

work page 1976
[21]

The analysis of k-step iterative methods for linear systems from summability theory

Wilhelm Niethammer and Richard S Varga. The analysis of k-step iterative methods for linear systems from summability theory. Numerische Mathematik , 41(2):177–206, 1983

work page 1983
[22]

A simple extrapolation m ethod for clustered eigenvalues

Nilima Nigam and Sara Pollock. A simple extrapolation m ethod for clustered eigenvalues. Numerical Algorithms, pages 1–29, 2022. RANDOM W ALKS, F ABER POLYNOMIALS, POWER METHODS 31

work page 2022
[23]

Extrapolating the Arn oldi algorithm to improve eigenvec- tor convergence

Sara Pollock and L Ridgway Scott. Extrapolating the Arn oldi algorithm to improve eigenvec- tor convergence. International Journal of Numerical Analysis and Modeling , 18(5):712–721, 2021

work page 2021
[24]

Y. Saad. Chebyshev acceleration techniques for solvin g nonsymmetric eigenvalue problems. Mathematics of Computation , 42(166):567–588, 1984)

work page 1984
[25]

Gmres: A generalized m inimal residual algorithm for solving nonsymmetric linear systems

Youcef Saad and Martin H Schultz. Gmres: A generalized m inimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientiﬁc and statistical computing , 7(3):856–869, 1986

work page 1986
[26]

Numerical methods for large eigenvalue problems: revised e dition

Yousef Saad. Numerical methods for large eigenvalue problems: revised e dition. SIAM, 2011

work page 2011
[27]

Faster alg orithms via approximation theory

Sushant Sachdeva, Nisheeth K Vishnoi, et al. Faster alg orithms via approximation theory. Foundations and Trends ® in Theoretical Computer Science , 9(2):125–210, 2014

work page 2014
[28]

A block Arnoldi-Chebyshev method for c omputing the leading eigenpairs of large sparse unsymmetric matrices

Miloud Sadkane. A block Arnoldi-Chebyshev method for c omputing the leading eigenpairs of large sparse unsymmetric matrices. Numer. Math. , 64:181–193, 1993

work page 1993
[29]

Series of Faber polynomials , volume 1

Pavel Kondratevich Suetin and EV Pankratiev. Series of Faber polynomials , volume 1. CRC Press, 1998

work page 1998
[30]

Freedman’s inequality for matrix martinga les

Joel Tropp. Freedman’s inequality for matrix martinga les. Electronic Communications in Probability, 16:262 – 270, 2011

work page 2011
[31]

Accelerated sto- chastic power iteration

Peng Xu, Bryan He, Christopher De Sa, Ioannis Mitliagka s, and Chris Re. Accelerated sto- chastic power iteration. In International Conference on Artiﬁcial Intelligence and St atistics, pages 58–67. PMLR, 2018

work page 2018
[32]

A chebyshev–davidson algo rithm for large symmetric eigen- problems

Yunkai Zhou and Yousef Saad. A chebyshev–davidson algo rithm for large symmetric eigen- problems. SIAM Journal on Matrix Analysis and Applications , 29(3):954–971, 2007. Email address : cowalp@oregonstate.edu Department of Mathematics, Oregon State University, Corval lis, OR Email address : marsnich@oregonstate.edu Department of Mathematics, Oregon State ...

work page 2007

[1] [1]

Dynami cally accelerating the power iter- ation with momentum

Christian Austin, Sara Pollock, and Yunrong Zhu. Dynami cally accelerating the power iter- ation with momentum. Numerical Linear Algebra with Applications , 31(6):e2584, 2024

work page 2024

[2] [2]

W eighted sums of certain dependent rando m variables

Kazuoki Azuma. W eighted sums of certain dependent rando m variables. Tohoku Mathemat- ical Journal , 19(3), January 1967

work page 1967

[3] [3]

An ad aptive Chebyshev iterative method\ newline for nonsymmetric linear systems based on modiﬁed mo ments

Daniela Calvetti, Gene H Golub, and Lothar Reichel. An ad aptive Chebyshev iterative method\ newline for nonsymmetric linear systems based on modiﬁed mo ments. Numerische Mathematik, 67:21–40, 1994

work page 1994

[4] [4]

Fabe r polynomials in a deltoid region and power iteration momentum methods

Peter Cowal, Nicholas F Marshall, and Sara Pollock. Fabe r polynomials in a deltoid region and power iteration momentum methods. arXiv preprint arXiv:2507.01885 , 2025

work page arXiv 2025

[5] [5]

The university of ﬂorida spa rse matrix collection

Timothy A Davis and Yifan Hu. The university of ﬂorida spa rse matrix collection. ACM Transactions on Mathematical Software (TOMS) , 38(1):1–25, 2011

work page 2011

[6] [6]

On semiiterative methods generated b y Faber polynomials

Michael Eiermann. On semiiterative methods generated b y Faber polynomials. Numerische Mathematik, 56(2):139–156, 1989

work page 1989

[7] [7]

On hybrid semi-iter ative methods

Michael Eiermann, X Li, and RS Varga. On hybrid semi-iter ative methods. SIAM journal on numerical analysis , 26(1):152–168, 1989

work page 1989

[8] [8]

An introduction to diﬀerence equations

Saber Elaydi. An introduction to diﬀerence equations . Undergraduate Texts in Mathematics. Springer, New York, NY, 3 edition, March 2005

work page 2005

[9] [9]

A ﬁltered Lanczos procedur e for extreme and interior eigen- value problems

Haw-ren Fang and Yousef Saad. A ﬁltered Lanczos procedur e for extreme and interior eigen- value problems. SIAM Journal on Scientiﬁc Computing , 34(4):A2220–A2246, 2012

work page 2012

[10] [10]

Chebyshev polynomial s are not always optimal

Bernd Fischer and Roland Freund. Chebyshev polynomial s are not always optimal. Journal of Approximation Theory , 65(3):261–272, 1991

work page 1991

[11] [11]

On tail probabilities for martingale s

David A Freedman. On tail probabilities for martingale s. the Annals of Probability , pages 100–118, 1975

work page 1975

[12] [12]

An Arnoldi-type algorithm f or computing page rank

Gene H Golub and Chen Greif. An Arnoldi-type algorithm f or computing page rank. BIT Numerical Mathematics , 46:759–771, 2006

work page 2006

[13] [13]

Chebyshev semi-iterat ive methods, successive over- relaxation iterative methods, and second order richardson iterative methods

Gene H Golub and Richard S Varga. Chebyshev semi-iterat ive methods, successive over- relaxation iterative methods, and second order richardson iterative methods. Numerische Mathematik, 3(1):157–168, 1961

work page 1961

[14] [14]

Methods of con jugate gradients for solving linear systems

Magnus R Hestenes, Eduard Stiefel, et al. Methods of con jugate gradients for solving linear systems. Journal of research of the National Bureau of Standards , 49(6):409–436, 1952

work page 1952

[15] [15]

Tchebychev acceleration technique for large s cale nonsymmetric matrices

Diem Ho. Tchebychev acceleration technique for large s cale nonsymmetric matrices. Numer. Math., 56:721–734, 1989

work page 1989

[16] [16]

Arnol di-tchebychev procedure for large scale nonsymmetric matrices

Diem Ho, Fran¸ coise Chatelin, and Maria Bennani. Arnol di-tchebychev procedure for large scale nonsymmetric matrices. ESAIM: M2AN , 24:53–65, 1990

work page 1990

[17] [17]

The suites parse matrix collection web- site interface

Scott P Kolodziej, Mohsen Aznaveh, Matthew Bullock, Ja rrett David, Timothy A Davis, Matthew Henderson, Yifan Hu, and Read Sandstrom. The suites parse matrix collection web- site interface. Journal of Open Source Software , 4(35):1244, 2019

work page 2019

[18] [18]

An iteration method for the solutio n of the eigenvalue problem of linear diﬀerential and integral operators

Cornelius Lanczos. An iteration method for the solutio n of the eigenvalue problem of linear diﬀerential and integral operators. Journal of research of the National Bureau of Standards , 45(4):255–282, 1950

work page 1950

[19] [19]

The Tchebychev iteration for nonsy mmetric linear systems

Thomas A Manteuﬀel. The Tchebychev iteration for nonsy mmetric linear systems. Nu- merische Mathematik , 28:307–327, 1977

work page 1977

[20] [20]

Approximation of monomials by l ower degree polynomials

DJ Newman and TJ Rivlin. Approximation of monomials by l ower degree polynomials. ae- quationes mathematicae , 14:451–455, 1976

work page 1976

[21] [21]

The analysis of k-step iterative methods for linear systems from summability theory

Wilhelm Niethammer and Richard S Varga. The analysis of k-step iterative methods for linear systems from summability theory. Numerische Mathematik , 41(2):177–206, 1983

work page 1983

[22] [22]

A simple extrapolation m ethod for clustered eigenvalues

Nilima Nigam and Sara Pollock. A simple extrapolation m ethod for clustered eigenvalues. Numerical Algorithms, pages 1–29, 2022. RANDOM W ALKS, F ABER POLYNOMIALS, POWER METHODS 31

work page 2022

[23] [23]

Extrapolating the Arn oldi algorithm to improve eigenvec- tor convergence

Sara Pollock and L Ridgway Scott. Extrapolating the Arn oldi algorithm to improve eigenvec- tor convergence. International Journal of Numerical Analysis and Modeling , 18(5):712–721, 2021

work page 2021

[24] [24]

Y. Saad. Chebyshev acceleration techniques for solvin g nonsymmetric eigenvalue problems. Mathematics of Computation , 42(166):567–588, 1984)

work page 1984

[25] [25]

Gmres: A generalized m inimal residual algorithm for solving nonsymmetric linear systems

Youcef Saad and Martin H Schultz. Gmres: A generalized m inimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientiﬁc and statistical computing , 7(3):856–869, 1986

work page 1986

[26] [26]

Numerical methods for large eigenvalue problems: revised e dition

Yousef Saad. Numerical methods for large eigenvalue problems: revised e dition. SIAM, 2011

work page 2011

[27] [27]

Faster alg orithms via approximation theory

Sushant Sachdeva, Nisheeth K Vishnoi, et al. Faster alg orithms via approximation theory. Foundations and Trends ® in Theoretical Computer Science , 9(2):125–210, 2014

work page 2014

[28] [28]

A block Arnoldi-Chebyshev method for c omputing the leading eigenpairs of large sparse unsymmetric matrices

Miloud Sadkane. A block Arnoldi-Chebyshev method for c omputing the leading eigenpairs of large sparse unsymmetric matrices. Numer. Math. , 64:181–193, 1993

work page 1993

[29] [29]

Series of Faber polynomials , volume 1

Pavel Kondratevich Suetin and EV Pankratiev. Series of Faber polynomials , volume 1. CRC Press, 1998

work page 1998

[30] [30]

Freedman’s inequality for matrix martinga les

Joel Tropp. Freedman’s inequality for matrix martinga les. Electronic Communications in Probability, 16:262 – 270, 2011

work page 2011

[31] [31]

Accelerated sto- chastic power iteration

Peng Xu, Bryan He, Christopher De Sa, Ioannis Mitliagka s, and Chris Re. Accelerated sto- chastic power iteration. In International Conference on Artiﬁcial Intelligence and St atistics, pages 58–67. PMLR, 2018

work page 2018

[32] [32]

A chebyshev–davidson algo rithm for large symmetric eigen- problems

Yunkai Zhou and Yousef Saad. A chebyshev–davidson algo rithm for large symmetric eigen- problems. SIAM Journal on Matrix Analysis and Applications , 29(3):954–971, 2007. Email address : cowalp@oregonstate.edu Department of Mathematics, Oregon State University, Corval lis, OR Email address : marsnich@oregonstate.edu Department of Mathematics, Oregon State ...

work page 2007