Speicherung der Koeffizientenmatrix

Speicherung der Koeffizientenmatrix

Bei iterativen Methoden (Gesamtschritt-, Einzelschrittverfahren) treten bei der Berechnung keine neuen Nichtnull-Elemente auf. Die Koeffizientenmatrix

wird im Verlauf der Rechnung nicht verändert. Hier läßt sich vorteilhaft eine nichtverkettete Datenstruktur verwenden. m ist dabei die Anzahl der Zeilen-/Spaltenvertauschungen.

Eine Koeffizienten-Matrix mit

und einer Besetzungsdichte mit Nichtnull-Elementen von

% benötigt bei konventioneller Speichertechnik

Speicherplätze, obwohl nur

Nichtnull-Elemente vorhanden sind.

Nichtverkettete Listen (ARRAYS) benötigen im allgemeinen weniger Speicherplatz als die direkte Speicherung verketteter Strukturen. Man wendet diese Speichertechnik an, um Zugriffe auf langsame Hintergrundspeicher zu vermeiden.

Bei schwach besetzten Matrizen speichere man möglichst nur Nichtnull-Elemente

(i = Zeile,

Spalte). Dies geschieht bei einer Matrix mit n Nichtnullementen in PASCAL oft als Record (Verbund):

      VAR A: ARRAY[1..n]
            OF RECORD
                Zeile:  INTEGER;
                Spalte: INTEGER;
                Wert:   REAL
               END;

Der Zugriff auf das i-te Nichtnullelment geschieht durch

      Zeilenindex  := A[i].Zeile
      Spaltenindex := A[i].Spalte
      Matrixelement:= A[i].Wert

In FORTRAN gibt es diese sehr übersichtliche Möglichkeit nicht. Dort müssen zwei ARRAYS definiert werden: Das eine enthält die Nichtnullelemente und das andere die Indizes.

Aufbau der Datenstruktur:

ist eine -Matrix mit sieben Nichtnull-Elementen

Im Speicher steht dann:

Das Speicherende ist hier durch gekennzeichnet.

Der Speicherbedarf läßt sich weiter verringern, wenn jeder neue Spalten- oder Zeilenindex nur einmal gespeichert wird.