This paper develops a new class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized sketching to accelerate subspace projection methods, such as GMRES and Rayleigh--Ritz. This approach offers great flexibility in designing the basis for the approximation subspace, which can improve scalability in many computational environments. The resulting algorithms outperform the classic methods with minimal loss of accuracy. For model problems, numerical experiments show large advantages over MATLAB's optimized routines, including a $100 \times$ speedup over gmres and a $10 \times$ speedup over eigs.
翻译:本文为普通线性系统和电子价值问题开发了一种新的算法类别。 这些算法应用快速随机绘图来加速子空间投影方法, 如 GMRES 和 Rayleigh- Ritz 。 这种方法在设计近似子空间的基础时提供了极大的灵活性, 这可以改善许多计算环境中的可缩放性。 结果的算法比经典方法的精确度低得多。 对于模型问题, 数字实验显示比 MATLAB 优化的例行程序有很大的优势, 包括100 美元的速度超过 gmres 和 10 美元的速度超过 eig 。