Ich habe eine sehr große absorbierende Markov-Kette (skaliert auf Problemgröße - von 10 Zuständen bis zu Millionen), die sehr spärlich ist (die meisten Zustände können nur auf 4 oder 5 andere Zustände reagieren).

Ich muss eine Zeile der Grundmatrix dieser Kette berechnen (die durchschnittliche Häufigkeit jedes Zustands bei einem Ausgangszustand).

Normalerweise würde ich dies durch Berechnen tun(I - Q)^(-1), aber ich konnte keine gute Bibliothek finden, die einen spärlichen Matrix-Invers-Algorithmus implementiert! Ich habe ein paar Zeitungen darüber gesehen, die meisten von ihnen P.h.D. Levelarbeit.

Die meisten meiner Google-Ergebnisse verweisen auf Beiträge, in denen darüber gesprochen wird, wie man beim Lösen linearer (oder nichtlinearer) Gleichungssysteme keine inverse Matrix verwenden sollte. Das finde ich nicht besonders hilfreich. Ist die Berechnung der Grundmatrix der Lösung eines Gleichungssystems ähnlich und ich weiß einfach nicht, wie ich eines in der Form des anderen ausdrücken soll?

Ich stelle also zwei spezifische Fragen:

Was ist der beste Weg, um eine Zeile (oder alle Zeilen) der Inversen einer dünnen Matrix zu berechnen?

ODER

Wie berechnet man am besten eine Reihe der Grundmatrix einer großen absorbierenden Markov-Kette?

Eine Python-Lösung wäre wunderbar (da mein Projekt derzeit noch ein Proof-of-Concept ist), aber wenn ich mir mit einem guten alten Fortran oder C die Hände schmutzig machen muss, ist das kein Problem.

Bearbeiten: Ich habe gerade festgestellt, dass die Inverse B der Matrix A als AB = I definiert werden kann, wobei I die Identitätsmatrix ist. Das könnte mir erlauben, einige Standard-Sparse-Matrix-Löser zu verwenden, um die Inverse zu berechnen ... Ich muss los, also fühle mich frei, meinen Gedankengang zu vervollständigen, von dem ich anfange zu denken, dass er nur eine wirklich elementare Matrix erfordert Eigentum...