Library

Description: {\footnotesize In der vorliegenden Arbeit werden neue Implementierungen des dualen und primalen revidierten Simplex-Algorithmus für die Lösung linearer Programme (LPs) vorgestellt. Dazu werden die Algorithmen mithilfe einer Zeilenbasis dargestellt, aus der über einen Spezialfall die übliche Darstellung mit einer Spaltenbasis folgt. Beide Darstellungen sind über die Dualität eng miteinander verbunden. Ausserdem wird eine theoretische Untersuchung der numerischen Stabilität von Simplex-Algorithmen durchgeführt, und es werden verschiedene Möglichkeiten der Stabilisierung diskutiert. Beide Darstellungen der Basis werden in den Implementierungen algorithmisch ausgenutzt, wobei der Einsatz der Zeilenbasis für LPs mit mehr Nebenbedingungen als Variablen Geschwindigkeitsvorteile bringt. Darüberhinaus werden weitere Beschleunigung gegenüber anderen state-of-the-art Implentierungen erzielt, und zwar durch den Einsatz eines Phase-1 LPs, das eine grösstmögliche Übereinstimmung mit dem Ausgangs-LPs aufweist, durch eine dynamische Anpassung der Faktorisierungsfrequenz für die Basis-Matrix und durch die Optimierung der Lösung linearer Gleichungssysteme für besonders dünnbesetzte Matrizen und Vektoren. Es wurden drei Implementierungen vorgenommen. Die erste läuft sequentiell auf einem PC oder einer Workstation. Ihre hohe numerische Stabilität und Effizienz durch die Integration der oben genannten Konzepte machen sie zu einem zuverlässigen Hilfsmittel für den täglichen Einsatz z.B.~in Schnittebenenverfahren zur Lösung ganzzahliger Programme. Als Programmiersprache wurde C++ verwendet, und es wurde ein objektorientierter Software-Entwurf zugrundegelegt. Dieser leistet eine hohe Flexibilität und Anpassbarkeit z.B.~für die Integration benutzerdefinierter Pricing-Strategien. Bei den anderen beiden Implentierungen handelt es sich um parallele Versionen für Parallelrechner mit gemeinsamem und für solche mit verteiltem Speicher. Dabei wird der objektorientierte Entwurf so genutzt, dass lediglich die zusätzlichen Aufgaben für die Parallelisierung (Synchronisation, Kommunikation und Verteilung der Arbeit) implementiert werden, während alle Algorithmen von der sequentiellen Implementierung geerbt werden. Die Parallelisierung setzt an vier Punkten an. Der erste und einfachste ist die parallele Berechnung eines Matrix-Vektor-Produktes. Als zweites wurden beim Pricing und Quotiententest parallele Suchalgorithmen eingesetzt. Weiter werden beim steepest-edge Pricing zwei lineare Gleichungssysteme nebenläufig gelöst. Schliesslich wird ein paralleles Block-Pivoting verwendet, bei dem Gleichungssysteme mehrerer aufeinanderfolgender Iterationen gleichzeitig gelöst werden. Ob und welche der Parallelisierungs-Konzepte eine Beschleunigung bewirken, ist problemabhängig. Es gelingt z.B.~mit 32 Prozessoren eine Beschleunigung um mehr als einen Faktor 16 zu erzielen. Schliesslich wird die parallele Lösung dünnbesetzter linearer Gleichungssysteme mit unsymmetrischen Matrizen untersucht und eine Implementierung für den Cray T3D vorgenommen. Sie enthält ein neues Verfahren des Lastausgleichs, das keinen zusätzlichen Aufwand verursacht. Die Implementierung erzielt vergleichsweise günstige Laufzeiten.}

Description: Sparse LU factorization offers some potential for parallelism, but at a level of very fine granularity. However, most current distributed memory MIMD architectures have too high communication latencies for exploiting all parallelism available. To cope with this, latencies must be avoided by coarsening the granularity and by message fusion. However, both techniques limit the concurrency, thereby reducing the scalability. In this paper, an implementation of a parallel LU decomposition algorithm for linear programming bases is presented for distributed memory parallel computers with noticable communication latencies. Several design decisions due to latencies, including data distribution and load balancing techniques, are discussed. An approximate performance model is set up for the algorithm, which allows to quantify the impact of latencies on its performance. Finally, experimental results for an Intel iPSC/860 parallel computer are reported and discussed.