计算成本与权衡

这种隐式方案的成本为p，而不是显式方案所需的k+p次矩阵-向量乘积，以应用相同的p次多项式并重建k步的Arnoldi分解。当操作w \leftarrow Av相对昂贵时，这种节省可能相当可观。然而，存在一些权衡。通常无法预测k和p的最佳值。矩阵A的谱分布对收敛行为有很大影响。两个具有完全相同稀疏模式的矩阵，对于给定的k和p选择，可能表现出完全不同的收敛特性。因此，仅基于每次迭代的操作计数来得出结论可能会产生误导。尽管如此，了解迭代的主要成本有助于指导初始选择。

在下文中，我们假设矩阵-向量乘积w \leftarrow Av的成本为\gamma n。对于稀疏矩阵，可以将\gamma视为A每行非零元素平均数量的两倍。对于稠密矩阵，\gamma = 2 n，而对于FFT矩阵，\gamma \approx \log(n)。参见第§10.2节。对于固定的k和p值，IRAM一次迭代的成本（以浮点运算次数计）为：

1. 矩阵-向量乘积w \leftarrow Av：\gamma p n；

2. Arnoldi步骤（从k扩展到k+p）：[(4k-2)p + 2p^2]n；

3. 正交化修正：每次修正大约为4(k+p)n。最坏情况估计为[(4k-2)p + 2p^2]n（假设每个新Arnoldi向量进行一次修正）；

4. 隐式重启：2 n(k^2 + kp) + O( (k+p)^3)；

5. 总成本：\gamma p n + 2[(5k-2)p + 2p^2]n + 2k^2n + O( (k+p)^3)。

注意，第二项中的系数2是由于正交化修正的最坏情况场景。在实践中，这个系数通常约为1.5。如果矩阵-向量乘积Av成本较低（即\gamma相当小），那么隐式重启的成本就变得显著，应考虑其他替代方案。其中之一可能是使用多项式谱变换。这将涉及用\psi(A)的适当构造的多项式函数代替A进行操作。例如，可以使用旨在抑制不必要谱部分的Chebyshev多项式。当然，操作w \leftarrow \psi(A)将作为涉及A的一系列矩阵-向量乘积来应用。