重启块Arnoldi约化

在§7.6节中，我们阐述并解释了如何隐式地重启Arnoldi方法。 实验结果[292,290,24]表明，隐式重启方案优于文献中出现的其他块方法[391,398]。这些显式重启技术根据某种准则选择后续的起始块，然后从头开始重启。BIRAM不仅大幅减少了矩阵-向量乘积的使用，还显著减少了需要存储的Arnoldi向量数量。读者可参考[391,227,245,398]了解更多关于显式重启Arnoldi方法的信息。

将§7.6节中的方案扩展到块Arnoldi方法中是直接的。主要区别在于需要一个保留带状海森堡形式的隐式移位QR算法。与标准隐式移位QR算法一样，通过构建并应用一系列酉矩阵，得到更新后的带状海森堡矩阵。

在QR算法中选择使用的p个移位有多种可能，包括具体的p值选择。如果移位成复共轭对，可以使用隐式双移位[198, pp. 355-358]来避免复数运算。

通常，p个移位是通过利用H_{[r+p]}中包含的谱信息来选择的。将{H}_{[m]}的特征值分块，使得

\{ \underbrace{\theta_1,\ldots,\theta_r}_{\mathrm{wanted}}\}\cup \{\underbrace{\theta_{r+1},\ldots,\theta_{m\cdot b}}_{\mathrm{unwanted}}\}. \tag{7.31}

对于非块约化，p个移位从H_{[m]}的不需要的特征值中选择，其中r=k。Sorensen[419]提出了这种精确移位策略。该策略等同于用与k个需要的特征值相关的近似Schur向量的线性组合重启后续的约化。其他有趣的策略包括Chebyshev多项式的根[383]，调和Ritz值[331,337,349,411]，Leja多项式的根[23]，最小二乘多项式的根[384]，以及精化移位[244]。特别是Leja值和谐调Ritz值已被用于估计A的内部特征值。

在算法7.12中，整数r通常在输入步骤中设为k，即所需特征值的数量。一旦进入迭代循环，r、p以及m=r+p的值可能会随每次i的值而变化。当b > 1时，我们不能将所有p=m \cdot b - k个不需要的特征值作为移位应用。这时我们面临选择哪些p个移位应用以及是否应考虑应用超过p个移位的问题。

例如，可以应用m个移位，直到一个Ritz对满足收敛容差。然后可以对Ritz对进行收缩（或锁定）。（这等同于Saad[387, p. 181]给出的收缩迭代Arnoldi算法，并在[24,398]的实现中使用。）这种方法允许我们隐式应用最大阶的多项式滤波器。（应用超过r+p个移位将需要对A应用显式多项式。）然而，随着应用更多移位，计算后续Arnoldi约化的成本增加。

在每次迭代中改变r、p（相对于k）以及使用的移位的策略将给出最佳结果。这是当前研究的主题。最近的报告[421]讨论了对称特征值问题的自适应策略。