矩阵求幂变得太慢

Question

我目前正在尝试计算矩阵求幂，为此我使用众所周知的平方求幂算法。

def mat_mul(a, b):
    n = len(a)
    c = []
    for i in range(n):
        c.append([0]*n)
        for j in range(n):
            for k in range(n) :                    
                c[i][j] += (a[i][k]*b[k][j])
    return c

def mat_pow(a, n):
    if n<=0:
        return None
    if n==1:
        return a
    if n==2:
        return mat_mul(a, a)
    t1 = mat_pow(a, n//2)
    if n%2 == 0:
        return mat_mul(t1, t1)
    return mat_mul(t1, mat_mul(a, t1))

问题是我的算法还是太慢了，经过一番研究，发现是因为与我想的相反，矩阵乘法的时间取决于矩阵大小和矩阵中的数字。

事实上，我的矩阵中的数字变得非常大，所以一段时间后，乘法变得很慢。通常，我有一个 13*13 的矩阵 M，其中随机填充 1 和 0，我想计算 M^(10⁸)。矩阵中的整数可以有数百位。我想知道是否有办法避免这个问题。

我看到我可以使用矩阵对角化，但问题是我不能使用外部库（如 numpy）。所以对角化算法似乎有点太复杂了。

Answer 1

the time of matrix multiplication depends on the matrix size and on the numbers in the matrix.

嗯，当然，您要乘以任意大小的整数。 CPU 不支持它们的乘法，所以它会很慢，并且随着整数的增长而变慢。

The integers in the matrix can have hundreds of digits. I'd like to know if there is a way to avoid that problem.

有几种方法：

避免使用整数，使用浮点数并根据项目需要处理错误。这将大大提高速度，最重要的是它不再依赖于数字的大小。内存占用也会大大减少。
使用更好的算法。你已经建议了这个，但如果更好的算法给你更好的边界，这是提高性能的最好方法之一。
用low-level系统语言对其进行优化。这可以让您恢复一些性能，大约一个数量级左右。 Python 对于 high-performance 计算来说非常是一个糟糕的选择，除非你使用专门的库来为你完成工作，比如 numpy。

理想情况下，如果您确实需要性能，则应该执行 all 3。

矩阵求幂变得太慢

Matrix exponentiation becomes too slow

python

multiplication

matrix-multiplication