实现跨迭代并行化的迭代算法的并行版本通常非常困难，如果不是不可能的话。一次迭代的完成是一个自然的序列点。如果一种算法需要更少的迭代但每次迭代的工作量更多，那么该算法更有可能可以有效地并行实现。

这方面的一个例子是线性规划，其中原始对偶障碍（内点）方法通常只使用几十次迭代，即使是非常大的问题，但每次迭代的工作量非常大。相比之下，单纯形法的各种版本通常需要更多的迭代，但每次迭代的工作量更少。在实践中，内点方法的并行实现已经显示出比单纯形方法的并行实现更好的并行效率。

我可以想到一些可能性：

如果两种算法都单调地减少每次迭代的误差，那么对于某些算法来说，拥有更多、更便宜的迭代可能比某些算法更可取，因为它为您提供了更多关于何时停止迭代的选择。

如果$\mathcal{A}_1$是$O(n)$工作和时间但是$O(n^k)$内存，你可能更喜欢$\mathcal{A}_2$如果$k$很大。$k=2$甚至可能大到足以让您选择$\mathcal{A}_2$因为内存使用更有可能将您限制在这里。

无论我们谈论的是优化还是任何其他类型的迭代问题，这都可能适用。