G. Mathematics of Computing
Refine
Year of publication
Document Type
- ZIB-Report (46)
- Master's Thesis (6)
- Doctoral Thesis (2)
- In Proceedings (1)
Keywords
- Mixed Integer Programming (5)
- Periodic Timetabling (3)
- MINLP (2)
- PDE (2)
- Periodic Event Scheduling Problem (2)
- SDP (2)
- Ubiquity Generator Framework (2)
- adaptive Newton (2)
- finite element method (2)
- large-scale integer programming (2)
Institute
- Mathematical Optimization (34)
- Numerical Mathematics (10)
- Network Optimization (7)
- Mathematical Optimization Methods (5)
- Applied Algorithmic Intelligence Methods (4)
- Computational Medicine (3)
- Computational Molecular Design (3)
- Computational Nano Optics (3)
- Computational Systems Biology (1)
- Energy Network Optimization (1)
Reconstruction of photonic crystal geometries using a reduced basis method for nonlinear outputs
(2016)
Maxwell solvers based on the hp-adaptive finite element method allow for accurate geometrical modeling and high numerical accuracy. These features are indispensable for the optimization of optical properties or reconstruction of parameters through inverse processes. High computational complexity prohibits the evaluation of the solution for many parameters. We present a reduced basis method (RBM) for the time-harmonic electromagnetic scattering problem allowing to compute solutions for a parameter configuration orders of magnitude faster. The RBM allows to evaluate linear and nonlinear outputs of interest like Fourier transform or the enhancement of the electromagnetic field in milliseconds. We apply the RBM to compute light-scattering off two dimensional photonic crystal structures made of silicon and reconstruct geometrical parameters.
Model order reduction for the time-harmonic Maxwell equation applied to complex nanostructures
(2016)
Fields such as optical metrology and computational lithography require fast and efficient methods for solving
the time-harmonic Maxwell’s equation. Highly accurate geometrical modeling and numerical accuracy atcomputational costs are a prerequisite for any simulation study of complex nano-structured photonic devices.
We present a reduced basis method (RBM) for the time-harmonic electromagnetic scattering problem based
on the hp-adaptive finite element solver JCMsuite capable of handling geometric and non-geometric parameter
dependencies allowing for online evaluations in milliseconds. We apply the RBM to compute light-scatteringoptical wavelengths off periodic arrays of fin field-effect transistors (FinFETs) where geometrical properties such
as the width and height of the fin and gate can vary in a large range.
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.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
Bei der numerischen Lösung von Optimalsteuerungsproblemen mit
elliptischen partiellen Differentialgleichungen als Nebenbedingung
treten unvermeidlich Diskretisierungs- und Iterationsfehler auf.
Man ist aus Aufwandsgründen daran interessiert die dabei entstehenden
Fehler nicht sehr klein wählen zu müssen. In der Folge werden die linearisierten Nebenbedingungen in einem Composite-Step-Verfahren nicht exakt erfüllt. In dieser Arbeit wird der Einfluss dieser Ungenauigkeit auf das Konvergenzverhalten von Newton-Lagrange-Verfahren untersucht.
Dabei sollen mehrere einschlägige lokale Konvergenzresultate diskutiert werden.
Anschließend wird ein konkretes Composite-Step-Verfahren formuliert, in dem die Genauigkeit der
inneren Iterationsverfahren adaptiv gesteuert werden kann.
Am Ende der Arbeit wird an zwei Musterproblemen die hohe Übereinstimmung der analytischen
Voraussagen und der tatsächlichen Performanz der dargestellten Methoden demonstriert.
We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps.
Contemporary supercomputers can easily provide years of
CPU time per wall-clock hour. One challenge of today's software
development is how to harness this wast computing power in order to solve
really hard mixed integer programming instances. In 2010, two out of
six open MIPLIB2003 instances could be solved by ParaSCIP in more than
ten consecutive runs, restarting from checkpointing files.
The contribution of this paper is threefold:
For the first time, we present computational results of single runs for
those two instances. Secondly, we provide new improved upper and lower
bounds for all of the remaining four open MIPLIB2003 instances.
Finally, we explain which new developments led to these results and
discuss the current progress of ParaSCIP. Experiments were conducted on
HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.
This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.
Trajectory- or mesh-based methods for analyzing the dynamical behavior of large molecules tend to be impractical due to the curse of dimensionality - their computational cost increases exponentially with the size of the molecule. We propose a method to break the curse by a novel square root approximation of transition rates, Monte Carlo quadrature and a discretization approach based on solving linear programs. With randomly sampled points on the molecular energy landscape and randomly generated discretizations of the molecular configuration space as our initial data, we construct a matrix describing the transition rates between adjacent discretization regions. This transition rate matrix yields a Markov State Model of the molecular dynamics. We use Perron cluster analysis and coarse-graining techniques in order to identify metastable sets in configuration space and approximate the transition rates between the metastable sets. Application of our method to a simple energy landscape on a two-dimensional configuration space provides proof of concept and an example for which we compare the performance of different discretizations. We show that the computational cost of our method grows only polynomially with the size of the molecule. However, finding discretizations of higher-dimensional configuration spaces in which metastable sets can be identified remains a challenge.