隐式重启

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分解，

A V_m = V_m T_m + r_m e_m^\ast, \tag{4.20}

被压缩为一个保留感兴趣特征信息的 k 长度的分解。这是通过应用 p 个隐式移位QR步完成的。移位过程的第一阶段结果是

A V_m^+ = V_m^+ T_m^+ + r_m e_m^\ast Q, \tag{4.21}

其中 V_m^+ = V_m Q， T_m^+ = Q^{\ast} T_m Q，以及 Q = Q_1Q_2 \cdots Q_p。每个 Q_j 是与移位QR算法中使用的移位 \mu_j 相关的正交矩阵。由于矩阵 Q_j 的海森堡结构，向量 e_m^{\ast} Q 的前 k-1 个元素为零。这意味着方程 (4.21) 中的前 k 列保持在Lanczos关系中。将 (4.21) 两边的第一个 k 列等式化，提供了更新的 k 步Lanczos分解

A V_k^+ = V_k^+ T_k^+ + r_k^+ e_k^{\ast},

具有更新形式的残差 r_k^+ = V_m^+ e_{k+1} \beta_k + r_m Q(m,k)。以此为起点，可以应用 p 个额外的Lanczos步骤返回到原始的 m 步形式。

隐式重启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 中给出。