计算成本与权衡

隐式方案需要进行p次矩阵-向量乘积，而不是显式方案所需的k+p次，后者在应用相同p次多项式并重建k步Lanczos分解时需要这些乘积。当操作r = Av相对昂贵时，这种节省可能相当可观。然而，存在一些权衡。通常无法预测额外向量数量p的最佳值。

收敛行为在很大程度上取决于A的谱分布。两个具有完全相同稀疏模式的矩阵，对于给定的k和p选择，可能表现出截然不同的收敛特性。因此，仅根据每次迭代的操作计数得出结论可能会产生误导。尽管如此，了解迭代的主要成本有助于指导初始选择。

在下文中，我们假设矩阵-向量乘积r = Av的成本为\gamma n。对于稀疏矩阵，可以将\gamma视为A每行非零条目平均数量的两倍。对于稠密矩阵，\gamma = 2 n，而对于快速傅里叶变换（FFT）矩阵，\gamma \approx \log_2(n)。参见第10.2节。对于固定的k和p值，IRLM一次迭代的成本（以浮点运算次数计）为：

• 矩阵-向量乘积r = Av：\gamma p n；
• 基本Lanczos步骤：9 pn；
• 正交化校正：每次校正大约4(k+p)n。最坏情况估计为每次IRLM迭代4(kp + p^2)n（假设每个新Lanczos向量进行一次校正）；
• 隐式重启：2 n(k^2 + kp) + O((k+p)^3)；
• 总成本：\gamma p n + (6k + 9)pn + 4p^2 n + 2k^2n + O((k+p)^3)。

如果矩阵-向量乘积Av的成本较低（即\gamma相当小），隐式重启的成本就显得显著，应考虑其他替代方案。其中之一可能是使用多项式谱变换。这将涉及用\psi(A)的适当约束多项式函数代替A进行操作。例如，可以使用旨在抑制谱中不希望部分的切比雪夫多项式。操作r = \psi(A)v当然会通过涉及A的一系列矩阵-向量乘积来应用。