algorithm - 计算 2x2 矩阵幂的最快方法

Question

我有一个 2x2 矩阵 M，它通常很复杂。将 M 与自身相乘 n 次的最快方法是什么，即 M^n？我可以想到两种方法:

一个。将其对角化并相乘

B.将 n 分成几组。例如，如果 n=15，那么我可以执行以下操作:

1. A=M*M
2. B=A*A=M^4
3. C=B*B=A^8
4. MAB*C=M^15

所以我总共需要做 6 次矩阵乘法。

我的问题是:

1. 哪种方法更快？

2. 还有其他方法可以实现吗？

3. 对于我的第二种方法，如何实现任意n的算法？如果 n 是 2 的幂，这很容易，但是当它不是如何像我给出的示例那样分解乘法和分组时？

Answer 1

1. 我认为 A 更好，因为在 A 中，对角化矩阵后它的复杂度为 O(1)，而在 B 中复杂度为 O(log(n))

2. 除了微不足道的(将矩阵本身乘以 n 次)之外，我什么都不知道。

1. 您应该将 n 表示为二进制数，并且只乘以“1”的位置。例如:15=1111 (bin) 所以你有:2^0,2^1,2^2,2^3，因此你需要将以上所有内容相乘才能得到答案。让我们再取一个 n，比如 n=23。二进制表示是 10111，所以你需要直到 5 的幂 (2^0,2^1,2^2,2^3,2^4) - 你只取“1”的位置 - 所以你乘以2^0*2^1*2^2*2^4(因为第 4 个索引，指的是 2^3 是 0 你不乘它)。