自适应分块Lanczos方法

算法 7.14在P^{\ast}_{j+1} Q_{j+1}为奇异时会失效。此外，由于计算的Lanczos向量Q_{[j]}和P_{[j]}之间双正交性的丧失，或者块大小小于所需特征值群集的大小，计算的Ritz三元组可能收敛缓慢。ABLE试图通过自适应地改变块大小并保持Lanczos向量的完全双正交性，即\Vert P^{\ast}_{[j]} Q_{[j]} - I \Vert \approx \epsilon_M，或半双正交性，即\Vert P^{\ast}_{[j]} Q_{[j]} - I \Vert \approx \sqrt{\epsilon_M}，来避免失效并消除这些导致缓慢收敛的原因。

算法 7.15是ABLE的伪代码。该方法可以通过以下逻辑参数指示的不同复杂级别执行：

fullbo

使用双侧Gram-Schmidt过程在每个Lanczos步骤中保持完全双正交性。

semibo

监控双正交性的丧失并在某些步骤中纠正这种丧失。

treatbd

通过增加块大小来治愈失效。

group

将块大小适应于收敛的Ritz值群集的阶数。

ABLE有四个实现级别：

Level 1:

所有逻辑标志均为假（F）。

这是最简单的块Lanczos算法，如算法 7.14所示。本质上，使用三项递归（7.50）和（7.51），并且不存储计算的Lanczos向量。仅计算特征值。用户指定参数tolbd以检测失效。tolbd的默认值为10n\epsilon_M，其中\epsilon_M表示机器精度。

Level 2:

fullbo = true（T），其他逻辑标志为假（F）。

此版本保持完全双正交性。通过TSMGS对三项递归计算的每对新的Lanczos向量与所有先前的Lanczos向量重新进行双正交化。对于级别\geq 2，计算特征三元组。

Level 3:

semibo = true（T），其他逻辑标志为假（F）。

此级别试图保持半双正交性。与完全双正交性相比，它在浮点运算和内存引用方面成本较低。

Level 4:

fullbo = true（T）或semibo = true（T），且treatbd = true（T）和/或group = true（T）。

此版本试图通过增加块大小和/或适应块大小至少为检测到的收敛Ritz值群集的阶数来治愈失效。用户指定参数tolbd和tolcl以声明失效和/或对Ritz值群集进行分组。tolcl和tolbd的默认值为\epsilon^{1/2}_M。

用户可以选择具有完全双正交性（Level 2）或半双正交性（Level 3）的ABLE实现，但不能同时选择两者。Level 4在Level 2或3（完全或半双正交性）之上实现。逻辑标志的默认值均为true，除了fullbo = false。

在Level 1，Ritz值收敛到A的特征值后，会在后续的Lanczos步骤中出现该Ritz值的副本。例如，缩减的三对角矩阵T_{[j]}的Ritz值群集可能近似于原始矩阵A的单个特征值。在[93]中提出了一种启发式方法来检测虚假Ritz值，并在§7.8中进行了讨论。在ABLE的更高级别中不预期这种现象。

算法 7.15：NHEP的ABLE方法

(1)  选择 n \times p 起始块 P_1 和 Q_1，使得 P_1^* Q_1 = I
(2)  R = A Q_1
(3)  S = A^* P_1
(4)  对于 j = 1, 2, \ldots, j_{\max} 直到收敛，
(5)      A_j = P_j^* R
(6)      R := R - Q_j A_j
(7)      S := S - P_j A_j^*
(8)      QR分解 R = Q_{j+1} C_{j+1}
(9)      QR分解 S = P_{j+1} B_{j+1}^*
(10)     如果 R 或 S 秩亏并且 (fullbo = T 或 semibo = T)
(11)         重新双正交化(TSMGS)
(12)     结束如果
(13)     计算SVD：P_{j+1}^* Q_{j+1} = U_j \Sigma_j V_j^*
(14)     如果 \omega_j = \min(\mathrm{diag}(\Sigma_j)) \lt \mathrm{tolbd},
(15)         中断 := T
(16)         如果 treatbd = F，方法失败，停止
(17)     结束如果
(18)     如果 group = T 并且 (fullbo = T 或 semibo = T)，
(19)         检测已收敛Ritz值的簇
(20)     结束如果
(21)     如果 (中断 = T 并且 treatbd = T) 或 group = T
(22)         实施中断或 adapt to clusters
(23)     结束如果
(25)     C_{j+1} := \Sigma_j^{1/2} V_j^* C_{j+1}
(26)     Q_{j+1} := Q_{j+1} V_j \Sigma_j^{-1/2}
(27)     P_{j+1} := P_{j+1} U_j \Sigma_j^{-1/2}
(28)     计算 T_{[j]} 的特征三元组 \left(\theta_i^{(j)}, z_i^{(j)}, w_i^{(j)}\right)
(29)     测试收敛性
(30)     如果 fullbo = T
(31)         保持完全双正交性
(32)     否则如果 semibo = T，
(33)         监控正交性损失并在必要时纠正
(34)     结束如果
(35)     R = A Q_{j+1}
(36)     S = A^* P_{j+1}
(37)     R := R - Q_j B_{j+1}
(39) 结束循环
(40) 计算近似特征向量 x_i^{(j)} 和 y_i^{(j)}

我们现在对算法 7.15的某些步骤进行评论：

(1)

算法 7.14的步骤(1)的评论也适用于此处。

(2), (3), (35), (36)

算法 7.14的步骤(2), (3)和(20), (21)的评论同样适用于此处。

(6), (7)

在步骤(7)之后，可以插入以下步骤以保持块向量Q_{j}和P_{j}的局部双正交性： R:=R-Q_j(P^{\ast}_jR)
S:=S-P_j(Q^{\ast}_jS)

(10)

如果R或S秩亏，则Q_{j+1}和P_{j+1}在先前的Lanczos向量Q_{[j]}和P_{[j]}上进行就地双正交化，使用TSMGS。

(14)

如果P^{\ast}_{j+1} Q_{j+1}的最小奇异值小于规定的容差值tolbd，则失效标志被切换。\delta_d表示小于tolbd的奇异值的数量。如果发生失效且用户未指定处理方法（即treatbd = false），则该方法失败。

(18)

在此步骤中确定从收敛的Ritz值\{ \theta^{(j)}_i \}中最大群集值的阶数\delta_c。两个Ritz值\theta^{(j)}_i和\theta^{(j)}_k被视为群集，如果\vert\theta^{(j)}_i - \theta^{(j)}_k\vert \leq {\tt tolcl} \cdot \vert\theta^{(j)}_i\vert，其中tolcl是用户规定的容差。

(21)

如果发生失效或收敛的Ritz值群集的阶数超过当前块大小\delta_c > p_j，则可以增加Q_{j+1}和P_{j+1}：

Q_{j+1} := \begin{bmatrix}{Q_{j+1}} & {\widehat{Q}}\end{bmatrix}, \quad P_{j+1} := \begin{bmatrix}{P_{j+1}}&{\widehat{P}}\end{bmatrix},

使得P^{\ast}_{j+1} Q_{j+1}在数值上非奇异，其中\widehat{Q}和\widehat{P}是n \times \delta，\delta由\delta = \min ( \max( \delta_c, \delta_d ), p_{\max} - p_j )确定，其中p_j是参数前的块大小，p_{\max}是规定的最大块大小。新的块大小为p_j+\delta。然后调用TSMGS对Q_{j+1}和P_{j+1}与存储在Q_{[j]}和P_{[j]}中的先前Lanczos向量进行双正交化。这就是所谓的自适应分块方案。

没有已知的方法可以选择保证将P^{\ast}_{j+1} Q_{j+1}的最小奇异值提升到tolbd以上的\widehat{Q}和\widehat{P}，除非在tolbd = 0的情况下，即精确失效。可以选择\widehat{Q}和\widehat{P}为随机向量。

(28), (29)

如果保持半双正交性，我们在每次重新双正交化后解T_{[j]}的特征问题。

公式（7.56）和（7.57）可用于检测收敛。由于我们期望在Level 1的Lanczos迭代中步骤过多，我们使用以下收敛测试：

\min\{ \Vert r^{(j)}_i\Vert, \Vert(s^{(j)}_i)^{\ast}\Vert \} \leq\mathrm{\tt tolconv} \cdot \Vert A\Vert _1,

在更高级别中，我们可能使用半二次收敛测试：

\min\left\{ \Vert r^{(j)}_i\Vert, \Vert(s^{(j)}_i)^{\ast}\Vert, \eta_{i}^{(j)} \right\}\leq \mathrm{\tt tolconv} \cdot \Vert A\Vert _1,

其中

\eta^{(j)}_i = \frac{ \Vert r^{(j)}_i\Vert\; \Vert(s^{(j)}_i)^{\ast}\Vert _2}{{\rm gap}(\theta^{(j)}_i,T_{[j]})};

\mathrm{gap}(\theta^{(j)}_i, T_{[j]})定义\theta^{(j)}_i与其他Ritz值之间的间隙。具体地，{\rm gap}(\theta^{(j)}_i,T_{[j]})=\min_{k \ne i} \vert \theta^{(j)}_i - \theta^{(j)}_k\vert。在分块情况下，间隙定义在群集之间。

在[29]中表明，在温和条件下，对于Ritz值\theta^{(j)}_i，存在A的特征值，使得\vert \lambda - \theta^{(j)}_i \vert与条件数和量\eta^{(j)}_i的乘积成比例。然而，对于病态问题（即大条件数），小残差（后向误差）并不意味着高特征值精度（小前向误差）。在这种情况下，上述半二次收敛准则过于乐观。无论如何，可以使用右和左特征向量来近似特征值条件数。这检测了特征值问题的病态性（见§7.13）。

(30)

如果需要完全双正交性（Level 2），只需使用TSMGS过程（见(10)）对Q_{j+1}和P_{j+1}与存储在Q_{[j]}和P_{[j]}中的所有先前Lanczos向量进行双正交化。如果需要半双正交性（Level 3），则监控双正交性的丧失，并在必要时调用TSMGS以保持半双正交性。

(j+1)st Lanczos向量Q_{j+1}和P_{j+1}与先前Lanczos向量的双正交性由量d_{j+1}衡量：

d_{j+1} = \max \left\{ \frac{\Vert P_{[j]}^{\ast}Q_{j+1} \Vert_1}{\Vert P_{[j]}\Vert_1 \Vert Q_{j+1}\Vert_1}, \frac{\Vert Q^*_{[j]}P_{j+1}\Vert_1}{\Vert Q_{[j]}\Vert _1 \Vert P_{j+1}\Vert _1 } \right\}.

在[29]中开发了一种高效的过程，以O(n)成本有效模拟此量。

(40)

算法 7.14的步骤(25)的评论也适用于此处。