Dynamik auf Netzwerken ist ein mathematisches Feld, das in den letzten Jahrzehnten schnell gewachsen ist und Anwendungen in zahlreichen Disziplinen wie z.B. Physik, Biologie und Soziologie findet. Die Funktion vieler Netzwerke hängt von der Fähigkeit ab, die Elemente des Netzwerkes zu synchronisieren. Mit anderen Worten, die Existenz und die transversale Stabilität der synchronen Mannigfaltigkeit sind zentrale Eigenschaften. Erst seit einigen Jahren wird versucht, den verwickelten Zusammenhang zwischen der Kopplungsstruktur und den Stabilitätseigenschaften synchroner Zustände zu verstehen. Genau das ist das zentrale Thema dieser Arbeit. Zunächst präsentiere ich erste Ergebnisse zur Klassifizierung der Kanten eines gerichteten Netzwerks bezüglich ihrer Bedeutung für die Stabilität des synchronen Zustands. Folgend untersuche ich ein komplexes Verzweigungsszenario in einem gerichteten Ring von Stuart-Landau Oszillatoren und zeige, dass das Szenario persistent ist, wenn dem Netzwerk eine schwach gewichtete Kante hinzugefügt wird. Daraufhin untersuche ich synchrone Zustände in Ringen von Phasenoszillatoren die mit Zeitverzögerung gekoppelt sind. Ich bespreche die Koexistenz synchroner Lösungen und analysiere deren Stabilität und Verzweigungen. Weiter zeige ich, dass eine Zeitverschiebung genutzt werden kann, um Muster im Ring zu speichern und wiederzuerkennen. Diese Zeitverschiebung untersuche ich daraufhin für beliebige Kopplungsstrukturen. Ich zeige, dass invariante Mannigfaltigkeiten des Flusses sowie ihre Stabilität unter der Zeitverschiebung erhalten bleiben. Darüber hinaus bestimme ich die minimale Anzahl von Zeitverzögerungen, die gebraucht werden, um das System äquivalent zu beschreiben. Schließlich untersuche ich das auffällige Phänomen eines nichtstetigen Übergangs zu Synchronizität in Klassen großer Zufallsnetzwerke indem ich einen kürzlich eingeführten Zugang zur Beschreibung großer Zufallsnetzwerke auf den Fall zeitverzögerter Kopplungen verallgemeinere. / Since a couple of decades, dynamics on networks is a rapidly growing branch of mathematics with applications in various disciplines such as physics, biology or sociology. The functioning of many networks heavily relies on the ability to synchronize the network’s nodes. More precisely, the existence and the transverse stability of the synchronous manifold are essential properties. It was only in the last few years that people tried to understand the entangled relation between the coupling structure of a network, given by a (di-)graph, and the stability properties of synchronous states. This is the central theme of this dissertation. I first present results towards a classification of the links in a directed, diffusive network according to their impact on the stability of synchronization. Then I investigate a complex bifurcation scenario observed in a directed ring of Stuart-Landau oscillators. I show that under the addition of a single weak link, this scenario is persistent. Subsequently, I investigate synchronous patterns in a directed ring of phase oscillators coupled with time delay. I discuss the coexistence of multiple of synchronous solutions and investigate their stability and bifurcations. I apply these results by showing that a certain time-shift transformation can be used in order to employ the ring as a pattern recognition device. Next, I investigate the same time-shift transformation for arbitrary coupling structures in a very general setting. I show that invariant manifolds of the flow together with their stability properties are conserved under the time-shift transformation. Furthermore, I determine the minimal number of delays needed to equivalently describe the system’s dynamics. Finally, I investigate a peculiar phenomenon of non-continuous transition to synchrony observed in certain classes of large random networks, generalizing a recently introduced approach for the description of large random networks to the case of delayed couplings.

Daten werden noch immer groesstenteils in Dateien und nicht in Datenbanken gespeichert. Dieser Trend wird durch den Internetboom der 90er Jahre nur noch verstaerkt. Daraus ist das Forschungsgebiet der semistrukturierten Daten entstanden. Semistrukturierte Daten sind Daten, die meist in Dokumenten gespeichert sind und eine implizite und irregulaere Struktur aufweisen. HTML- oder BibTeX-Dateien oder in ASCII-Dateien gespeicherte Genomdaten sind Beispiele. Traditionelles Datenbankmanagement erfordert Design und sichert Deklarativitaet zu. Dies ist im Umfeld der semistrukturierten Daten nicht gegeben, ein flexiblerer Ansatz wird gebraucht. In dieser Arbeit wird ein neuer Ansatz des Abfragens semistrukturierter Daten praesentiert. Wir schlagen vor, semistrukturierte Daten durch eine Menge von partiellen Schemata zu beschreiben, anstatt zu versuchen, ein globales Schema zu definieren. Letzteres ist zwar geeignet, einen effizienten Zugriff auf Daten zu ermoeglichen; ein globales Schema fuer semistrukturierte Daten leidet aber zwangslaeufig an der Irregularitaet der Struktur der Daten. Wegen der vielen Ausnahmen vom intendierten Schema wird ein globales Schema schnell sehr gross und wenig repraesentativ. Damit wird dem Nutzer ein verzerrtes Bild ueber die Daten gegeben. Hingegen koennen partielle Schemata eher ein repraesentatives Bild eines Teils der Daten darstellen. Mit Hilfe statistischer Methoden kann die Guete eines partiellen Schemas bewertet werden, ebenso koennen irrelevante Teile der Datenbank identifiziert werden. Ein Datenbanksystem, das auf partiellen Schemata basiert, ist flexibler und reflektiert den Grad der Strukturierung auf vielen Ebenen. Seine Benutzbarkeit und seine Performanz steigen mit einem hoeheren Grad an Struktur und mit seiner Nutzungsdauer. Partielle Schemata koennen auf zwei Arten gewonnen werden. Erstens koennen sie durch einen Datenbankdesigner bereitgestellt werden. Es ist so gut wie unmoeglich, eine semistrukturierte Datenbank komplett zu modellieren, das Modellieren gewisser Teile ist jedoch denkbar. Zweitens koennen partielle Schemata aus Benutzeranfragen gewonnen werden, wenn nur die Anfragesprache entsprechend entworfen und definiert wird. Wir schlagen vor, eine Anfrage in einen ``Was''- und einen ``Wie''-Teil aufzuspalten. Der ``Was''-Teil wird durch partielle Schemata repraesentiert. Partielle Schemata beinhalten reiche semantische Konzepte, wie Variablendefinitionen und Pfadbeschreibungen, die an Konzepte aus Anfragesprachen angelehnt sind. Mit Variablendefinitionen koennen verschiedene Teile der Datenbank miteinander verbunden werden. Pfadbeschreibungen helfen, durch das Zulassen einer gewissen Unschaerfe, die Irregularitaet der Struktur der Daten zu verdecken. Das Finden von Stellen der Datenbank, die zu einem partiellen Schema passen, bildet die Grundlage fuer alle Arten von Anfragen. Im ``Wie''-Teil der Anfrage werden die gefundenen Stellen der Datenbank fuer die Antwort modifiziert. Dabei koennen Teile der gefundenen Entsprechungen des partiellen Schemas ausgeblendet werden oder auch die Struktur der Antwort voellig veraendert werden. Wir untersuchen die Ausdrucksstaerke unserer Anfragesprache, in dem wir einerseits die Operatoren der relationalen Algebra abbilden und andererseits das Abfragen von XML-Dokumenten demonstrieren. Wir stellen fest, dass das Finden der Entsprechungen eines Schemas (wir nennen ein partielles Schema in der Arbeit nur Schema) den aufwendigsten Teil der Anfragebearbeitung ausmacht. Wir verwenden eine weitere Abstraktionsebene, die der Constraint Satisfaction Probleme, um die Entsprechungen eines Schemas in einer Datenbank zu finden. Constraint Satisfaction Probleme bilden eine allgemeine Klasse von Suchproblemen. Fuer sie existieren bereits zahlreiche Optimierungsalgorithmen und -heuristiken. Die Grundidee besteht darin, Variablen mit zugehoerigen Domaenen einzufuehren und dann die Werte, die verschiedene Variablen gleichzeitig annehmen koennen, ueber Nebenbedingungen zu steuern. In unserem Ansatz wird das Schema in Variablen ueberfuehrt, die Domaenen werden aus der Datenbank gebildet. Nebenbedingungen ergeben sich aus den im Schema vorhandenen Praedikaten, Variablendefinitionen und Pfadbeschreibungen sowie aus der Graphstruktur des Schemas. Es werden zahlreiche Optimierungstechniken fuer Constraint Satisfaction Probleme in der Arbeit vorgestellt. Wir beweisen, dass die Entsprechungen eines Schemas in einer Datenbank ohne Suche und in polynomialer Zeit gefunden werden koennen, wenn das Schema ein Baum ist, keine Variablendefinitionen enthaelt und von der Anforderung der Injektivitaet einer Einbettung abgesehen wird. Zur Optimierung wird das Enthaltensein von Schemata herangezogen. Das Enthaltensein von Schemata kann auf zwei Weisen, je nach Richtung der Enthaltenseinsbeziehung, genutzt werden: Entweder kann der Suchraum fuer ein neues Schema reduziert werden oder es koennen die ersten passenden Stellen zu einem neuen Schema sofort praesentiert werden. Der gesamte Anfrageansatz wurde prototypisch zunaechst in einem Public-Domain Prolog System, spaeter im Constraintsystem ECLiPSe implementiert und mit Anfragen an XML-Dokumente getestet. Dabei wurden die Auswirkungen verschiedener Optimierungen getestet. Ausserdem wird eine grafische Benutzerschnittstelle zur Verfuegung gestellt. / Most of today's data is still stored in files rather than in databases. This fact has become even more evident with the growth of the World Wide Web in the 1990s. Because of that observation, the research area of semistructured data has evolved. Semistructured data is typically stored in documents and has an irregular, partial, and implicit structure. The thesis presents a new framework for querying semistructured data. Traditional database management requires design and ensures declarativity. The possibilities to design are limited in the field of semistructured data, thus, a more flexible approach is needed. We argue that semistructured data should be represented by a set of partial schemata rather than by one complete schema. Because of irregularities of the data, a complete schema would be very large and not representative. Instead, partial schemata can serve as good representations of parts of the data. While finding a complete schema turns out to be difficult, a database designer may be able to provide partial schemata for the database. Also, partial schemata can be extracted from user queries if the query language is designed appropriately. We suggest to split the notion of query into a ``What''- and a ``How''-part. Partial schemata represent the ``What''-part. They cover semantically richer concepts than database schemata traditionally do. Among these concepts are predicates, variable definitions, and path descriptions. Schemata can be used for query optimization, but they also give users hints on the content of the database. Finding the occurrences (matches) of such a schema forms the most important part of query execution. All queries of our approach, such as the focus query or the transformation query, are based on this matching. Query execution can be optimized using knowledge about containment relationships between different schemata. Our approach and the optimization techniques are conceptually modeled and implemented as a prototype on the basis of Constraint Satisfaction Problems (CSPs). CSPs form a general class of search problems for which many techniques and heuristics exist. A CSP consists of variables that have a domain associated to them. Constraints restrict the values that variables can simultaneously take. We transform the problem of finding the matches of a schema in a database to a CSP. We prove that under certain conditions the matches of a schema can be found without any search and in polynomial time. For optimization purposes the containment relationship between schemata is explored. We formulate a sufficient condition for schema containment and test it again using CSP techniques. The containment relationship can be used in two ways depending on the direction of the containment: It is either possible to reduce the search space when looking for matches of a schema, or it is possible to present the first few matches immediately without any search. Our approach has been implemented into the constraint system ECLiPSe and tested using XML documents.

Wir beginnen mit der Herleitung der asymptotischen Entwicklung der Spur des Wärmeleitungskernes, $\tr e^{-t\Delta}$, für $t\to0+$, wobei $\Delta$ der Laplace-Beltrami-Operator auf einer Mannigfaltigkeit mit Kegel-Singularitäten ist; dabei folgen wir der Arbeit von Brüning und Seeley. Dann untersuchen wir, wie die Koeffizienten der Entwicklung mit der Geometrie der Mannigfaltigkeit zusammenhängen, insbesondere fragen wir, ob die (mögliche) Singularität der Mannigfaltigkeit aus den Koeffizienten - und damit aus dem Spektrum des Laplace-Beltrami-Operators - abgelesen werden kann. In wurde gezeigt, dass im zweidimensionalen Fall ein logarithmischer Term und ein nicht lokaler Term im konstanten Glied genau dann verschwinden, wenn die Kegelbasis ein Kreis der Länge $2\pi$ ist, die Mannigfaltigkeit also geschlossen ist. Dann untersuchen wir wir höhere Dimensionen. Im vier-dimensionalen Fall zeigen wir, dass der logarithmische Term genau dann verschwindet, wenn die Kegelbasis eine sphärische Raumform ist. Wir vermuten, dass das Verschwinden eines nicht lokalen Beitrags zum konstanten Term äquivalent ist dazu, dass die Kegelbasis die runde Sphäre ist; das kann aber bisher nur im zyklischen Fall gezeigt werden. Für geraddimensionale Mannigfaltigkeiten höherer Dimension und mit Kegelbasis von konstanter Krümmung zeigen wir weiter, dass der logarithmische Term ein Polynom in der Krümmung ist, das Wurzeln ungleich 1 haben kann, so dass erst das Verschwinden von mehreren Termen - die derzeit noch nicht explizit behandelt werden können - die Geschlossenheit der Mannigfaltigkeit zur Folge haben könnte. / We derive a detailed asymptotic expansion of the heat trace for the Laplace-Beltrami operator on functions on manifolds with one conic singularity, using the Singular Asymptotics Lemma of Jochen Bruening and Robert T. Seeley. Then we investigate how the terms in the expansion reflect the geometry of the manifold. Since the general expansion contains a logarithmic term, its vanishing is a necessary condition for smoothness of the manifold. It is shown in the paper by Bruening and Seeley that in the two-dimensional case this implies that the constant term of the expansion contains a non-local term that determines the length of the (circular) cross section and vanishes precisely if this length equals $2\pi$, that is, in the smooth case. We proceed to the study of higher dimensions. In the four-dimensional case, the logarithmic term in the expansion vanishes precisely when the cross section is a spherical space form, and we expect that the vanishing of a further singular term will imply again smoothness, but this is not yet clear beyond the case of cyclic space forms. In higher dimensions the situation is naturally more difficult. We illustrate this in the case of cross sections with constant curvature. Then the logarithmic term becomes a polynomial in the curvature with roots that are different from 1, which necessitates more vanishing of other terms, not isolated so far.

Die vorliegende Arbeit beschaeftigt sich mit der Herleitung, Analyse und Numerik von reduzierten Systemen gewoehnlicher Differenzialgleichungen (bezeichnet als reduzierte Modelle), die einer Familie von eindimensionalen Schmierfilmgleichungen (lubrication equations) entsprechen. Diese Familie wurde von Muench et al. 06'' hergeleitet und beschreibt den Entnetzungsprozess von nanoskopischen duennen Fluessigkeitsfilmen auf hydrophoben Polymersubstraten als Folge von anziehenden van der Waals und abstossenden Born Intermolekularkraeften. Dabei wurden verschiedene Regime von Schlupf-Laengen auf der Grenzflaeche zwischen Fluessigkeit und Polymersubstrat betrachtet. Die letzte Phase des Entnetzungsprozesses ist durch eine sehr langsame Vergroeberungsdynamik der verbleibenden Tropfen charakterisiert. Reduzierte Modelle, hergeleitet aus den zugrunde liegenden Schmierfilmgleichungen, ermoeglichen die effiziente analytische und numerische Untersuchung des Vergroeberungsprozesses. Im ersten Teil dieser Studie leiten wir unter Verwendung von asymptotischen Methoden reduzierte Modelle fuer verschiedene Schmierfilmgleichungen ab. Der zweite Teil dieser Studie widmet sich einer neuen Methode fuer die Herleitung und die Begruendung solcher reduzierter Modelle. Diese Methode basiert auf der Idee der Reduktion auf eine Zentrumsmannigfaltigkeit. Zuerst beschreiben wir eine formale Reduktion auf eine sogenannte "approximative invariante" Mannigfaltigkeit. Danach betrachten wir die Linearisierung der Schmierfilmgleichung um den stationaeren Tropfen. Hier geben wir eine rigorose Herleitung fuer das asymptotische Verhalten des Spektrums bezuglich des kleinen Parameters epsilon. Fuer das entsprechende Eigenwertproblem belegen wir die Existenz von einer von epsilon abhaengigen Luecke im Spektrum, die eine wichtige Eigenschaft fuer die strenge Begruendung unserer formalen Reduktion auf die "approximative invariante" Mannigfaltigkeit ist. / In this dissertation the topic of reduced ODE models corresponding to a family of one-dimensional lubrication equations derived by Muench et al. 06'' is addressed. This family describes the dewetting process of nanoscopic thin liquid films on hydrophobic polymer substrates due to the presence of several intermolecular forces and takes account of different ranges of slip-lengths at the polymer substrate interface. Reduced ODE models derived from underlying lubrication equations allow for an efficient analytical and numerical investigation of the latest stage of the dewetting process: coarsening dynamics of the remaining droplets. We first give an asymptotical derivation of these models and use them to investigate the influence of slip-length on the coarsening dynamics. In the second part of the talk we present a new geometric approach which can be used for an alternative derivation and justification of above reduced ODE models and is based on a center-manifold reduction recently applied by Mielke and Zelik 08'' to a certain class of semilinear parabolic equations. One of the main problems for a rigorous justification of this approach is investigation of the spectrum of a lubrication equation linearized at the stationary solution, which describes physically a single droplet. The corresponding eigenvalue problem turns out to be a singularly perturbed one with respect to a small parameter epsilon tending to zero. For this problem we show existence of an epsilon-dependent spectral gap between a unique exponentially small eigenvalue and the rest of the spectrum.

Es werden hybride Mannigfaltigkeiten untersucht, d.h. Systeme von zweidimensionalen Mannigfaltigkeiten, die durch eindimensionale Intervalle miteinander verknuepft sind. In einer solchen Struktur definieren wir einen Laplace-Operator, der sich aus den Laplace-Beltrami-Operatoren auf den glatten Teilen und Randbedingungen an den Verknuepfungspunkten zusammenstellt. Durch Verwendung der Kreinschen Theorie selbstadjungierter Erweiterungen wird es gezeigt, dass alle moeglichen Laplace-Operatoren durch hermitsche Matrizen einer speziellen Form parametrisiert werden koennen. Wir berechnen die Entwicklung der Spur der quadrirten Resolvent eines Laplace-Operators fuer grosse Spectralparameter vermittels der Randbedingungen und der Waermeleitungskoeffizienten der glatten Teilen der hybriden Mannigfaltigkeit. Unter gewissen zusaetzlichen Annahmen is es moeglich, aus dieser Entwicklung einige geometrische Invarianten und einige Information ueber den Randbedingungen zu gewinnen. / We consider a hybrid manifold (i.e. some two-dimensional manifolds connected with each other by some segments) and a Laplace operator on it. Such an operator can be constructed by using the Laplace-Beltrami operators on each part of the hybrid manifold with some boundary conditions in the points of gluing. We use the Krein theory of self-adjoint extensions to show that all possible Laplace operators are parameterized by some Hermitian matrices. We find the large spectral parameter expansion of the trace of the second power of the resolvent of a fixed Laplace operator in terms of the boundary condition matrix and heat kernel coefficients for the parts of the hybrid manifold. If we assume that we already have such an expansion for some hybrid manifold then we can find some data about this manifold (inverse spectral problem). Under some additional conditions it is possible to find some geometric invariants of the hybrid space and some information about the boundary conditions matrix. We apply the same technique also to two degenerate cases of hybrid manifolds: quantum graphs and the manifolds glued without segments.

Dyson-Schwinger-Gleichungen sind Fixpunktgleichungen, die in der Quantenfeldtheorie auftauchen. Obwohl es bekannt ist, wie die Kombinatorik vor der Anwendung von Feynman-Regeln aussieht, war die Kombinatorik der resultierenden analytischen Dyson-Schwinger-Gleichungen bisher unbekannt. Wir verallgemeinern die Arbeiten von Yeats et.al. auf diesem Gebiet zu einer Klasse von unendlich vielen Dyson-Schwinger-Gleichungen mit Hilfe von Sehnen-Diagrammen. / In quantum field theory, Dyson-Schwinger equations are fixed-point equations that come from self insertion properties of Feynman graphs. While the combinatorics of these are well understood, the combinatorics are still mysterious after applying the Feynman rules. We generalize the work of Yeats et.al. in this field to an infinite number of Dyson-Schwinger equations with the help of chord diagrams.

Sei V ein holomorphes Vektorbündel über einer q-konvexen Mannigfaltigkeit X. Die Andreotti-Grauert-Theorie sagt, dass die r-te Kohomologiegruppe holomorpher Schnitte mit Werten in V endlich-dimensional ist und dass die Kohomologie verschwindet, falls X q-vollständig ist. Ist E ein holomorphes Banachbündel über X, dann ist bekannt, dass die erste Kohomologiegruppe verschwindet, falls X Steinsch ist. Kapitel I gibt einen ausführlichen Überblick über die Arbeit. In Kapitel II wird gezeigt, dass es holomorphe Hilbertbündel über 1-konvexen Mannigfaltigkeiten gibt, für die die erste Kohomologie nicht Hausdorffsch ist. In Kapitel III wird folgender Endlichkeitssatz gezeigt: Ist E ein holomorph triviales Banachbündel oder ein holomorphes Banachbündel von kompaktem Typ mit kompakter Approximationseigenschaft über einer q-konvexen Mannigfaltigkeit X, und ist V ein holomorphes Vektorbündel über X, für das die q-te Kohomologie verschwindet, dann gilt: Die q-te Kohomologie für das Tensorprodukt von V und E ist endlich-dimensional. Ist X q-vollständig, dann verschwindet die r-te Kohomologie, falls r größer oder gleich q ist. Für r größer q kann dies auch für beliebige holomorphe Banachbündel E gezeigt werden. Im Anhang wird skizziert, wie der Ansatz der L2-Methode im Fall r gleich q für Hilbertbündel zu einem Verschwindungssatz führen könnte. / Let V be a holomorphic vector bundle over a q-convex manifold X. The Andreotti-Grauert theory says that the r-th cohomology group of holomorphic section with values in V is finite dimensional and that the cohomology is vanishing if X is q-complete. If E is a holomorphic Banach bundle over X, it is known that the first cohomology group vanishes if X is Stein. Chapter I gives a detailed overview of the work. In chapter II it is shown that there are holomorphic Hilbert bundles over 1-convex manifolds such that the first cohomology of the bundle is not Hausdorff. In chapter III the following finiteness theorem is shown: If E is a holomorphically trivial Banach bundle or a holomorphic Banach bundle of compact type with the compact approximation property over a q-convex manifold X, and if V is a holomorphic vector bundle over X such that the q-th cohomology vanishes, then the following holds true: The q-th cohomology for the tensor product of V and E is finite dimensional. If X is q-complete, then the r-th cohomology vanishes if r is greater or equal q. If r is greater than q, this is shown also for arbitrary holomorphic Banach bundles E. In the appendix it is sketched how for r equal q the L2 method could yield a vanishing theorem for Hilbert bundles.

Die parallele Anfragebearbeitung für relationale Datenbankmanagementsysteme (RDBMS) ist wegen ihrer unterschiedlichen Arten der Ausführungsparallelität und den Eigenschaften der zugrunde liegenden parallelen Architektur ein äusserst komplexes Problem. Systemänderungen zur Laufzeit der Anfrage können zusätzlich ein dynamisches Verhalten der ausführenden Komponenten erfordern, um eine nahezu optimale Antwortzeit zu gewährleisten. Diese Arbeit stellt einen neuen, flexiblen Ansatz für die Optimierung und Abarbeitung von komplexen Anfragen vor, der besonders die dynamische Optimierung berücksichtigt. Insbesondere werden in der Arbeit folgende Teile präsentiert: 1. die Architektur eines neuen, verteilt-kooperierenden Komponentensystems beeinflusst von agenten-orientierten Konzepten; 2. der Entwurf und die Realisierung einer neuen Kommunikationsinfrastruktur für die identifizierten Systemkomponenten; 3. der Entwurf und die Implementierung eines flexiblen Anfrageoptimierers mit einem neuen, zufallsbasierten Algorithmus; und 4. der Entwurf und die Realisierung einer parallel arbeitenden Ausführungskomponente unter besonderer Berücksichtigung der dynamischen Anfrageoptimierung. Bei der Entwicklung der Konzepte standen neben den spezifischen Anforderungen für RDBMS besonders die Konfigurierbarkeit und die Erweiterbarkeit des verteilten Systems im Vordergrund. / Parallel query evaluation for relational database management systems (RDBSM) still remains a challenging problem. Modern systems must show near optimal performance in spite of running in a heterogeneous hardware environment, exploiting different ways of parallelism and dealing with unpredictable system load. This thesis paper presents a dynamic and flexible system addressing the issues of optimization and evaluation of relational queries for a distributed and dynamic environment. In particular, this work consists of: 1) the architecture of a distributed system which was inspired by the concepts of software agents, 2) the architecture and the implementation of a communication infrastructure for the system components, 3) the architecture and the implementation of a new query optimization algorithm, and 4) the concept and the implementation of a new query evaluation engine for parallel execution, which enables runtime optimization of queries. Furthermore, the design supports the extension and the configuration of the system and its components.

In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt. / This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.

No description available.