表演$k$GMRES使用步骤$O(n k^2)$时间和$O(n k)$记忆。换句话说，随着每次额外的迭代，算法变得越来越昂贵。理论上，算法终止于$k \le n$步骤（忽略四舍五入），从而产生最坏情况的三次$O(n^3)$时间和二次$O(n^2)$记忆图。

在实践中，我们手动终止算法后$k=O(1)$产生线性的步骤$O(n)$时间和记忆的数字。我们这样做是希望收敛足够快，$k$-th 迭代将已经满足容错。在某些特殊情况下，我们将能够证明这一点。

尽管如此，当$k$很大，成本$k$-th 迭代可能仍然太大。我们可以通过在每次之后重新启动 GMRES 来减少这种情况$p \le k$脚步。在这种情况下，算法有一个固定的$O(n p^2) = O(n)$时间和$O(n p) = O(n)$内存复杂度，与最终的迭代次数无关$k$. 然而，复杂性的降低是有代价的：重新启动的 GMRES（可证明）收敛速度比 GMRES 慢，并且也可能停滞不前。