Probabilistically Certified Randomized Krylov Recycling for Many-Query Parametric PDE Systems

Abstract

Many-query parametric partial differential equation workflows require repeated solutions of large sparse linear systems together with a reliable stopping statement for every query. Recent literature has developed reduced Krylov bases, randomized/sketched Krylov methods, recycling and deflation, and probabilistic model certification, but these components remain insufficiently integrated in one online solver. This paper proposes Probabilistically Certified Randomized Krylov Recycling (PCR-KR). The method warm-starts each query, constructs a local POD recycle space from recently certified solution corrections, applies a sketched coarse correction with an acceptance gate, and performs restarted sketched minimal-residual iterations. Correctness is separated from acceleration through a fresh independent Gaussian validation sketch. Under a subspace-embedding event, the sketched step is quasi-optimal and the recycle gate implies a true-residual bound. Independently, a one-sided chi-square certificate provides an upper residual bound; allocating a total failure budget over all planned queries and checks gives a familywise guarantee, and a stability lower bound converts it to a PDE state-error certificate. Fixed-seed convection–diffusion–reaction experiments cover 120 systems with 400–1600 unknowns. All queries converged with 100% observed certificate coverage. Relative to cold-start GMRES, PCR-KR reduced mean matrix–vector products by 23.36%–33.52%; it improved on warm-start GMRES in three of four principal cases. Mean residual-certificate effectivity was 1.84–1.93, with a maximum below 2.43. Deterministic recycling remained 7.53%–11.89% cheaper in matrix–vector products, quantifying the price of randomization and certification.