A new MOX Report entitled “Chebyshev-Filtered Randomized Low-rank Preconditioners for Symmetric Positive Definite Linear Systems” by Dong Z., Jiang Y., Ng M., Ciaramella G., Yin J. has appeared in the MOX Report Collection.
Check it out here: https://www.mate.polimi.it/biblioteca/add/qmox/53-2026.pdf
Abstract: 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 resu! lting pre conditioner 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.
