计算最小奇异组的一个精化调和Lanczos双对角化方法

A REFINED HARMONIC LANCZOS DIDIAGONALIZATION FOR COMPUTING SMALLEST SINGULAR TRIPLETS

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.

In many applications, one is required to compute several smallest singular triplets of large matrices. Harmonic projection methods are commonly used to compute interior eigenpairs of large matrices, and their principle can be applied to large singular value decomposition problems. It is proved that for sufficiently good subspaces the approximate singular values obtained by the harmonic projection methods converge while the corresponding approximate singular vectors may not. Based on the refined projection principle proposed by the second author, a refined harmonic Lanczos bidiagonalization method is proposed and its convergence is proved. In combination of the implicit restarting technique due to Sorensen, an implicitly restarted harmonic Lanczos bidiagonalzation algorithm （IRHLB） and its refined version （IRRHLB） are developed. A proper selection of shifts involved is one of the keys for the success of algorithms. A new shifts scheme, called refined harmonic shifts, is proposed for use within IRRHLB. Theoretical analysis shows that the refined shifts are better than the harmonic shifts used within IRHLB and they can be computed reliably and efficiently. Numerical experiments indicate that IRRHLB is considerably superior to IRHLB and better than the commonly used implicitly restarted Lanczos bidiagonalization algorithm （IRLB） and its refined version （IRRLB）.