Algorithmus zum Lösen von linearen Gleichungssystem ohne explizite Schreibweise der Matrix-Komponenten

Question

Ich habe eine lineare Funktion (n Eingänge -> n Ausgänge), und mit speziellen Struktur der Funktion (einige DP-ähnliche Algorithmus), kann ich die Ausgabe auswerten in O (n) Zeit, anstatt O (n^2) Zeit. Nun, bei einigen Ausgabewerten muss ich die Eingabe finden, die die Ausgabe auswertet.

Ich könnte die Matrix-Komponenten (durch Auswertung der linearen Funktion mit n Basis-Eingaben) buchstabieren und einige Algorithmen wie LU-Zerlegung verwenden, aber das würde O (n^3) Zeit zur Berechnung benötigen. Gibt es einen schnelleren Algorithmus, der die Struktur der linearen Funktion ausnutzt?

(Da die lineare Funktion nicht symmetrisch ist, könnte Conjugate Gradient Verfahren nicht verwendet werden.)

ich genaue Lösungen benötigen, wobei n klein ist (n = 10 ~ 20), aber ich brauche diese Art zu tun der Berechnung Hunderttausende von Malen in einer Sekunde.

Vom Code-Design-Standpunkt aus wäre es besser, wenn der Algorithmus keine Transponierung der linearen Funktion benötigt. (Obwohl auf Kosten von mehr Code und mehr Debugging, ist es möglich, die Transponierungsfunktion mit O (n) Zeitkomplexität bereitzustellen.)

Answer 1

Haben Sie in Betracht gezogen GMRES? Sie haben erwähnt, dass Sie nach exakten Lösungen suchen, jedoch können Sie den Fehler in der Maschinengenauigkeit relativ schnell erreichen.

Ich kann die Ausgabe in O (n) Zeit, anstatt O (n^2) Zeit auswerten.

Sie einen linearen Operator diese Vorteile nehmen können, zum Beispiel mit dem GMRES in scipy implementation kann A ein LinearOperator sein. Ein linearer Operator ist nur eine Funktion, die Ax auswertet. Dies ist der Schritt "evaluate the output".

Ansonsten, kurz vor einer Ad-hoc-Lösung, kenne ich keine genauen Methoden, die mit linearen Operatoren beschleunigt werden können, also müsste ich mehr über Ihr Problem wissen, zB ist Ihre Matrix gebändert?