Chebyshev-Filtered Randomized Low-rank Preconditioners for Symmetric Positive Definite Linear Systems

53/2026

Chebyshev-Filtered Randomized Low-rank Preconditioners for Symmetric Positive Definite Linear Systems

Tuesday 23rd June 2026

Dong Z., Jiang Y., Ng M., Ciaramella G., Yin J.

Preconditioning is essential for accelerating Krylov methods for large symmet- ric positive definite (SPD) linear systems, especially when a small number of extremal eigenvalues deteriorate the convergence of preconditioned conjugate gradient (PCG) method. In this work, we propose a Chebyshev-filtered randomized low-rank preconditioning framework for SPD systems that targets spectral outliers at both ends of the spectrum of the coefficient matrices. The main idea is to use Chebyshev polynomial filtering to make the near-null eigenspace accessible to randomized subspace extraction. The filter amplifies the lower-tail eigencomponents that often govern PCG convergence, while randomized sketching recovers the amplified subspace using only a small number of matrix-matrix products. The resulting low-rank correction therefore targets small-eigenvalue components that are usually missed by standard randomized subspace extraction methods. The resulting preconditioner is algebraic and admits an efficient low-rank representation. We provide subspace error bounds for the filtered randomized extraction and derive condition-number estimates for the proposed preconditioning tech- niques. Numerical experiments demonstrate that the proposed method improves PCG convergence, especially when small eigenvalues are the main obstruction.

This report, or a modified version of it, has been also submitted to, or published on
Articolo appena sottomesso.