Die Netzwerkanalyse zielt darauf ab, nicht-triviale Erkenntnisse aus vernetzten Daten zu gewinnen. Beispiele für diese Erkenntnisse sind die Wichtigkeit einer Entität im Verhältnis zu anderen nach bestimmten Kriterien oder das Finden des am besten geeigneten Partners für jeden Teilnehmer eines Netzwerks - bekannt als Maximum Weighted Matching (MWM). Da der Begriff der Wichtigkeit an die zu betrachtende Anwendung gebunden ist, wurden zahlreiche Zentralitätsmaße eingeführt. Diese Maße stammen hierbei aus Jahrzehnten, in denen die Rechenleistung sehr begrenzt war und die Netzwerke im Vergleich zu heute viel kleiner waren. Heute sind massive Netzwerke mit Millionen von Kanten allgegenwärtig und eine triviale Berechnung von Zentralitätsmaßen ist oft zu zeitaufwändig. Darüber hinaus ist die Suche nach der Gruppe von k Knoten mit hoher Zentralität eine noch kostspieligere Aufgabe. Skalierbare Algorithmen zur Identifizierung hochzentraler (Gruppen von) Knoten in großen Graphen sind von großer Bedeutung für eine umfassende Netzwerkanalyse. Heutigen Netzwerke verändern sich zusätzlich im zeitlichen Verlauf und die effiziente Aktualisierung der Ergebnisse nach einer Änderung ist eine Herausforderung. Effiziente dynamische Algorithmen sind daher ein weiterer wesentlicher Bestandteil moderner Analyse-Pipelines. Hauptziel dieser Arbeit ist es, skalierbare algorithmische Lösungen für die zwei oben genannten Probleme zu finden. Die meisten unserer Algorithmen benötigen Sekunden bis einige Minuten, um diese Aufgaben in realen Netzwerken mit bis zu Hunderten Millionen von Kanten zu lösen, was eine deutliche Verbesserung gegenüber dem Stand der Technik darstellt. Außerdem erweitern wir einen modernen Algorithmus für MWM auf dynamische Graphen. Experimente zeigen, dass unser dynamischer MWM-Algorithmus Aktualisierungen in Graphen mit Milliarden von Kanten in Millisekunden bewältigt. / Network analysis aims to unveil non-trivial insights from networked data by studying relationship patterns between the entities of a network. Among these insights, a popular one is to quantify the importance of an entity with respect to the others according to some criteria. Another one is to find the most suitable matching partner for each participant of a network knowing the pairwise preferences of the participants to be matched with each other - known as Maximum Weighted Matching (MWM). Since the notion of importance is tied to the application under consideration, numerous centrality measures have been introduced. Many of these measures, however, were conceived in a time when computing power was very limited and networks were much smaller compared to today's, and thus scalability to large datasets was not considered. Today, massive networks with millions of edges are ubiquitous, and a complete exact computation for traditional centrality measures are often too time-consuming. This issue is amplified if our objective is to find the group of k vertices that is the most central as a group. Scalable algorithms to identify highly central (groups of) vertices on massive graphs are thus of pivotal importance for large-scale network analysis. In addition to their size, today's networks often evolve over time, which poses the challenge of efficiently updating results after a change occurs. Hence, efficient dynamic algorithms are essential for modern network analysis pipelines. In this work, we propose scalable algorithms for identifying important vertices in a network, and for efficiently updating them in evolving networks. In real-world graphs with hundreds of millions of edges, most of our algorithms require seconds to a few minutes to perform these tasks. Further, we extend a state-of-the-art algorithm for MWM to dynamic graphs. Experiments show that our dynamic MWM algorithm handles updates in graphs with billion edges in milliseconds.

Matching of concepts with variables (concept patterns) is a relatively new operation that has been introduced in the context of description logics, originally to help filter out unimportant aspects of large concepts appearing in industrial-strength knowledge bases. Previous work has concentrated on (sub-)languages of CLASSIC, which in particular do not allow for existential restrictions. In this work, we present sound and complete decision algorithms for the solvability of matching problems and for computing sets of matchers for matching problems in description logics with existential restrictions.

This thesis deals with the optimal control of PDEs. After a brief introduction in the theory of elliptic and parabolic PDEs, we introduce a software that solves systems of PDEs by the finite elements method. In the second chapter we derive optimality conditions in terms of function spaces, i.e. a systems of PDEs coupled by some pointwise relations. Now we present algorithms to solve the optimality systems numerically and present some numerical test cases. A further chapter deals with the so called lack of adjointness, an issue of gradient methods applied on parabolic optimal control problems. However, since optimal control problems lead to large numerical schemes, model reduction becomes popular. We analyze the proper orthogonal decomposition method and apply it to our model problems. Finally, we apply all considered techniques to a real world problem.

The book summarises the results of the DFG-funded coordinated priority programme \"Fast Algorithms for Material Specific Process Chain Design and Analysis in Metal Forming\". In the first part it includes articles which provide a general introduction and overview on the field of process modeling in metal forming. The second part collates the reports from all projects included in the priority programme.

In dieser Arbeit geht es um die schrittweise Verfeinerung verteilter Algorithmen. Dabei wird ein einfacher Algorithmus, der einige gewünschte Eigenschaften hat, Schritt für Schritt zu einem komplexen Algorithmus verfeinert, der konkrete Implementationsanforderungen erfüllt, so daß in jedem Schritt die gewünschten Eigenschaften erhalten bleiben. Wir stellen einen neuen eigenschaftserhaltenden Verfeinerungsbegriff vor, der auf der kausalen Ordnung der Aktionen eines Algorithmus basiert. Diesen Begriff definieren wir als Transitionsverfeinerung für elementare Petrinetze und diskutieren Beweiskriterien. Danach definieren und diskutieren wir die simultane Verfeinerung mehrerer Transitionen. Zur Modellierung komplexer verteilter Algorithmen sind elementare Petrinetze oft nicht adäquat. Wir benutzen deshalb algebraische Petrinetze. Wir definieren Transitionsverfeinerung für algebraische Petrinetze und stellen einen Zusammenhang zur simultanen Verfeinerung von Transitionen in elementaren Petrinetzen her. Transitionsverfeinerung ist besonders für Verfeinerungsschritte geeignet, in denen synchrone Kommunikation zwischen Agenten durch asynchronen Nachrichtenaustausch ersetzt wird. Wir zeigen dies am Beispiel eines komplexen verteilten Algorithmus, zur Berechnung des minimalen spannenden Baumes in einem gewichteten Graphen. Wir zeigen die Korrektheit dieses Algorithmus in mehreren Schritten, von denen einige Schritte Transitionsverfeinerungen sind. In anderen Schritten sind klassische Verfeinerungsbegriffe ausreichend. Wir übertragen deshalb auch einen klassischen Verfeinerungsbegriff in unser formales Modell. / The topic of this PhD thesis is the stepwise refinement of distributed algorithms. Stepwise refinement starts with a simple algorithm with certain desired properties. This algorithm is refined step by step such that the desired properties are preserved in each refinement step. The result is a complex distributed algorithm which satisfies concrete implementation requirements and which still has the desired properties. We propose a new property preserving notion of refinement which is based on the causal ordering of actions of an algorithm. We call this notion transition refinement and we define it first for elementary Petri nets. Furthermore, we discuss proof criteria. Then, we define and discuss the simultaneous refinement of several transitions. For modelling complex distributed algorithms, we use algebraic Petri nets instead of elementary Petri nets. We define transition refinement for algebraic Petri nets, and we show its relationship to simultaneous transition refinement in elementary Petri nets. Transition refinement is particularly suitable for refinement steps in which synchronous communication between agents is replaced by asynchronous message passing. We show this by means of a complex distributed algorithm for determining the minimal spanning tree of a weighted graph. We prove the correctness of this algorithm in several steps. Some of these steps are transition refinements. For other steps, well-known notions of refinement are sufficient. Therefore, we also carry over a well-known notion of refinement into our formal model.

Für die erfolgreiche Lösung eines Optimierungsproblems ist die Wahl der verwendeten Suchstrategie von entscheidender Bedeutung. Die vorliegende Arbeit untersucht die Kriterien dieser Wahl. Dabei stellen sich drei grundlegende Fragen: Welche Strategien der Optimierung eines gegebenen Problems existieren überhaupt, und was für Eigenschaften besitzen sie? Wodurch wird der Charakter eines Optimierungsproblems bestimmt, und gibt es Klassen ähnlicher Probleme? Besteht eine Verbindung zwischen den Eigenschaften der Strategien und den Klassen der Probleme, die es ermöglicht, für jede Problemklasse eine geeignete Optimierungsstrategie anzugeben? Dazu wird zuerst die Klasse der Evolutionären Algorithmen naher betrachtet, deren generelles Verhalten die Boltzmannstrategie, Darwinstrategie oder Boltzmann-Darwin-Strategie beschreiben. Als weiteres Beispiel wird die Multitome Strategie untersucht. In ihr wird das Problem unter verschiedenen Gesichtspunkten betrachtet und in Einzelanforderungen zerlegt, die abwechselnd optimiert werden. Für den speziellen Fall der Dichotomen Strategie wird die allgemeine zeitabhängige Lösung mit Hilfe der Methode der Charakteristiken bestimmt. Zur Beantwortung der zweiten Frage wird die Zustandsdichte als klassifizierende Größe des Optimierungsproblems eingeführt. Sie kann unter Verwendung der Boltzmannstrategie während des Optimierungslaufes durch zwei allgemeine Approximationsmethoden: die Methode der stationären Verteilungen und die Eigenvektormethode bestimmt werden. Aus der Zustandsdichte erhält man den Wirkungsgrad der Zufallssuche. Er charakterisiert den Ordnungsgrad des Problems und stellt damit ein wichtiges Maß der Problemschwierigkeit dar. Die entscheidende dritte Frage wird für Probleme der Optimierung frustrierter Sequenzen, der Netzwerkoptimierung und für das Faltungsproblem der RNA behandelt. Mit der Einführung der Klassen gerichteter und ungerichteter Strategien, die für Optimierungsprobleme mit niedrigem bzw. hohem Wirkungsgrad der Zufallssuche effektiv sind, kann eine Verbindung zwischen dem Strategieverhalten und dem Problemcharakter hergestellt werden, die es ermöglicht, für eine konkrete Optimierungsaufgabe die Klasse der geeigneten Strategien zu wählen. / A crucial point of successful solving an optimization problem is the choice of the used strategy. The present paper investigates the criteria of this choice. Thereby three fundamental questions put themselves: Which strategies of the optimization of a given problem exist altogether, and which properties characterize the strategies? How is the character of an optimization problem determined, and are there classes of similar problems? Does a combination exist between the characteristics of the strategies and the classes of problems, which makes it possible to indicate a suitable strategy for each class? The class of the Evolutionary Algorithms is considered more closely. The general behavior of the algorithms can be described by the Boltzmann strategy, Darwin strategy or Boltzmann-Darwin strategy. As a further example the Multitomic strategy is explored. In this approach the problem is considered under different points of view and decomposes in single demands, which are optimized alternately. For the special case of the Dichotomic strategy the general time dependent solution is determined. To answer the second question the density of states is introduced as classifying measure of optimization problems. The density can be determined during the optimization course by two general approaches: the method of the stationary distribution and the eigenvalue method. From the density of states one receives the efficiency of the random search. It describes the degree of order of the problem and presents an measure of the problem difficulty. The important third question is treated for problems of the optimization of frustrated sequences, the network optimization and RNA folding. The introduction of the classes of directed and non directed strategies, which are effective for problems with low and high efficiency of the random search, establishes a connection between the strategy and the character of the problem, which makes it possible to choose the class of the suitable strategies for a given optimization task.

Die Besonderheit der drahtlosen Kommunikation gegenüber den drahtgebundenen Netzwerken liegt im drahtlosen Übertragungsmedium. Aufgrund der Broadcast-Eigenschaft des Übertragungsmediums werden Nachrichten potentiell von allen Netzwerkstationen empfangen, welche sich in der Übertragungsreichweite des Senders aufhalten. Als Konsequenz können bei einem unsynchronisierten Medienzugriff mehrere Nachrichten beim Empfänger kollidieren und nicht korrekt empfangen werden. Dieses Phänomen wird auch als Interferenz bezeichnet. Um solche Interferenzen zu vermeiden, wurden spezielle Protokolle für den Medienzugriff in drahtlosen Netzen entwickelt. Ein solcher Ansatz für drahtlose Maschennetze ist die verteilte Kanalzuweisung. Bei der verteilten Kanalzuweisung werden sich nicht-überlappende Kanäle im verfügbaren Frequenzspektrum für Übertragungen verwendet, die auf dem gleichen Kanal Interferenzen erzeugen würden. Dieser Ansatz ist möglich, da die verwendeten Funktechnologien, wie zum Beispiel IEEE 802.11 (WLAN), mehrere nicht-überlappende Kanäle bereitstellen. Aufgrund der großen Verbreitung von IEEE 802.11, ist eine hohe Dichte von privaten wie kommerziellen Netzen im urbanen Raum die Norm. Diese räumlich überlappenden Netze konkurrieren um den Medienzugriff. Daher ist es für die Leistung von Kanalzuweisungsalgorithmen von großer Bedeutung, die Aktivität der externen Netze mit einzubeziehen. Die Leistung der vorgelegten Arbeit umfasst das Design, die Implementierung und Validierung von Modellen und Algorithmen zur Reduzierung von Interferenzen in drahtlosen Maschennetzen. Die Arbeit beinhaltet die Entwicklung eines Messungs-basierten Interferenzmodells, mit dem Interferenzabhängigkeiten der Maschenrouter untereinander effizient bestimmt werden können. Weiterhin wurde ein Algorithmus für die verteilte Kanalzuweisung entwickelt, der die Aktivität von externen Netzen berücksichtigt. Die Gesamtlösung wurde in einem großen drahtlosen Maschennetz experimentell validiert. / Due to the broadcast nature of the shared medium, wireless transmissions are potentially received by all network stations in the communication range of the sender. With an unsynchronized medium access, multiple transmissions may be active at the same time and thus interfere with each other. In consequence, multiple transmissions may collide at the receiver side and cannot be properly decoded. For this reason, protocols have been developed on the MAC layer to synchronize the medium access and thus reduce interference effects. One of these approaches in wireless mesh networks is channel assignment. The idea of channel assignment is to minimize the network-wide interference by utilizing non-overlapping channels for otherwise interfering wireless transmissions. This is feasible, since wireless mesh routers are usually equipped with multiple radios and commonly used wireless network technologies, such as IEEE 802.11, provide multiple non-overlapping channels. Since IEEE 802.11 operates in the unlicensed frequency spectrum, the dense distribution of private and commercial network deployments of WLANs in urban areas poses a new challenge. Co-located networks compete for the wireless medium, thus decreasing the achievable network performance in terms of throughput and latency. Therefore, an important issue for efficient channel assignment is to also address external interference The contributions of this dissertation comprise the design, implementation, and validation of models and algorithms to enable wireless multi-hop networks to become interference-aware. This includes a measurement-based interference model suitable for large-scale network deployments. A distributed channel assignment algorithm has been developed that considers external sources of interference. The overall solution has been experimentally validated in a large-scale wireless multi-hop multi-radio testbed and has significantly increased the network performance with regard to the network capacity.

Das Ziel dieser Doktorarbeit ist die Berechnung, aus ersten Prinzipien, von Niedrigenenergiekonstanten (NEK), welche die chirale Störungsheorie (ChST) parametrisieren, durch Simulationen auf dem Gitter. Diese Arbeit ist eine Pilotstudie und will deshalb nicht zu definitiven und präzisen quantitativen Vorhersagen führen, sondern wir möchten qualitative Leitlinien für zukünftige genauere Erforschungen der epsilon-Entwicklung der ChST geben. Letztere ist ein Gebiet in dem die chirale Symmetrie wiederhergestellt ist und wo die Compton-Wellenlänge der leichtesten Mesonen grösser als die lineare Dimension des endlichen Volumens ist. Die epsilon-Region ist weiterhin durch die wichtige Rolle der topologischen Ladung, nu, charakterisiert, so dass die Untersuchung der mesonischen Zweipunkt-Korrelationsfunktionen in definierten topologischen Sektoren vorzunehmen ist. Aus diesem Grunde haben wir chirale Fermionen auf dem Gitter simuliert, wobei der overlap Formalismus für den Dirac Operator, mit dem gewöhnliches Wilson Dirac Operator als Kern, in der quenched Approximation genommen wurde. Wir demonstrieren dass der Sektor mit neutraler topologischer Ladung, nu = 0, numerisch sehr schwierig zu untersuchen ist, weil die Daten von erheblichen Spitzen beeinflusst werden, die aufgrund sehr kleiner, nicht verschwindender Eigenwerte herrühren. Diese Beobachtung findet eine Übereinstimmung in einer Studie der Random Matrix Theory (RMT), die besagt, dass man eine Statistik von mehr als 10000 Konfigurationen benötigt, falls man auf kleine Eigenwerte empfindlich reagierende physikalische Grössen, im triviale topologische Sektoren simulieren möchte. Weniger Probleme ergeben sich in dem nicht-trivialen Sektoren |nu| > 0: wir präsentieren deshalb unsere Ergebnisse aus dem topologisches Sektor nu = 1 und den Daten aus das Sektor mit nu = 2 nur als Gegenprobe. Wir zeigen die Existenz einer unteren Schranke für das physikalisches Volumen bei V > 1 fm zur vierten Potenz für die Gültigkeit der ChST, übereinstimmend mit einer vorherigen Beobachtung aus der RMT. Wir beschränken deshalb unsere Untersuchung auf ein grösseres Gitter, wo wir die Daten des axialen Korrelators mit den Vorhersagen der ChST in der Valenzquark-Approximation fitten und eine stabile Bestimmung der gequenchten Pionen-Zerfallskonstante, F, erhalten. Die skalaren und pseudoskalaren Korrelationsfunktionen sind durch mehrere NEK parametrisiert. Dadurch ist der Vergleich mit den Vorhersagen der ChST schwieriger, und deshalb präsentieren wir nur einige Abschätzungen, die mit der entsprechenden Literatur verglichen werden. Zum Schluss präsentieren wir mögliche Implementierungen von verbesserten Algorithmen für die Inversion des overlap Operators, die die Simulationkosten reduzieren. / The aim of this thesis is the computation of Low Energy Constants (LEC) which parameterise Chiral Perturbation Theory (ChPT) from a first principles analysis via lattice simulations. The thesis provides a pilot study and will not give definitive and precise quantitative predictions, but rather our aim is to provide qualitative hints for future accurate investigations of the epsilon-expansion of ChPT, where chiral symmetry is restored and the Compton wavelength of the lightest meson is larger than the linear size of the finite volume. One of the property characterising the epsilon-regime is the important role played by the topological charge, nu, leading to the investigation of the two-point meson correlation functions in distinct topological sectors. To this end, we simulate chiral fermions on the lattice adopting the overlap formalism for the Dirac operator in the quenched approximation, with the kernel provided by the usual Wilson Dirac operator. We demonstrate that the neutral topological sector, nu = 0, is very difficult to explore numerically, as the data are affected by large spikes due to the presence of very small, non-zero eigenvalues. This observation is in agreement with a study of Random Matrix Theory (RMT), which indicates that a statistic of more than 10000 configurations is required when physical quantities sensitive to small eigenvalues are investigated in the neutral topological sector. Therefore, we present our results corresponding to the topological sector nu = 1. Due to the modest statistic, we only use the nu = 2 data as a crosscheck. We find a lower bound on the physical volume V > 1 fm to the four for ChPT to be used, in agreement with a previous observation using RMT. Restricting our attention to a larger lattice, we fit the data of the axial correlation function with the predictions of quenched ChPT, obtaining a stable determination of the quenched pion decay constant, F. The scalar and pseudoscalar correlation functions are parameterised by a larger number of LEC, rendering the comparison with ChPT predictions much more difficult and hence we present only some estimates that are compared with other determinations in the literature. Finally, we present possible implementations of improved algorithms used in the ``inversion'''' of the overlap operator, whose aim is to reduce the computational cost of the simulations.

Die Dissertation behandelt methodische und algorithmische Aspekte der Spektralelementemethode zur räumlichen Diskretisierung partieller Differentialgleichungen. Die Weiterentwicklung einer symmetriebasierten Faktorisierung ermöglicht effiziente Operatoren für Tetraederelemente. Auf Grundlage einer umfassenden Leistungsanalyse werden Engpässe in der Implementierung der Operatoren identifiziert und durch algorithmische Modifikationen der Methode eliminiert.

In this paper we propose an algorithm for solving systems of coupled monotone inclusions in Hilbert spaces. The operators arising in each of the inclusions of the system are processed in each iteration separately, namely, the single-valued are evaluated explicitly (forward steps), while the set-valued ones via their resolvents (backward steps). In addition, most of the steps in the iterative scheme can be executed simultaneously, this making the method applicable to a variety of convex minimization problems. The numerical performances of the proposed splitting algorithm are emphasized through applications in average consensus on colored networks and image classification via support vector machines.