Backslash, chol und linsolve

RendBremKZur Demonstration der wichtigsten direkten Lösungsverfahren, die von Matlab angeboten werden, wird hier ein Finite-Elemente-Modell erzeugt (Berechnungs-Modell der Brücke über den Nord-Ostsee-Kanal bei Rendsburg). Es ist ein System mit 4482 Unbekannten und hat die für FEM-Modelle typische dünn besetzte Koeffizientenmatrix, die symmetrisch und positiv definit ist. Dieses Modell wird auch an anderer Stelle benutzt, um die Speichervarianten "Band", "Skyline", "Sparse" und "Voll" zu demonstrieren (dort wird auch gezeigt, was eigentlich mit dem Gleichungssystem berechnet wird) und für Vergleichsrechnungen mit den von Matlab angebotenen iterativen Verfahren.

DerAlgorithmus für den Aufbau des Gleichungssystems ist für die hier anzustellenden Überlegungen nicht von Belang (für Interessenten: Matlab-Femset). Das Modell wird im nachfolgend zu sehenden Matlab-Script in der Zeile 3 von einer Datei gelesen, in Zeile 5 wird das lineare Gleichungssystem mit einer symmetrischen Bandmatrix erzeugt. Diese wird in den Zeilen 7 und 8 in die beiden Speichformate "Sparse" bzw. "Voll" umgewandelt, die den Matlab-Functions angeboten werden können. Hier sollen zunächst nur die erforderlichen Rechnenzeiten für die verschiedenen Verfahren und Speicherformate ermittelt werden.

BackslashCholLinsolve02Vom Standard-Solver (Backslash-Operator) darf laut Matlab-Helpsystem erwartet werden, dass er die Symmetrie und positive Definitheit der Koeffizientenmatrix erkennt und ausnutzt. Mit diesem Operator wird das Gleichungssystem in Zeile 11 mit der "Sparse matrix" gelöst, in Zeile 22 mit der voll besetzten Matrix.

Die Function chol führt ausschließlich die Cholesky-Zerlegung der Matrix aus (es wird kein Gleichungssystem gelöst), deshalb muss anschließend das Vorwärts- und Rückwärtseinsetzen gesondert durchgeführt werden (hier mit dem Backslash-Operator realisiert, beide Operationen wurden in einer Zeile nacheinander aufgerufen). Auch der Function chol kann die Matrix sowohl als "Sparse matrix" (Zeile 15) als auch als voll besetzte Matrix angeboten werden (Zeile 26).

Diese Variante ist in der Programmierung für den Anwender etwas aufwendiger, und vermutlich werden in beiden Varianten die gleichen Algorithmen abgearbeitet. Aber natürlich ist die "Cholesky-Variante" für den Anwender sicherer. Es wird zwar in beiden Fällen der Test auf positive Definitheit durchgeführt, aber bei der "Backslash-Variante" erfährt der Anwender das Ergebnis dieses Tests nicht, denn bei negativem Ausgang wechselt der Backslash-Operator automatisch zu einem Verfahren, das die positive Definitheit nicht voraussetzt.

Vermutlich um genau diesen Informationsmangel des komfortablen Backslash-Operators zu heilen, wird ab Matlab 7 (R14) die Function linsolve als Alternative angeboten, die den Komfort des Backslash-Operators bietet, aber dem Anwender gestattet, über Optionen auf die Wahl des Lösungsverfahrens Einfluss zu nehmen. Dies wird in den Zeilen 33 und 34 demonstriert. In Zeile 33 werden die Optionen SYM (symmetrische Matrix) und POSDEF (positiv definite Matrix) gesetzt, die beim linsolve-Aufruf in Zeile 34 mit übergeben werden. Damit wird linsolve gezwungen, nur Lösungsverfahren zu wählen, die Symmetrie und positive Definitheit voraussetzen.

BackslashCholLinsolveCWDer nebenstehend zu sehende Schnappschuss des Command windows zeigt die Ergebnisse (mit einem Notebook mit 1,66-GHz-Prozessor, aber wichtig sind nicht die absoluten Werte, sondern die Relationen):

Backslash und linsolve

BackslashLinsolveMit dem oben demonstrierten Beispiel scheint die Strategie klar zu sein: Wenn keine Prüfung der symmetrischen Koeffizientenmatrix auf positive Definitheit (oder einer anderen Eigenschaft, linsolve kann mehr als hier demonstriert) gewünscht wird, dann verwendet man den Backslash-Operator, ansonsten linsolve.

Mit dem nebenstehenden Matlab-Script werden die beiden Möglichkeiten noch einmal gezeigt:

Zunächst wird das Gleichungssystem sowohl mit dem Backslash-Operator als auch mit linsolve (unter Übergabe der Information über die Eigenschaften der Koeffizientenmatrix) gelöst (Zeilen 10 bzw. 15).

In Zeile 18 wird nun gezielt ein Fehler in die Koeffizientenmatrix eingebaut, der ihr die Eigenschaft "positiv definit" nimmt. Danach werden noch einmal die Lösungsversuche gestartet. Der Backslash-Operator (Zeile 21) löst dieses "falsche Gleichungssystem" problemlos, denn es ist ja aus seiner Sicht nicht falsch, sondern nur anders, schließlich kann er nicht wissen, welches Problem der Anwender lösen will.

Die Function linsolve dagegen, die aufgefordert wird, ein Gleichungssystem mit positiv definiter Koeffizientenmatrix zu lösen (Zeile 26) erkennt, dass es in diesem Sinne ein falsches System ist.

BackslashLinsolveCWDas nebenstehend zu sehende Command Window zeigt die erwarteten Ergebnisse:

Damit sieht es so aus, als wäre alles, was sich der Anwender wünschen kann, verfügbar. Doch es ist noch ein wesentlicher Mangel zu beklagen:

Leider kann linsolve keine Koeffizientenmatrix verarbeiten, die im Speicherformat "Sparse" vorliegt. Damit scheidet die Function gerade für die sehr großen Gleichungssysteme, wie sie z. B. bei der Finite-Elemente-Methode anfallen, als Alternative zum Backslash aus.

Das ist schade und eigentlich auch nicht zu verstehen, denn die Algorithmen dafür sind ja in Matlab implementiert, nur eben über linsolve nicht zugänglich. Es bleibt der oben beschriebene Umweg mit der Function chol (verarbeitet auch "Sparse matrix") und dem Backslash für das Vorwärts-Rückwärtseinsetzen. Um sich dabei aber nicht wesentlich größere Rechenzeiten LinsolveErrorSparseeinzuhandeln, sollte man unbedingt die Strukturoptimierung der dünn besetzten Koeffizientenmatrix realisieren, die auf der Seite "Reduzierung von Bandweite und Fill-in" beschrieben wird.

Allerdings lässt das Wort "currently" in der Fehlerausschrift von linsolve auf die nächste Matlab-Version hoffen.

Zum Download verfügbar sind