很难击败这两种幼稚的方法，迭代平方和重复应用从右关联$A(A(A(\cdots Av)))$. 两者哪个更好取决于$k$，稀疏性等，如评论中所述。

如果您对近似值没问题，可能还有其他选择；例如，您可以：

(1) 将您的问题视为一般问题$f(A)v$， 在哪里$f$是一个标量函数。这开辟了一些策略，例如对角化或 Schur-Parlett 方法：改变基础以减少到对角线或三角形形式 + 明确解决三角形/对角线问题。这可能便于密集$A$和巨大的$k$因为它的复杂性不取决于$k$（除了计算$k$标量的 th 次方，通常可以在恒定时间内完成）。或稀疏的 Arnoldi 方法$A$，它同样对指数有非常温和的依赖性$k$. 这些在 Higham 的书Functions of matrices中得到处理。

(2) 近似$A$排名-$r$矩阵$UV^T$，例如使用随机方法，然后使用$(UV^T)^{k} = U(V^TU)^{k-1}V^T$, 这让你拥有 a 的权力$r\times r$矩阵而不是$n\times n$一。例如，在流行的评论文章https://arxiv.org/abs/2002.01387中概述了这种随机近似的技术（双关语） 。请注意，上面建议的 Arnoldi 方法本质上也是一个等级-$r$以特殊方式计算的近似值。