TRPL+K: Thick-Restart Preconditioned Lanczos+K Method for Large Symmetric Eigenvalue Problems
TRPL+K: Thick-Restart Preconditioned Lanczos+K Method for Large Symmetric Eigenvalue Problems
复制标题
DOI：
10.1137/17m1157568
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Lingfei Wu;Fei Xue;A. Stathopoulos
中科院分区：
文献类型：
--
作者：
Lingfei Wu;Fei Xue;A. Stathopoulos
Lanczos方法是计算大型稀疏对称矩阵的几个特征对的标准方法之一。它通常与重新启动一起使用，以避免内存和计算需求的无限增长。厚重启Lanczos是一个流行的重新启动的变种，因为它的简单性和数值鲁棒性。然而，高度聚集的特征值的收敛速度可能会很慢，因此需要更有效的重新启动技术和预处理的使用。在本文中，我们提出了一个厚重启预处理Lanczos方法，TRPL+K，结合了局部最优重启（+K）和预处理技术的权力与厚重启Lanczos方法的效率。TRPL+K采用内外方案，其中内部循环在预处理算子上应用Lanczos，而外部循环用来自先前重新开始循环的某些向量来增加所得到的Lanczos子空间，以获得特征向量近似，从而厚重新开始外部子空间。我们首先确定了文献中各种相关方法的差异。然后，基于优化的角度来看，我们证明了一个简化的TRPL+K方法相比，一个unrestarted全局最优方法的渐近全局拟最优性。最后，我们提出了大量的实验表明，TRPL+K无论是优于或匹配其他国家的最先进的特征方法在矩阵向量乘法和计算时间。
The Lanczos method is one of the standard approaches for computing a few eigenpairs of a large, sparse, symmetric matrix. It is typically used with restarting to avoid unbounded growth of memory and computational requirements. Thick-restart Lanczos is a popular restarted variant because of its simplicity and numerically robustness. However, convergence can be slow for highly clustered eigenvalues so more effective restarting techniques and the use of preconditioning is needed. In this paper, we present a thick-restart preconditioned Lanczos method, TRPL+K, that combines the power of locally optimal restarting (+K) and preconditioning techniques with the efficiency of the thick-restart Lanczos method. TRPL+K employs an inner-outer scheme where the inner loop applies Lanczos on a preconditioned operator while the outer loop augments the resulting Lanczos subspace with certain vectors from the previous restart cycle to obtain eigenvector approximations with which it thick restarts the outer subspace. We first identify the differences from various relevant methods in the literature. Then, based on an optimization perspective, we show an asymptotic global quasi-optimality of a simplified TRPL+K method compared to an unrestarted global optimal method. Finally, we present extensive experiments showing that TRPL+K either outperforms or matches other state-of-the-art eigenmethods in both matrix-vector multiplications and computational time.