Effizientes Lösen numerischer Probleme mit MATLAB 6

Ernst Haunschmid, ZID
Herbert Karner, Stefan Katzenbeisser, Christoph Überhuber
Institut für Angewandte und Numerische Mathematik
{ernst,herbert,katze,christof}@aurora.anum.tuwien.ac.at

Einleitung

MATLAB 6 (Überhuber, Katzenbeisser [4]), die neue Version des Programmsystems MATLAB, bietet eine Reihe neuer und verbesserter Features: Die Effizienzsteigerungen bei der Lösung linearer Gleichungssysteme und bei der diskreten Fourier-Transformation sind das Thema dieses Artikels.

LAPACK

 LAPACK (Linear Algebra Package) [1] ist ein frei verfügbares Softwarepaket von Fortran 77-Unterprogrammen, mit deren Hilfe man viele Standardprobleme der Linearen Algebra numerisch lösen kann. Das komplette Softwareprodukt LAPACK umfasst mehr als 600 000 Zeilen Fortran-Code in über 1000 Routinen und eine Benutzungsanleitung. 1LAPACK ist für numerische Probleme der Linearen Algebra mit dicht besetzten Matrizen und Bandmatrizen der De-facto-Standard (Überhuber [3]). Um die Zuverlässigkeit und Effizienz von LAPACK mit der Benutzerfreundlichkeit und dem Komfort von MATLAB zu verbinden, wurden die wichtigsten LAPACK-Programme in MATLAB 6 einbezogen.

BLAS

Die bisherigen MATLAB-Versionen verwendeten Teile des Programmpakets LINPACK [2] zur Lösung von Aufgaben der numerischen Linearen Algebra. Sowohl LINPACK als auch LAPACK basieren auf den Basic Linear Algebra Subroutines (BLAS), einer Sammlung spezieller Unterprogramme zur Lösung elementarer Teilaufgaben der Linearen Algebra. Die Verwendung der BLAS-Programme bringt einen zweifachen Nutzen: In LINPACK waren es nur Vektor-Operationen (z. B. die Bestimmung der Norm eines Vektors oder die Berechnung des Skalarprodukts zweier Vektoren), die mit den dafür geeigneten BLAS-1-Programmen realisiert wurden. Der größte Teil der Algorithmen musste daher noch in Form von Fortran-Anweisungen implementiert werden. Erst durch das 1988 veröffentlichte BLAS-2-Softwarepaket für Matrix-Vektor-Operationen wurde es möglich, viele Algorithmen der numerischen Linearen Algebra so zu implementieren, dass ein großer Teil der Berechnungen in den BLAS-Programmen durchgeführt wird.

Um die potentielle Leistungsfähigkeit von Computern mit stark gestaffelten Speicherhierarchien in einem möglichst hohen Ausmaß nutzen zu können, ist es notwendig, Daten so oft es geht wieder zu verwenden, um möglichst wenig Daten zwischen den verschiedenen Ebenen der Speicherhierarchie transportieren zu müssen. Dieses Ziel kann nur dann erreicht werden, wenn man die Algorithmen nicht nur auf elementare Vektor- und Matrix-Vektor-Operationen, sondern auch auf elementare Matrix-Matrix-Operationen (Matrizenmultiplikationen etc.) zurückführt. Das 1990 veröffentlichte BLAS-3-Softwarepaket stellt die hierfür erforderlichen Module zur Verfügung. Die maschinenspezifische Implementierung dieser Unterprogramme kann auf modernen Computern zu noch erheblich größeren Leistungsgewinnen führen als die (ausschließliche) Verwendung optimierter BLAS-1- und BLAS-2-Programme.

In den LAPACK-Programmen werden alle rechenaufwendigen Teilalgorithmen durch Aufrufe von BLAS-1-, BLAS-2- und BLAS-3-Programmen realisiert. Maschinenabhängige, aber sehr effiziente BLAS-Implementierungen sind für die meisten modernen Hochleistungsrechner verfügbar. Die drei Gruppen der BLAS-Programme ermöglichen es, dass LAPACK-Programme einen hohen Grad an Rechenleistung und Portabilität erreichen.

In die Version 6 von MATLAB wurde LAPACK vollständig integriert. Im Gegensatz zu den LINPACK-basierten Routinen, die Bestandteil des früheren MATLAB-Source-Codes waren, wurde in Version 6 eine andere Vorgangsweise gewählt. Die LAPACK-Routinen und BLAS-Routinen sind jeweils in eigenen Dateien (als so genannte shared objects) implementiert. Dadurch ist es möglich, die mit MATLAB mitgelieferten BLAS- und LAPACK-Bibliotheken durch eigene oder systemseitig bereits vorhandene Bibliotheken zu ersetzen.

Lösung linearer Gleichungssysteme

Durch die Verwendung von LAPACK in MATLAB 6 konnte ein signifikanter Leistungsgewinn erzielt werden. Zum Vergleich wurde die Gleitpunktleistung des MATLAB-Befehls A\b mit MATLAB 5.3 und MATLAB 6 experimentell untersucht.

Die praktischen Untersuchungen wurden auf der SGI Origin2000 des ZID und auf verschiedenen PCs durchgeführt. Es wurden dabei die MATLAB-Versionen 5.3 und 6.0 beta 5 verglichen.

Abb. 1 zeigt die Gleitpunktleistung von MATLAB 5.3 und MATLAB 6 bei der Lösung linearer nichtsymmetrischer Gleichungssysteme durch Auswertung von A\b. Für größere Gleichungssysteme ist die Version 6 zwar etwa doppelt so schnell wie ihre Vorgängerversion, aber absolut gesehen ist die erreichte Leistung nicht befriedigend. Ein Fortran 77-Programm erreicht bei Verwendung optimierter, systemseitig vorhandener LAPACK- und BLAS-Bibliotheken (im Fall der Origin2000 wurde die SGI Cray Scientific Library (SCSL) verwendet), mehr als die dreifache Gleitpunktleistung von MATLAB 6.

Abb. 1

Abbildung 1: Gleitpunktleistung von A\b in MATLAB 5.3, 6 und in LAPACK.

Eine detaillierte Analyse des Problems zeigte, dass die mit MATLAB 6 mitgelieferte BLAS-Bibliothek in Bezug auf die Gleitpunktleistung nicht mit der SCSL vergleichbar ist. Die mitgelieferte BLAS-Bibliothek kann aber sehr einfach gegen die hochoptimierte SCSL ausgetauscht werden. Die damit erreichbare Gleitpunktleistung liegt nur noch geringfügig unter der eines entsprechenden Fortran-Programmes.

Bei linearen Gleichungssystemen mit symmetrischen, positiv definiten Matrizen sind die beobachtbaren Ergebnisse ähnlich. Obwohl auch hier MATLAB 6 eine deutlich bessere Gleitpunktleistung erzielt als MATLAB 5.3, können die Leistungswerte eines LAPACK-Programms erst durch das Ersetzen der in MATLAB 6 verwendeten BLAS-Bibliothek durch eine hochoptimierte Version erreicht werden (siehe Abb. 2).

Abb. 2

Abbildung 2: Gleitpunktleistung von A\b in MATLAB 5.3, 6 und in LAPACK bei symmetrischen, positiv definiten Matrizen.

Die Eigenschaften der Systemmatrix (Bandstruktur, Symmetrie, Definitheit etc.) haben einen sehr großen Einfluss auf die Rechenzeit, die zur Lösung eines linearen Gleichungssystems benötigt wird.

Bei der direkten Verwendung von LAPACK-Routinen unter Fortran muss der Programmierer dafür Sorge tragen, dass er eine den Eigenschaften der Matrix angemessene Routine auswählt. Zum Vergleich sind in Abb. 3 die normierten Laufzeiten der entsprechenden LAPACK-Programme dargestellt.

Abb. 3

Abbildung 3: Normierte Laufzeit von LAPACK-Routinen zur Lösung linearer Gleichungssysteme bei verschiedenen Matrixtypen.

Bei Verwendung von MATLAB 6 braucht der Benutzer diese Eigenschaften weder kennen noch in irgendeiner Weise berücksichtigen; die Verwendung des MATLAB-Befehls A\b gewährleistet in allen Fällen eine Problemlösung mit minimalem Rechenaufwand. Abb. 4 zeigt die entsprechenden Laufzeiten.

Abb. 4

Abbildung 4: Normierte Laufzeit von A\b (MATLAB 6 mit SCSL) bei verschiedenen Matrixtypen.

Insbesondere hervorzuheben ist der Komfort, den MATLAB 6 gegenüber der direkten Verwendung von LAPACK-Programmen bietet. Man erspart sich die Auswahl der passenden Programme und auch die unübersichtlichen und fehleranfälligen Aufrufe der LAPACK-Routinen.

Diskrete Fourier-Transformationen

MATLAB 6 enthält mit FFTW (Fastest Fourier Transform in the West) von Matteo Frigo und Steven Johnson (MIT Laboratory for Computer Science) das zurzeit "innovativste" FFT-Pogrammpaket. In FFTW sind erste Ansätze zu einer architekturadaptiven FFT-Berechnung realisiert. In einer Initialisierungsphase wird ein "Berechnungsplan" ermittelt, der die FFT-Berechnung an die Speicherhierarchie des Rechners anpasst.

Abb. 5 zeigt einen Vergleich der normierten Laufzeiten der FFT-Berechnung von MATLAB 6 mit MATLAB 5.3 und der in C geschriebenen FFTW-Version.

Abb. 5

Abbildung 5: Normierte Laufzeit der FFT-Routinen in MATLAB 5.3, 6 und FFTW.

Wie man sieht, ist MATLAB 6 für lange Vektoren mehr als doppelt so schnell wie MATLAB 5.3. Der durch die Integration von FFTW in MATLAB entstandene Overhead ist dafür verantwortlich, dass die "reine" C-Implementierung ein - geringfügig - besseres Laufzeitverhalten aufweist.

Zusammenfassung

In MATLAB 6 wurde erstmals eine sehr komfortable und gleichzeitig effiziente Möglichkeit zur Lösung numerischer Probleme realisiert. Man kann ohne Übertreibung von einer neuen Generation numerischer Software sprechen.

Literatur

[1]    E. Anderson et al.: LAPACK User's Guide, 3rd ed., SIAM Press, Philadelphia, 1999.
[2]    J. J. Dongarra et al.: LINPACK User's Guide. SIAM Press, Philadelphia, 1979.
[3]    C. W. Überhuber: Numerical Computation. Springer-Verlag, Heidelberg, 1997.
[4]    C. W. Überhuber, S. Katzenbeisser: MATLAB 6. Springer-Verlag, Wien, 2000.


1 siehe http://www.netlib.org/lapack/

2 siehe http://www.netlib.org/blas/


Zum Inhaltsverzeichnis, ZIDline 4, Dezember 2000