预处理

对于像GMRES或CGS这样的迭代求解器，结合方程（4.50）进行预处理，其复杂度仅比单向量情况（参见第4.7.1节）稍高。假设我们有一个可用的左预处理器{K}，用于操作符A-\theta_j^{(m)}I。令\widetilde{Q}表示矩阵\widetilde{X}_{k-1}扩展后，将{u}_j^{(m)}作为其第k列。在这种情况下，预处理器{K}必须限制在与\widetilde{Q}正交的子空间内，这意味着我们需要在这个子空间内有效工作，即

\widetilde{K} \equiv (I-\widetilde{Q}\widetilde{Q}^\ast){K}(I-\widetilde{Q}\widetilde{Q}^\ast) .

类似于单向量情况，这一过程可以出乎意料地高效实现。

假设我们使用一个初始猜测{t}_0=0的Krylov求解器，并通过左预处理来近似求解修正方程（4.50）。由于起始向量位于与\widetilde{Q}正交的子空间内，Krylov求解器的所有迭代向量都将处于该空间内。在这个子空间内，我们需要计算向量{z} \equiv\widetilde{K}^{-1}\widetilde{A}{v}，其中向量{v}由Krylov求解器提供，并且

\widetilde{A}\equiv(I-\widetilde{Q}\widetilde{Q}^\ast)(A-\theta_j^{(m)} I)(I-\widetilde{Q}\widetilde{Q}^\ast).

这一计算分两步进行。首先我们计算

\widetilde{A}{v} =(I-\widetilde{Q}\widetilde{Q}^\ast) (A-\theta^{(m)}_j I)(I-\widetilde{Q}\widetilde{Q}^\ast){v} =(I-\widetilde{Q}\widetilde{Q}^\ast){y}

其中y \equiv (A-\theta_j^{(m)} I){v}，因为\widetilde{Q}^\ast {v}=0。然后，通过左预处理，我们解出{z}\perp \widetilde{Q}，即

\widetilde{K} {z}=(I-\widetilde{Q}\widetilde{Q}^\ast){y} .

由于\widetilde{Q}^\ast {z}=0，因此{z}满足{K}{z}={y}-\widetilde{Q}\vec{\alpha}或{z}={K}^{-1}{y} - {K}^{-1}\widetilde{Q}\vec{\alpha}。条件\widetilde{Q}^\ast {z}=0导致

\vec{\alpha}=(\widetilde{Q}^\ast {K}^{-1}\widetilde{Q})^{-1}\widetilde{Q}^\ast {K}^{-1}{y} .

向量\widehat{y}\equiv {K}^{-1}{y}从{K}\widehat{y}={y}中解出，同样地，{\widehat{Q}}\equiv{K}^{-1}\widetilde{Q}从{K}{\widehat{Q}}=\widetilde{Q}中解出。注意，最后一组方程在迭代过程中只需解一次，因此对于{i}_S次线性求解器迭代，实际上需要{i}_S+{k}次预处理器操作。同时注意，在Krylov求解器的迭代中，左预处理操作符的矩阵向量乘法仅需一次\widetilde{Q}^\ast和{K}^{-1}\widetilde{Q}操作，而非四次投影操作符(I-\widetilde{Q}\widetilde{Q}^\ast)的操作。这在算法4.18给出的解决方案模板中有详细阐述。如果操作符{K}在多次连续特征值计算中保持不变，可以实现明显的节省（详细信息参见[412]）。