Die Matrixexponentiation wird zu langsam

Question

Ich versuche gerade, die Matrixexponentiation zu berechnen, und verwende dafür den bekannten Algorithmus der Exponentiation durch Quadrieren.

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))

Das Problem ist, dass mein Algorithmus immer noch zu langsam ist, und nach einigen Recherchen fand ich heraus, dass die Zeit der Matrixmultiplikation entgegen meiner Meinung von der Matrixgröße und den Zahlen in der Matrix abhängt .

Tatsächlich werden die Zahlen in meiner Matrix sehr groß, so dass die Multiplikation nach einiger Zeit viel langsamer wird. Normalerweise habe ich M, eine 13 * 13-Matrix, die mit Zufall 1 und 0 gefüllt ist, und ich möchte M ^{(10 8 )} berechnen . Die ganzen Zahlen in der Matrix können Hunderte von Ziffern haben. Ich würde gerne wissen, ob es einen Weg gibt, dieses Problem zu vermeiden.

Ich habe gesehen, dass ich Matrixdiagonalisierung verwenden könnte, aber das Problem ist, dass ich keine externen Bibliotheken (wie Numpy) verwenden kann. Der Diagonalisierungsalgorithmus scheint also etwas zu kompliziert.

Answer 1

Die Zeit der Matrixmultiplikation hängt von der Matrixgröße und den Zahlen in der Matrix ab.

Natürlich multiplizieren Sie ganze Zahlen beliebiger Größe. CPUs unterstützen keine Multiplikation dieser CPUs, daher ist sie sehr langsam und wird langsamer, wenn die ganzen Zahlen wachsen.

Die ganzen Zahlen in der Matrix können Hunderte von Ziffern haben. Ich würde gerne wissen, ob es einen Weg gibt, dieses Problem zu vermeiden.

Es gibt verschiedene Möglichkeiten:

• Vermeiden Sie Ganzzahlen, verwenden Sie Gleitkommazahlen und behandeln Sie den Fehler, wie es Ihr Projekt benötigt. Dies erhöht die Geschwindigkeit erheblich und hängt vor allem nicht mehr von der Größe der Zahlen ab. Die Speichernutzung wird ebenfalls stark abnehmen.

• Use a better algorithm. You already suggested this one, but this is one of the best ways to increase performance if the better algorithm gives you way better bounds.

• Optimize it in a low-level systems language. This can give you some performance back, around an order of magnitude or so. Python is a very bad choice for high-performance computing unless you use specialized libraries that do the work for you like numpy.

Ideally, you should be doing all 3 if you actually need the performance.