@phdthesis{Wunderling, author = {Wunderling, Roland}, title = {Paralleler und Objektorientierter Simplex}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5386}, number = {TR-96-09}, abstract = {{\footnotesize In der vorliegenden Arbeit werden neue Implementierungen des dualen und primalen revidierten Simplex-Algorithmus f{\"u}r die L{\"o}sung linearer Programme (LPs) vorgestellt. Dazu werden die Algorithmen mithilfe einer Zeilenbasis dargestellt, aus der {\"u}ber einen Spezialfall die {\"u}bliche Darstellung mit einer Spaltenbasis folgt. Beide Darstellungen sind {\"u}ber die Dualit{\"a}t eng miteinander verbunden. Ausserdem wird eine theoretische Untersuchung der numerischen Stabilit{\"a}t von Simplex-Algorithmen durchgef{\"u}hrt, und es werden verschiedene M{\"o}glichkeiten der Stabilisierung diskutiert. Beide Darstellungen der Basis werden in den Implementierungen algorithmisch ausgenutzt, wobei der Einsatz der Zeilenbasis f{\"u}r LPs mit mehr Nebenbedingungen als Variablen Geschwindigkeitsvorteile bringt. Dar{\"u}berhinaus werden weitere Beschleunigung gegen{\"u}ber anderen state-of-the-art Implentierungen erzielt, und zwar durch den Einsatz eines Phase-1 LPs, das eine gr{\"o}sstm{\"o}gliche {\"U}bereinstimmung mit dem Ausgangs-LPs aufweist, durch eine dynamische Anpassung der Faktorisierungsfrequenz f{\"u}r die Basis-Matrix und durch die Optimierung der L{\"o}sung linearer Gleichungssysteme f{\"u}r besonders d{\"u}nnbesetzte Matrizen und Vektoren. Es wurden drei Implementierungen vorgenommen. Die erste l{\"a}uft sequentiell auf einem PC oder einer Workstation. Ihre hohe numerische Stabilit{\"a}t und Effizienz durch die Integration der oben genannten Konzepte machen sie zu einem zuverl{\"a}ssigen Hilfsmittel f{\"u}r den t{\"a}glichen Einsatz z.B.~in Schnittebenenverfahren zur L{\"o}sung ganzzahliger Programme. Als Programmiersprache wurde C++ verwendet, und es wurde ein objektorientierter Software-Entwurf zugrundegelegt. Dieser leistet eine hohe Flexibilit{\"a}t und Anpassbarkeit z.B.~f{\"u}r die Integration benutzerdefinierter Pricing-Strategien. Bei den anderen beiden Implentierungen handelt es sich um parallele Versionen f{\"u}r Parallelrechner mit gemeinsamem und f{\"u}r solche mit verteiltem Speicher. Dabei wird der objektorientierte Entwurf so genutzt, dass lediglich die zus{\"a}tzlichen Aufgaben f{\"u}r die Parallelisierung (Synchronisation, Kommunikation und Verteilung der Arbeit) implementiert werden, w{\"a}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{\"a}ufig gel{\"o}st. Schliesslich wird ein paralleles Block-Pivoting verwendet, bei dem Gleichungssysteme mehrerer aufeinanderfolgender Iterationen gleichzeitig gel{\"o}st werden. Ob und welche der Parallelisierungs-Konzepte eine Beschleunigung bewirken, ist problemabh{\"a}ngig. Es gelingt z.B.~mit 32 Prozessoren eine Beschleunigung um mehr als einen Faktor 16 zu erzielen. Schliesslich wird die parallele L{\"o}sung d{\"u}nnbesetzter linearer Gleichungssysteme mit unsymmetrischen Matrizen untersucht und eine Implementierung f{\"u}r den Cray T3D vorgenommen. Sie enth{\"a}lt ein neues Verfahren des Lastausgleichs, das keinen zus{\"a}tzlichen Aufwand verursacht. Die Implementierung erzielt vergleichsweise g{\"u}nstige Laufzeiten.}}, language = {de} } @misc{GrammelHegeWunderling, author = {Grammel, Martin and Hege, Hans-Christian and Wunderling, Roland}, title = {On the Impact of Communication Latencies on Distributed Sparse LU Factorization.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1245}, number = {SC-93-28}, abstract = {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.}, language = {en} } @inproceedings{GrammelBackWunderlingetal.1994, author = {Grammel, Martin and Back, Godmar and Wunderling, Roland and Hege, Hans-Christian}, title = {Ein paralleles C++/C-Programmiermodell f{\"u}r ein objektorientiertes B\&C-Framework}, series = {GI/ITG-Workshop, Sept.1994, Mitteilungen der Fachgruppe PARS der Gesellschaft f{\"u}r Informatik (GI)}, volume = {13}, booktitle = {GI/ITG-Workshop, Sept.1994, Mitteilungen der Fachgruppe PARS der Gesellschaft f{\"u}r Informatik (GI)}, address = {Potsdam}, pages = {50 -- 59}, year = {1994}, language = {en} } @inproceedings{WunderlingGrammelHege1994, author = {Wunderling, Roland and Grammel, Martin and Hege, Hans-Christian}, title = {Parallele LU-Zerlegung großer, unsymmetrischer, d{\"u}nn besetzter Matrizen bei hohen Kommunikationslatenzen}, series = {GI/ITG-Workshop, Sept.1994, Mitteilungen der Fachgruppe PARS der Gesellschaft f{\"u}r Informatik (GI)}, volume = {13}, booktitle = {GI/ITG-Workshop, Sept.1994, Mitteilungen der Fachgruppe PARS der Gesellschaft f{\"u}r Informatik (GI)}, address = {Potsdam}, pages = {191 -- 200}, year = {1994}, language = {en} } @misc{WunderlingHege1992, author = {Wunderling, Roland and Hege, Hans-Christian}, title = {AGIL - the Adaptable Graphical Interface Layer, Programmierer-Handbuch}, publisher = {Interner Report, Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB), Germany}, pages = {34pp.}, year = {1992}, language = {en} } @misc{Wunderling1996, type = {Master Thesis}, author = {Wunderling, Roland}, title = {Paralleler und objektorientierter Simplex-Algorithmus}, year = {1996}, language = {en} }