矩阵功率和

Question

计算矩阵之和的最佳方法是什么,例如A ^ i + A ^(i + 1)+ A ^ i + 2 ........ A ^ n用于非常大的n？

我想到了两种可能的方法:

1)对A ^ i使用对数矩阵求幂(LME),然后乘以A计算后续矩阵.

问题:没有真正利用LME算法,因为我只使用它来获得最低功耗!!

2)使用LME查找A ^ n并记忆中间计算.

问题:大n需要太多空间.

还有第三种方式吗？

Answer 1

请注意:

A + A^2 = A(I + A)
A + A^2 + A^3 = A(I + A) + A^3
A + A^2 + A^3 + A^4 = (A + A^2)(I + A^2)
                    = A(I + A)(I + A^2)

让

B(n) = A + ... + A^n

我们有:

B(1) = A
B(n) = B(n / 2) * (I + A^(n / 2)) if n is even
B(n) = B(n / 2) * (I + A^(n / 2)) + A^n if n is odd

因此,您将执行对数步数,而无需计算反转.

虽然直接实施将导致一个(log n)^2因素,你可以把它log n通过计算的力量A为你计算B.