@phdthesis{Zumbusch, author = {Zumbusch, Gerhard}, title = {Simultanous h-p Adaption in Multilevel Finite Elements}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5298}, number = {TR-95-14}, language = {en} } @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} } @phdthesis{Weismantel, author = {Weismantel, Robert}, title = {Plazieren von Zellen: Theorie und L{\"o}sung eines quadratischen 0/1- Optimierungsproblems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4883}, number = {TR-92-03}, abstract = {Die vorliegende Arbeit besch{\"a}ftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexit{\"a}tstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die L{\"o}sung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur L{\"o}sung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, besch{\"a}ftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gel{\"o}st werden k{\"o}nnen und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.}, language = {de} } @phdthesis{Stalling, author = {Stalling, Detlev}, title = {Fast Texture-Based Algorithms for Vector Field Visualization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3838}, number = {SC-98-40}, abstract = {In this thesis we develop new methods for visualizing vector fields which specifically address three design goals: accuracy, performance, and cognition. Our methods will be general-purpose and can be applied to arbitrary vector fields in two- and three-dimensional space. The methodology behind our approach is {\em texture-based visualization}. Texture-based visualization methods imitate techniques known from experimental flow visualization, namely, the observation of randomly dispersed particles or dye injection patterns. Instead of depicting individual lines or symbols, a contiguous high-resolution image or texture is generated. This texture clearly reveals the directional structure of the field. In this way intuitive insight can be obtained and even small details of the field become visible. However, it remains unclear what kind of textures are best suited for our purpose. How do we generate them? Can we apply these methods in three-dimensional space? In particular, we focus on a technique known as {\em line integral convolution} or LIC. This method turns out to be quite versatile and well-suited for visualizing many interesting vector fields. LIC images display the integral curves or field lines of a vector field at high spatial resolution. Although conceptually quite simple, line integral convolution implies a number of interesting mathematical and algorithmic questions.}, language = {en} } @phdthesis{Schuette, author = {Sch{\"u}tte, Christof}, title = {A Quasiresonant Smoothing Algorithm for Solving Large Highly Differential Equations from Quantum Chemistry.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5090}, number = {TR-94-04}, abstract = {In Quantum Chemistry the field of Laser--Assisted Molecular Control'' has received a considerable amount of attention recently. One key problem in this new field is the simulation of the dynamical reaction of a molecule subjected to external radiation. This problem is described by the Schr{\"o}dinger equation, which, after eigenfunction expansion, can be written in the form of a large system of ordinary differential equations, the solutions of which show a highly oscillatory behaviour. The oscillations with high frequencies and small amplitudes confine the stepsizes of any numerical integrator -- an effect, which, in turn, blows up the simulation time. Larger stepsizes can be expected by averaging these fast oscillations, thus smoothing the trajectories. Standard smoothing techniques (averaging, filtering) would kill the whole process and thus, lead to wrong numerical results. To avoid this unwanted effect and nevertheless speed up computations, this paper presents a quasiresonant smoothing algorithm (QRS). In QRS, a natural splitting parameter \$\delta\$ controls the smoothing properties. An adaptive QRS--version (AQRS) is presented which includes an error estimation scheme for choosing this parameter \$\delta\$ in order to meet a given accuracy requirement. In AQRS \$\delta\$ is permanently adapted to the solution properties for computing the chemically necessary information'' only. The performance of AQRS is demonstrated in several test problems from the field Laser--Assisted Selective Excitation of Molecules'' in which the external radiation is a picosecond laser pulse. In comparison with standard methods speedup factors of the order of \$10^2\$ are observed.}, language = {en} } @phdthesis{Nowak, author = {Nowak, Ulrich}, title = {Adaptive Linienmethoden f{\"u}r nichtlineare parabolische Systeme in einer Raumdimension.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5059}, number = {TR-93-14}, abstract = {A new method for the numerical solution of highly nonlinear, coupled systems of parabolic differential equations in one space dimension is presented. The approach is based on a classical method of lines treatment. Time discretization is done by means of the semi--implicit Euler discretization. Space discretization is done with finite differences on non--uniform grids. Both basic discretizations are coupled with extrapolation techniques. With respect to time the extrapolation is of variable order whereas just one extrapolation step is done in space. Based on local error estimates for both, the time and the space discretization error, the accuracy of the numerical approximation is controlled and the discretization stepsizes are adapted automatically and simultaneously. Besides the local adaptation of the space grids after each integration step (static regridding), the grid may even move within each integration step (dynamic regridding). Thus, the whole algorithm has a high degree of adaptivity. Due to this fact, challenging problems from applications can be solved in an efficient and robust way.}, language = {en} } @phdthesis{Martin, author = {Martin, Alexander}, title = {Packen von Steinerb{\"a}umen: Polyedrische Studien und Anwendung.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4894}, number = {TR-92-04}, abstract = {Gegeben sei ein Graph \$G=(V,E)\$ mit positiven Kantenkapazit{\"a}ten \$c_e\$ und Knotenmengen \$T_1,\ldots,T_N\$. Das Steinerbaumpackungs-Problem besteht darin, Kantenmengen \$S_1,\ldots,S_N\$ zu finden, so da\ss\ jedes \$S_k\$ die Knoten aus \$T_k\$ verbindet und jede Kante \$e\$ in h{\"o}chstens \$c_e\$ Kantenmengen aus \$S_1,\ldots,S_N\$ vorkommt. Eine zul{\"a}ssige L{\"o}sung dieses Problems nennen wir eine Steinerbaumpackung. Ist zus{\"a}tzlich eine Gewichtung der Kanten gegeben und nach einer bez{\"u}glich dieser Gewichtung minimalen Steinerbaumpackung gesucht, so sprechen wir vom gewichteten Steinerbaumpackungs-Problem. Die Motivation zum Studium dieses Problems kommt aus dem Entwurf elektronischer Schaltungen. Ein dort auftretendes Teilproblem ist das sogenannte Verdrahtungsproblem, das im wesentlichen darin besteht, gegebene Punktmengen unter bestimmten Nebenbedingungen und Optimalit{\"a}tskriterien auf einer Grundfl{\"a}che zu verbinden. Wir studieren das Steinerbaumpackungs-Problem aus polyedrischer Sicht und definieren ein Polyeder, dessen Ecken genau den Steinerbaumpackungen entsprechen. Anschlie\ss end versuchen wir, dieses Polyeder durch gute'' beziehungsweise facetten-definierenden Ungleichungen zu beschreiben. Basierend auf diesen Ungleichungen entwickeln wir ein Schnittebenenverfahren. Die L{\"o}sung des Schnittebenenverfahrens liefert eine untere Schranke f{\"u}r die Optimall{\"o}sung und dient als Grundlage f{\"u}r die Entwicklung guter Primalheuristiken. Wir haben das von uns implementierte Schnittebenenverfahren an einem Spezialfall des Verdrahtungsproblems, dem sogenannten Switchbox-Verdrahtungsproblem, getestet und vielversprechende Ergebnisse erzielt.}, language = {de} } @phdthesis{Koch, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8346}, number = {04-58}, abstract = {The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.}, language = {en} } @phdthesis{Hohmann, author = {Hohmann, Andreas}, title = {Inexact Gauss Newton Methods for Parameter Dependent Nonlinear Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5049}, number = {TR-93-13}, abstract = {A new approach to inexact Gauss Newton methods for the solution of underdetermined nonlinear problems is presented. It is based on a convergence theorem being invariant under affine transformations of the domain and results in an easily implementable accuracy matching strategy for the arising linear subproblems which guarantees the quadratic convergence. Thanks to the weak assumptions on the given nonlinear problem, the results provide a general framework for multilevel Newton and continuation methods. As an example, a new multilevel Newton h-p collocation method for boundary value problems of ordinary differential equations is developed. It combines the inexact Newton method with a linear collocation solver using adaptive refinement and variable orders. The performance of the resulting C++ class library {\sc Cocon} is demonstrated by some numerical examples including singular perturbed problems. In addition, the new method is applied to a realistic railway bogie model in which a branch of periodic solutions emanates from a branch of fixed points at a Hopf bifurcation.}, language = {en} } @phdthesis{Ascheuer, author = {Ascheuer, Norbert}, title = {Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5328}, number = {TR-96-03}, abstract = {In this thesis we describe a practical problem that we encountered in the on--line optimization of a complex Flexible Manufacturing System. In the considered system a stacker crane has to fulfill all transportation tasks (jobs) in a single aisled automatic storage system. The jobs have to be sequenced in such a way, that the time needed for the unloaded moves is minimized. The modelling of this question leads to the so--called on--line Hamiltonian path problem. We computationally compare several on--line heuristics and derive lower bounds on the value obtained by an optimal on--line strategy by analyzing two off--line Combinatorial Optimization problems: the asymmetric Hamiltonian path problem with precedence constraints, also called sequential ordering problem (SOP), and the asymmetric Hamiltonian path problem with time windows (AHPPTW). We study the SOP and AHPPTW from a polyhedral point of view and derive several new classes of valid inequalities. Based on the polyhedral investigations we develop branch\&cut algorithms for both problems and can achieve encouraging results on solving problem instances from real--world examples of the practical application.}, language = {en} }