隐式重启

Lanczos过程的一个不幸方面是，无法预先确定需要多少步才能在指定精度内确定感兴趣的特征值。这取决于特征值 $\lambda(A)$ 的分布和初始向量 $v_1$ 的选择。在很多情况下，收敛不会发生，直到 $k$ 变得非常大。保持 $V_k$ 的数值正交性对于大的 $k$ 很快变得难以处理，其代价是 $O(nk^2)$ 次浮点运算。

另一种保持正交性的方法是限制基集的大小并使用重启方案。重启意味着用一个“改进的”初始向量 $v_1^+$ 替换初始向量 $v_1$，并使用新向量重新计算Lanczos分解。残差向量 $r_k$ 的结构起到了指导作用：理论上，如果 $v_1$ 是 $A$ 的 $k$ 个特征向量的线性组合，$r_k$ 将消失。我们的目标是迭代地实现这一点。在对称情况下，这些特征向量是正交的，因此构成了一个不变子空间的标准正交基。

重启的需求早在Karush [258] 和Lanczos [285] 的原始算法出现后不久就被认识到了。随后，Paige [347]、Cullum和Donath [89]，以及Golub和Underwood [197] 都有所发展。所有这些方案都是显式的，即通过某种过程产生一个新的初始向量，并构建一个全新的Lanczos分解。

在本节中，我们将描述隐式重启。这是一种将隐式移位QR方案与 $k$ 步Lanczos分解相结合的技术，以获得隐式移位QR迭代的截断形式。避免了与Lanczos过程相关的数值困难和存储问题。该算法能够计算出具有用户指定特征的少数（$k$ 个）特征值，例如代数最大或最小特征值或幅度最大的特征值，仅使用 $k$ 个向量的适度倍数的存储空间。计算出的特征向量构成了所需 $k$ 维特征空间的基础，并且在工作精度上数值正交。

隐式重启提供了一种从大型Krylov子空间中提取有趣信息的方法，同时避免了与标准方法相关的存储和数值困难。它通过不断将有趣的信息压缩到一个固定大小的 $k$ 维子空间中来实现这一点。这是通过隐式移位QR机制完成的。一个长度为 $m = k+p$ 的Lanczos分解，

隐式重启Lanczos方法（IRLM）的模板在算法 4.7 中给出。

算法 4.7 HEP的隐式重启Lanczos方法（IRLM）
(1)  取初始猜测向量 $v$，归一化 $v_1 = v/\Vert v\Vert_2$
(2)  计算 $m$-步Lanczos分解 $AV_m = V_mT_m + r_me^\ast_m$
(3)  repeat until 收敛（$T_k=D_k$ 对角化）
(4)      计算谱 $\sigma(T_m)$，选择 $p$ 个位移 $\mu_1, \mu_2, \dots, \mu_p$
(5)      初始化 $Q = I_m$
(6)      for j = 1,2,...,p,
(7)          QR分解 $Q_jR_j = T_m - \mu_j I$
(8)          更新 $T_m = Q_j^\ast T_m Q_j, Q = QQ_j$
(9)      end for
(10)     $r_k = v_{k+1}\beta_k + r_m \sigma_k$, 其中 $\beta_k = T(k+1,k)$ 及 $\sigma_k = Q(m, k)$
(11)     $V_k = V_m Q(:, 1:k)$; $T_k = T_m(1:k, 1:k)$
(12)     以如下 $k$ 步Lanczos分解开始
             $AV_k = V_kT_k+r_k e^\ast_k$,
        在进行 $p$ 步Lanczos迭代后，得到新的 $m$ 步Lanczos分解
             $AV_m = V_mT_m+r_m e^\ast_m$
(13) end repeat

现在我们将描述一些实现细节，参考算法 4.7 中的相应阶段。

(1)

理想情况下，对于特征值计算，应尝试构建一个在感兴趣的特征向量方向上占主导地位的初始向量 $v$。如果有一系列密切相关的特征值问题，前一个问题的解可能为下一个问题提供初始向量。在没有其他考虑的情况下，随机向量是一个合理的选择。

(2)

下面的算法 4.8 可以用来计算这个初始的 $(m = k+p)$ 步Lanczos分解。

(4)

移位 $\mu_j$ 是根据用户的“所需集”规范以及 $T_m$ 的谱的当前和可能过去的信息选择的；参见第4.5.2节。

(6)-(9)

使用 $\mu_1, \mu_2, \ldots, \mu_p$ 作为移位，对 $T_m$ 应用 $p$ 步移位QR迭代。这应该使用隐式移位QR变体（即“凸起追踪”机制）来完成。如果使用精确移位，则在完成 $p$ 步QR后，$\beta_{k} = T_m(k+1,k)$ 应为零，并且前导子矩阵 $T_m(1:k,1:k)$ 应具有 $\theta_1, \theta_2, \ldots, \theta_k$ 作为其特征值。

(10)

当使用精确移位时，步骤 (6)-(9) 中提到的属性通常在有限精度下近似为真。然而，由于舍入误差，它们可能无法实现。因此，在更新残差向量时包含两个项是很重要的 $r_k \leftarrow v_{k+1}\beta_{k} + r_m \sigma_k$。请注意，使用精确移位，更新后的 $V_k$ 和 $T_k$ 将提供一个新的 $k$ 步Lanczos分解，其Ritz值和向量是目前为止对用户规范的最佳近似。

(12)

这一步需要对之前讨论的Lanczos过程进行轻微修改。它从通常方案的第 $k$ 步开始，并假设所有 $k$ 个Lanczos向量都已保留在一个矩阵 $V_k$ 中。详细信息在下面的算法 4.8 中给出。