TY - THES A1 - Frech, Ralf T1 - Das Konzept der Flussdichte und sein Bezug zur Bohmschen Mechanik Y1 - 2014 ER - TY - THES A1 - Tumescheit, Charlotte T1 - Using Birkhoff-von Neumann und Sinkhorn Algorithm to Find Dominating Cycles Y1 - 2014 ER - TY - THES A1 - Günther, Matthias T1 - Implementation and verification of methods for the validation of knee joint kinematics KW - Biomechanics Y1 - 2014 ER - TY - THES A1 - Gutsche, Philipp T1 - Convergence Study of the Fourier Modal Method for Nano-optical Scattering Problems in Comparison with the Finite Element Method N2 - Nano-optical scattering problems play an important role in our modern, technologically driven society. Computers, smartphones and all kinds of electronic devices are manufactured by the semiconductor industry which relies on production using photomasks as well as optical process control. The digital world, e.g. the world wide web, is based on optical interconnects and so-called quantum computers based on optics are supposed to be next generation computers. Moreover, global economic progress demands new and sustainable energy resources and one option is to make use of the power stored in optical radiation from the sun. Additionally, understanding fundamental physics such as the optical properties of asymmetric, or chiral, structures could promote future innovations in engineering. In order to understand and manipulate these kinds of processes, physics provides a well established model: the so-called Maxwell’s equations. Stated by James Clerk Maxwell in 1862, this description of the interaction of light and matter still provides a profound basis for the analysis of electromagnetic phenomena. However, real world problems cannot be calculated using simple mathematics. Rather, computer simulations are needed to obtain solutions of the physical model. Finding suitable methods to solve these problems opens up a wide variety of possibilities. On the one hand, there are methods which require long computing times. On the other hand, some algorithms depend on high memory usage. That is why the field of numerics deals with the question which method is optimally suited for specific problems. The aim of this work is to investigate the applicability of the so-called Fourier Modal Method (FMM) to nano-optical scattering problems in general. Since simple analytical solutions are non-existent for most recent physical problems, we use the Finite Element Method (FEM) to double-check performance of the FMM. Mathematics provide reliable procedures to control the errors of numerics using the FEM. Yet up to now it has not been possible to rigorously classify the quality of the Fourier Modal Method’s results. It is not fully understood whether the process of investing more and more computing resources yields more accurate results. So, we have to ask ourselves: does the numerical method invariably converge? In spite of this uncertainty when using the FMM, it is a well established method dating back to the 1980s. This numerical method has recently been used to optimize performance of solar cells [19] as well as to improve the optical properties of so-called single-photon sources [41] which are essential for quantum cryptography. The latter is a promising candidate to increase digital security and revolutionise cryptography techniques. Furthermore, with the help of the Fourier Modal Method an important issue in optics has been partly resolved: angular filtering of light was made possible by using a mirror which becomes transparent at a certain viewing angle [77]. In addition, an improved numerical technique to design so-called Photonic Crystal waveguides based on the FMM was developed recently [15]. Photonic Crystals are used in the fields of optical bio-sensing and for the construction of novel semiconductor devices. Moreover, approaches to link the FMM and the FEM try to combine advantages of both methods to obtain fast and accurate results [81]. These ideas are closely linked to the well-known concept of Domain Decomposition within the FEM [88]. Here, one possibility to couple domains is to use the scattering matrix formalism as it is done in the FMM. In the scope of this convergence study, we state Maxwell’s equations, particularly for periodic geometries. We describe two physical phenomena of nano-optics, namely chirality and opto-electrical coupling, and define the errors of our simulations. Afterwards, the two investigated methods are analysed with respect to their general properties and a way to unify modelling physics when using both algorithms is presented. With the help of various numerical experiments, we explore convergence characteristics of the FMM and draw conclusions about the ability of this approach to provide accurate results and, consequently, its potential for research on technological innovations. KW - Nano-optics KW - Fourier Modal Method (FMM) KW - Rigorous Coupled Wave Analysis (RCWA) KW - Finite Element Method (FEM) Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56084 ER - TY - THES A1 - Knötel, David T1 - Segmentation of ray and shark tesserae N2 - Rays and sharks are cartilaginous fishes. Most of the cartilaginous skeleton is covered with calcified tiles to improve the stability of the skeleton. These tiles are called tesserae and enclose areas of uncalcified cartilage. Because of the special properties of the tesserae, biologists are interested to understand shape and structure of tessellated cartilage. This thesis presents a segmentation pipeline for the separation of tesserae on the cartilaginous skeleton of rays and sharks. The segmentation pipeline consists of an automatic initial segmentation step followed by manual error corrections by the user. The initial segmentation is based on the contour tree data structure that tracks the evolution of level sets in a dataset during iso-value changes. The presented segmentation concepts are not limited to the segmentation of tesserae but also viable for similar kinds of tiled structures. The input datasets are given as micro-CT scans. The contribution of this thesis is the development of a segmentation pipeline. The pipeline uses a newly developed fast version of the contour-tree-based segmentation algorithm that, after a preprocessing step, does not need to iterate over all voxels in the dataset. Visualizations and computations are done with the software system ZIBAmira. Used algorithms are either implemented as new ZIBAmira modules or they extend already existing ZIBAmira modules. KW - segmentation, contour tree, watershed, distance map Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54429 ER - TY - THES A1 - Hendel, Gregor T1 - Empirical Analysis of Solving Phases in Mixed Integer Programming N2 - Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process. KW - mixed-integer programming KW - branch-and-cut Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54270 ER - TY - THES A1 - Witzig, Jakob T1 - Reoptimization Techniques in MIP Solvers N2 - Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems. In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence. At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this thesis, 2013. Since most of the state-of-the-art MIP solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54067 ER - TY - THES A1 - Sniegula, Erik T1 - Histogram-based Visualization and Analysis of Vector Fields using Stream Line Projection Plots N2 - Field lines in vector fields, e.g. stream lines, path lines, streak lines or time lines, play an important role in the analysis of vector fields. They improve the classification of flow features and its characteristics in particular. Because of the variety of structural information in field lines the effective processing, analysis and visualization play an important role. More effective techniques may contribute to an improved understanding of struc- tural phenomena in a wide range of applications of vector field visualization, such as gaseous flow (e.g. development of cars and aircrafts), design of machines (e.g. turbines), chemistry (e.g. simulation of molecules) and fluid flow in technical or medical applications (e.g. bloodvessel and ocean simulations). This master thesis focuses on the histogram-based visualization and analysis of vec- tor fields using field line projection plots, stream lines in particular. The goal of this work is to develop a hand full of selection criteria to answer specific applica- tion relevant questions about the characteristics and structures of their vector fields. Therefore we present a powerful analysis tool for vector fields or more precisely for their field lines. KW - Vector Field Visualization, Trajectory Visualization Y1 - 2014 ER - TY - THES A1 - von Hafe Pérez Ferreira da Silva, Maria Isabel T1 - Computational Left-Ventricle Reconstruction from MRI Data for Patient-specific Cardiac Simulations Y1 - 2014 ER - TY - THES A1 - Kulagina, Svetlana T1 - Distributed Multi-Stage Time Series Similarity Search Y1 - 2014 ER - TY - THES A1 - Fajerski, Jan T1 - Map Reduce on Distributed Hash Tables Y1 - 2014 ER - TY - THES A1 - Amiranashvili, Tamaz T1 - Fitting Smooth Strips to Rough Surfaces Y1 - 2014 ER - TY - THES A1 - Hoppmann, Heide T1 - A Configuration Model for the Line Planning Problem N2 - In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented. N2 - Das Linienplanungsproblem ist ein wichtiges Teilproblem der Angebotsplanung im öffentlichen Nahverkehr. Dabei werden Routen und Betriebsfrequenzen von Linien in einem gegebenen Infrastrukturnetzwerk gesucht, sodass ein gegebener Beförderungsbedarf gedeckt wird und die Kosten minimal sind. Praktische Ansätze zum Lösen dieser Probleme beruhen auf ganzzahliger Programmierung. Ein Schwachpunkt klassischer Modelle ist, dass schon kleine Änderungen der Eingabeparameter eine Vergrößerung oder Verkleinerung der Menge der zulässigen fraktionalen Lösungen bewirken können, auch wenn die Menge der ganzzahligen Lösungen unverändert bleibt. Wir betrachten in dieser Arbeit einen neuen kombinatorischen Ansatz, welcher die Möglichkeiten den Bedarf auf einer Verbindung im Netzwerk mit Frequenzen zu überdecken mit Hilfe von diskreten "Konfigurationen" beschreibt und dieses Problem eliminiert. Um die Vorteile dieses Konfigurationsmodells aufzuzeigen, vergleichen wir es mit einem klassischen Ansatz, den wir Standardmodell nennen. Wir zeigen, dass das Konfigurationsmodell mehrere facettendefinierende Ungleichungen des Standardmodells impliziert: Setcover-, symmetrische Band-, Multicover- und MIR-Ungleichungen. Diese theoretischen Ergebnisse können wir mit Rechenergebnissen bestätigen. Um die Anzahl dieser Variablen auch für große Instanzen zu beschränken, schlagen wir ein weiteres Modell vor, welches nur eine Teilmenge der Konfigurationsvariablen enthält. Dieses stellt sich als ein sehr guter Kompromiss zwischen der Größe und der Stärke des Modells heraus. Da das Linienplanungsproblem eine Spezialisierung des Netzwerkdesignproblems ist, können unsere Methoden auch auf andere Problemklassen übertragen werden. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51610 ER - TY - THES A1 - Ruthenberg, Gunnar T1 - Hybrid Transactions for Intel’s Transactional Synchronization Extensions Y1 - 2014 N1 - Es handelt sich um eine Diplomarbeit ER - TY - THES A1 - Michels, Maximilian T1 - Request-Based Load Balancing in Distributed Hash Tables Y1 - 2014 ER - TY - THES A1 - Walther, Tom T1 - A SCIP Constraint Handler for Piecewise Linear Functions N2 - In this thesis, we study different modelling approaches for piecewise linear functions, in particular with respect to their occurrence in mathematical optimization problems. Reviewing the quality of the classical MIP models from the literature, we will see that all but the disaggregated convex combination method yield both sharp and locally ideal formulations. In the main part, we will present an alternative approach for modelling constraints involving piecewise linear functions, based on ideas of constraint programming and using a convex hull relaxation. For the purpose of developing a branch-and-bound procedure specifically adapted to our constraint formulation within SCIP, all required components such as propagation, branching and separation will be discussed. In particular, we will focus on adapting well-known MIP strategies for the selection of branching variables to our type of piecewise linear constraints. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49112 ER - TY - THES A1 - Knöchel, Jane T1 - Mathematische Modellierung metabolischer Einflussfaktoren auf den Milchkuhzyklus N2 - In den letzten Jahren ist die reproduktive Leistung von Milchkühen parallel zur steigenden Milchleistung drastisch gesunken. Um die zu Grunde liegenden biologischen Mechanismen besser zu verstehen, wurde in dieser Arbeit eine Modellerweiterung des vorhandenen Modells von Stötzel et al. (2011) um metabolische Einflussfaktoren angestrebt. Hierfür wurde zuerst aus veröffentlichten, experimentell gewonnen Erkenntnissen herausgearbeitet, wie die metabolischen Faktoren auf das periodische Zyklusverfahren der Milchkuh Einfluss nehmen. Daraus wurde ersichtlich, dass Glukose, Insulin und IGF-I die wichtigsten metabolischen Faktoren sind, aber lediglich IGF-I als dynamische Größe in das Modell eingeht. Zur Validierung des erweiterten Modells, wurden im Rahmen dieser Arbeit Szenarien aus der Literatur entwickelt, welche eine negative Energiebilanz oder den Effekt von Diätrestriktionen auf den Milchkuhzyklus simulieren sollten. Ferner wurden Messdaten für IGF, E2 und P4 von Kawashima et al. (2007) und Cerri et al. (2011) bereit gestellt. Das erweiterte Modell umfasst lediglich 8 Parameter mehr als das Ursprungsmodell, wobei gezeigt werden konnte, dass weder die Bedingung für die Lösbarkeit noch die Stabilität in den Anfangswerten eingebüßt wurde. Die Modellkurven konnten mittels des NLSCON erfolgreich an die bereitgestellten Messdaten für IGF, E2 und P4 angepasst werden. Anhand der Ergebnisse aus den Szenarien ließ sich zeigen, dass es teilweise gelingt über die metabolischen Einflussfaktoren eine negative Energiebilanz für unterernährte Kühe darzustellen. Die Rückführung in das periodische Zyklusverhalten verlief jedoch im Vergleich zu in vivo Beobachtungen zu schnell ab. Eine mögliche Erklärung hierfür ist ein zu geringer Einfluss von IGF-I auf das Modell. Darüber hinaus kam es trotz (stark) reduzierter LH-Konzentration zur Ovulation. Auf diesen Erkenntnissen aufbauend könnte in Zukunft die Follikelmodellierung modifiziert oder die Hillfunktion, die die Ovulation darstellt, überarbeitet werden. N2 - During the last few years there has been a drastic decline in the fertility of dairy cows. Therefore the goal of this work is to identify the underlying mechanisms for this problem by extending the model from Stötzel et al. (2011) to include the influence of metabolic factors. For this purpose the influence of the metabolic factors was determined based on published, experimentally obtained findings. The important metabolic factors were glucose, insulin and IGF-I, but only IGF-I was shown to be dynamic over the course of a cycle and therefore implemented into the model. To validate the chosen model extension we developed scenarios from the literature in order to simulate the impact of negative energy balance as well as the effect of diet restrictions on the bovine oestrous cycle. Furthermore we got measurement data from Kawashima et al. (2007) and Cerri et al. (2011) for IGF, E2 and P4. The new model has just 8 parameters more, while maintaining the same solvability and stability in the initial values. It was possible to fit the model with the use of NLSCON to the measurement data for IGF, E2 and P4. In addition the scenarios allowed us to show that the model is able to simulate a negative energy balance in parts. Merely the return into the cyclic behaviour was faster than observed in vivo. One possible explanation would be, that the influence of IGF-I on the model is not strong enough. The model showed a deficit while simulating the scenarios since a marked reduction of the LH concentration still led to ovulation. Thus future research could be done in this direction, where it would probably be necessary to modify the follicle function or the hill function responsible for ovulation. KW - Systembiologie Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-46170 N1 - Diplomarbeit ER -