510 Mathematik
Refine
Department, Institute
Document Type
- Article (19)
- Conference Object (15)
- Report (9)
- Part of a Book (7)
- Preprint (4)
- Book (2)
- Doctoral Thesis (1)
Year of publication
Keywords
Das Cutting sticks-Problem ist in seiner allgemeinen Formulierung ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Unter der Annahme, dass P ungleich NP (P != NP) ist, existieren keine effizienten, d.h. polynomiellen Algorithmen zur Lösung des allgemeinen Problems.
In diesem Papier werden Ansätze aufgezeigt, mit denen bestimmte Instanzen des Problems effizient berechnet werden können. Für die Berechnung wichtige Parameter werden charakterisiert und deren Beziehung untereinander analysiert.
Das Cutting sticks-Problem ist in seiner allgemeinen Formulierung ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Unter der Annahme, dass P ungleich NP (P != NP) ist, existieren keine effizienten, d.h. polynomiellen Algorithmen zur Lösung des allgemeinen Problems.
In diesem Papier werden für eine Reihe von Instanzen effiziente Lösungen angegeben.
Das Cutting sticks-Problem ist ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Es werden grundlegende Definitionen für die Behandlung sowie bisherige Ansätze zur Lösung des Problems aufgearbeitet und durch einige neue Aussagen ergänzt. Insbesondere stehen Ideen für eine algorithmische Lösung des Problems bzw. von Varianten des Problems im Fokus.
An Universitäten und Fachhochschulen ist die Mathematik-Ausbildung eines der Nadelöhre für angehende Ingenieurinnen und Ingenieure. Viele Studierende der Ingenieurwissenschaften scheitern in den ersten Studiensemestern an den Anforderungen der Mathematik. Lehrende, Fach- und Hochschuldidaktiker/innen und zunehmend auch Fachvertretungen und Verbände stellen sich die Frage, was an den Fakultäten und Fachbereichen getan werden kann, damit Studierende ihre mathematischen Fähigkeiten vergrößern und den anspruchsvollen Studienweg zur Ingenieurin oder zum Ingenieur meistern können.
We derive rates of convergence for limit theorems that reveal the intricate structure of the phase transitions in a mean-field version of the Blume–Emery–Griffith model. The theorems consist of scaling limits for the total spin. The model depends on the inverse temperature β and the interaction strength K. The rates of convergence results are obtained as (β,K) converges along appropriate sequences (βn,Kn) to points belonging to various subsets of the phase diagram which include a curve of second-order points and a tricritical point. We apply Stein’s method for normal and non-normal approximation avoiding the use of transforms and supplying bounds, such as those of Berry–Esseen quality, on approximation error.
Demand forecast
(2020)
Solving differential-algebraic equations (DAEs) efficiently by means of appropriate numerical schemes for time-integration is an ongoing topic in applied mathematics. In this context, especially when considering large systems that occur with respect to many fields of practical application effective computation becomes relevant. In particular, corresponding examples are given when having to simulate network structures that consider transport of fluid and gas or electrical circuits. Due to the stiffness properties of DAEs, time-integration of such problems generally demands for implicit strategies. Among the schemes that prove to be an adequate choice are linearly implicit Rung-Kutta methods in the form of Rosenbrock-Wanner (ROW) schemes. Compared to fully implicit methods, they are easy to implement and avoid the solution of non-linear equations by including Jacobian information within their formulation. However, Jacobian calculations are a costly operation. Hence, necessity of having to compute the exact Jacobian with every successful time-step proves to be a considerable drawback. To overcome this drawback, a ROW-type method is introduced that allows for non-exact Jacobian entries when solving semi-explicit DAEs of index one. The resulting scheme thus enables to exploit several strategies for saving computational effort. Examples include using partial explicit integration of non-stiff components, utilizing more advantageous sparse Jacobian structures or making use of time-lagged Jacobian information. In fact, due to the property of allowing for non-exact Jacobian expressions, the given scheme can be interpreted as a generalized ROW-type method for DAEs. This is because it covers many different ROW-type schemes known from literature. To derive the order conditions of the ROW-type method introduced, a theory is developed that allows to identify occurring differentials and coefficients graphically by means of rooted trees. Rooted trees for describing numerical methods were originally introduced by J.C. Butcher. They significantly simplify the determination and definition of relevant characteristics because they allow for applying straightforward procedures. In fact, the theory presented combines strategies used to represent ROW-type methods with exact Jacobian for DAEs and ROW-type methods with non-exact Jacobian for ODEs. For this purpose, new types of vertices are considered in order to describe occurring non-exact elementary differentials completely. The resulting theory thus automatically comprises relevant approaches known from literature. As a consequence, it allows to recognize order conditions of familiar methods covered and to identify new conditions. With the theory developed, new sets of coefficients are derived that allow to realize the ROW-type method introduced up to orders two and three. Some of them are constructed based on methods known from literature that satisfy additional conditions for the purpose of avoiding effects of order reduction. It is shown that these methods can be improved by means of the new order conditions derived without having to increase the number of internal stages. Convergence of the resulting methods is analyzed with respect to several academic test problems. Results verify the theory determined and the order conditions found as only schemes satisfying the order conditions predicted preserve their order when using non-exact Jacobian expressions.
Solving differential-algebraic equations (DAEs) efficiently is an ongoing topic in applied mathematics. Applications are given with respect to many fields of practical interest, such as multiphysics problems or network simulations. Due to the stiffness properties of DAEs, linearly implicit Runge-Kutta methods in the form of Rosenbrock-Wanner (ROW) schemes are an appropriate choice for effecitive numerical time-integration. Compared to fully implicit schemes, they are easy to implement and avoid having to solve non-linear equations by including Jacobian information in their formulation explicity. But, especially when having to solve large coupled systems, computing the Jacobian is costly and proves to be a considerable drawback. Inspired by the works of Steihaug and Wolfbrandt [4], we introduce concepts to realize linearly-implicit Runge-Kutta methods for DAEs in the form of so-called W-methods. These schemes allow for arbitrary approximations to given Jacobian entries and, thus, for versatile strategies to reduce computational effort significantly when solving semi-explicit DAE problems of index-1. An approach extending Roche’s procedure [3] will be presented that enables to derive order conditions of the resulting methods by an algebraic theory using rooted trees, a strategy originally introduced by Butcher regarding Runge-Kutta schemes [1,2]. Besides, suitable sets of coefficients for implementing embedded schemes and their potential of increasing efficincy when solving DAEs will be demonstrated.
Network aggregation
(2020)
Since being introduced in the sixties and seventies, semi-implicit RosenbrockWanner (ROW) methods have become an important tool for the timeintegration of ODE and DAE problems. Over the years, these methods have been further developed in order to save computational effort by regarding approximations with respect to the given Jacobian [5], reduce effects of order reduction by introducing additional conditions [2, 4] or use advantages of partial explicit integration by considering underlying Runge-Kutta formulations [1]. As a consequence, there is a large number of different ROW-type schemes with characteristic properties for solving various problem formulations given in literature today.
The simulation of fluid flows is of importance to many fields of application, especially in industry and infrastructure. The modelling equations applied describe a coupled system of non-linear, hyperbolic partial differential equations given by one-dimensional shallow water equations that enable the consistent implementation of free surface flows in open channels as well as pressurised flows in closed pipes. The numerical realisation of these equations is complicated and challenging to date due to their characteristic properties that are able to cause discontinuous solutions.
Simulating free-surface and pressurised flow is important to many fields of application, especially in network approaches. Modelling equations to describe flow behaviour arising in these problems are often expressed by one-dimensional formulations of the hyperbolic shallow water equations. One established approach to realise their numerical computation is the method of lines based on semi-discretisation in space (Steinebach and Rentrop, An adaptive method of lines approach for modeling flow and transport in rivers. In: Vande Wouwer, Saucez, Schiesser (eds) Adaptive method of lines, pp 181–205. Chapman & Hall/CRC, Boca Raton, London, New York, Washington, DC, 2001; Steinebach and Weiner, Appl Numer Math 62:1567–1578, 2012; Steinebach et al., Modeling and numerical simulation of pipe flow problems in water supply systems. In: Martin, Klamroth, et al. (eds) Mathematical optimization of water networks. International series of numerical mathematics, vol 162, pp 3–15. Springer, Basel, 2012). It leads to index-one DAE systems as algebraic constraints are required to realise coupling and boundary conditions of single reaches.Linearly implicit ROW schemes proved to be effective to solve these DAE systems (Steinebach and Rentrop, An adaptive method of lines approach for modeling flow and transport in rivers. In: Vande Wouwer, Saucez, Schiesser (eds) Adaptive method of lines, pp 181–205. Chapman & Hall/CRC, Boca Raton, London, New York, Washington, DC, 2001). However, under certain conditions an extended partial explicit time-integration of the shallow water equations could be worthwhile to save computational effort. To restrict implicit solution by ROW schemes to stiff components while using explicit solution by RK methods for remaining terms, we adapt ROW method ROS34PRW (Rang, J Comput Appl Math 262:105–114, 2014) to an AMF and IMEX combining approach (Hundsdorfer and Verwer, Numerical solution of time-dependent advection-diffusion-reaction equations. Springer, Berlin, Heidelberg, New York, 2003). Applied to first test problems regarding open channel flow, efficiency is analysed with respect to flow behaviour. Results prove to be advantageous especially concerning dynamical flow.
Differential-Algebraic Equations and Beyond: From Smooth to Nonsmooth Constrained Dynamical Systems
(2018)
Seit vielen Jahren ist der Übergang von der Schule zur Hochschule eines der zentralen Themen für didaktische Theorien, empirische Untersuchungen und bildungspolitische Diskussionen. Ein dabei identifiziertes großes Problem vieler Studierender ist, dass mit dem Abitur „eine Lebensphase mit meist klar definierten Zielen in überschaubaren räumlichen, familiären und schulischen Strukturen endet“.1) Entscheidet man sich als Studierender gegen die nicht akademische Laufbahn und nimmt ein Hochschulstudium auf, trifft man auf Studienstrukturen und -bedingungen, die einem fremd und chaotisch vorkommen können. Der Weg an die Hochschulen ermöglicht den Individuen eine Reihe von Optionen, ist aber leider auch immer mit Risiken und Unsicherheiten behaftet. Entscheidungen müssen nun selbstständig vorbereitet und getroffen werden und dies in einem Umfeld, das sehr unterschiedlich im Vergleich zur bekannten Schulstruktur sein kann.
Wissenschaftliches Rechnen
(1999)
Wissenschaftliches Rechnen
(1999)
Two Rosenbrock-Wanner type methods for the numerical treatment of differential-algebraic equations are presented. Both methods possess a stepsize control and an index-1 monitor. The first method DAE34 is of order (3)4 and uses a full semi-implicit Rosenbrock-Wanner scheme. The second method RKF4DA is derived from the Runge-Kutta-Fehlberg 4(5)-pair, where a semi-implicit Rosenbrock-Wanner method is embedded, in order to solve the nonlinear equations. The performance of both methods is discussed in artificial test problems and in technical applications.
The numerical solution of implicit ordinary differential equations arising in vehicle dynamic
(1988)
River alarm systems are designed for the forecasting of water stages during floods or low flow conditions or the prediction of the transport of pollution plumes. The basic model equations are introduced and a Method of Lines approach for their numerical solution is discussed. The approach includes adaptive space-mesh strategies and a Rosenbrock-Wanner scheme for the time integration. It fits into a PC environment and fulfills the requirements on an implementation within river alarm systems.
Die vorliegende Arbeit beschäftigt sich mit der numerischen Behandlung Differential-Algebraischer Gleichungen (DAE" s). DAE" s treten beispielsweise bei der Modellierung der Dynamik mechanischer System, der Schaltkreissimulation sowie der chemischen Reaktionskinetik auf. Es werden Rosenbrock-Wanner ähnliche Verfahren zu deren Lösung hergeleitet und an technischen Modellen (Fahrzeugachse und Verstärker) getestet.
Zur Perzentilberechnung
(1990)
Ein mathematisches Modell zur schiffahrtsbezogenen Wasserstandsvorhersage am Beispiel des Rheins
(1996)
A Method of Lines Flux-Difference Splitting Finite Volume Approach for 1D and 2D River Flow Problems
(2001)
The reliable forecasting of water levels is a very important issue. The modelling approach for water level forecasting at the Middle and Lower River Rhine is based on hydrodynamic river flow models coupled with precipitation-runoff models. The hydrodynamic model is defined by a numerical solution of the one-dimensional (1d) shallow water equations. If flood plains or flood risk maps are important, a two-dimensional (2d) model is required.
In this paper the usage of the Alcrudo-Garcia-Navarro scheme (Alcrudo and Garcia-Navarro, 1993) for 1d and 2d problems within the method of lines framework is described. The scheme is slightly modified, in order to allow a more accurate solution of problems with strong variations in the bottom topography. The problem of drying and re-wetting of mesh-cells is not yet fully sufficiently solved. Numerical results for some test problems and an application to a natural river will be presented.
In this paper an overview on modelling techniques and numerical methods applied to problems in water network simulation is given. The considered applications cover river alarm systems (Rentrop and Steinebach, Surv Math Ind 6:245–265, 1997), water level forecast methods (Steinebach and Wilke, J CIWEM 14(1):39–44, 2000) up to sewer and water supply networks (Steinebach et al., Mathematical Optimization of Water Networks Martin. Springer, Basel, 2012).
The hyperbolic modelling equations are derived from mass and momentum conservation laws. A typical example are the well known Saint-Venant equations. For their numerical solution a conservative semi-discretisation in space by finite differences is proposed. A new well-balanced space discretisation scheme is presented which improves the local Lax-Friedrichs approach applied so far. Higher order discretisations are achieved by WENO methods (Kurganov and Levy, SIAM J Sci Comput 22(4):1461–1488, 2000).
Together with appropriate boundary and coupling conditions this method of lines approach leads to an index-one DAE system. Efficient solution of the DAE system is the topic of Jax and Steinebach (ROW methods adapted to network simulation for fluid flow, in preparation).
For many practical problems an efficient solution of the one-dimensional shallow water equations (Saint-Venant equations) is important, especially when large networks of rivers, channels or pipes are considered. In order to test and develop numerical methods four test problems are formulated. These tests include the well known dam break and hydraulic jump problems and two steady state problems with varying channel bottom, channel width and friction.