Optimal Krylov on Average

Abstract.

We propose an adaptive randomized truncation estimator for Krylov subspace methods that optimizes the trade-off between the solution variance and the computational cost while remaining unbiased. The estimator solves a constrained optimization problem to compute the truncation probabilities on the fly with minimal computational overhead. The problem has a closed-form solution when the improvement of the deterministic algorithm satisfies a diminishing returns property. We prove that obtaining the optimal adaptive truncation distribution is impossible in the general case. Without the diminishing return condition, our estimator provides a suboptimal but still unbiased solution. We present experimental results in Gaussian process (GP) hyperparameter training and competitive physics-informed neural networks problems to demonstrate the effectiveness of our approach.

Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/RockyL7/AdaptivelySubsampledKrylov.jl and in the supplementary materials ( AdaptivelySubsampledKrylov_jl-master.zip [14.5KB]). [Formula: see text]