TY - GEN A1 - Deuflhard, Peter T1 - A Note on Extrapolation Methods for Second Order ODE Systems. N2 - A slight modification of the extended Stoermer discretization for non self-adjoint second order ODE systems is derived on the basis of a simple stability analysis. This discretization easily extends to implicit ODE systems, which are known to arise e.g. in mechanical engineering. In addition, a special variant of semi-implicit Euler discretization is proposed, which essentially treats the state variables explicitly, but their derivatives implicitly. Numerical tests over critical parameter values of the van der Pol oscillator illustrate the domain of efficiency of the suggested discretizations. T3 - ZIB-Report - SC-87-05 Y1 - 1987 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79 ER - TY - GEN A1 - Yserentant, Harry T1 - Preconditioning Indefinite Discretization Matrices. N2 - The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can be used also for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case. {\bf Keywords: }Preconditioned conjugate gradient methods, finite elements. {\bf Subject Classification: } AMS(MOS):65F10, 65N20, 65N30. T3 - ZIB-Report - SC-87-06 KW - preconditioned conjugate gradient methods KW - finite elements Y1 - 1987 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81 ER - TY - GEN A1 - Neun, Winfried A1 - Melenk, Herbert T1 - Implementation of the LISP-Arbitrary Precision Arithmetic for a Vector Processor. N2 - Portable Standard LISP (PSL, Version 3.4) and REDUCE 3 were implemented for CRAY1 and Cray X- MP computers at the Konrad-Zuse-Zentrum Berlin in 1986. As an special aspect of the implementation of PSL, an interface to the vector hardware of CRAY processors was defined. With that interface and mostly driven by the needs of REDUCE applications (e.g. extensive calculations of Gröbner bases), the arbitrary precision integer arithmetic of PSL was rebuild using full power of the vector hardware. A modular arithmetic using vector hardware was also constructed. T3 - ZIB-Report - SC-88-01 Y1 - 1988 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93 ER - TY - GEN A1 - Melenk, Herbert A1 - Möller, H. Michael A1 - Neun, Winfried T1 - On Gröbner Bases Computation on a Supercomputer Using REDUCE. N2 - Gröbner bases are the main tool for solving systems of algebraic equations and some other problems in connection with polynomial ideals using Computer Algebra Systems. The procedure for the computation of Gröbner bases in REDUCE 3.3 has been modified in order to solve more complicated algebraic systems of equations by some general improvements and by some tools based on the specific resources of the CRAY X-MP. We present this modification and illustrate it by examples. T3 - ZIB-Report - SC-88-02 Y1 - 1988 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-107 ER - TY - GEN A1 - Schütte, Christof A1 - Nettesheim, Peter T1 - Non-Adiabatic Effects in Quantum-Classical Molecular Dynamics N2 - In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The article is concerned with the so-called QCMD model. This model describes most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of a wavefunction. We review the conditions under which the QCMD model is known to approximate the full quantum dynamical evolution of the system. In most quantum-classical simulations the {\em Born-Oppenheimer model} (BO) is used. In this model, the wavefunction is adiabatically coupled to the classical motion which leads to serious approximation deficiencies with respect to non-adiabatic effects in the fully quantum dynamical description of the system. In contrast to the BO model, the QCMD model does include non-adiabatic processes, e.g., transitions between the energy levels of the quantum system. It is demonstrated that, in mildly non-adiabatic scenarios, so-called {\em surface hopping} extensions of QCMD simulations yield good approximations of the non-adiabatic effects in full quantum dynamics. The algorithmic strategy of such extensions of QCMD is explained and the crucial steps of its realization are discussed with special emphasis on the numerical problems caused by highly oscillatory phase effects. T3 - ZIB-Report - SC-98-38 KW - quantum-classical molecular dynamics KW - non-adiabatic processes KW - Schrödinger equation KW - highly oscillatory phase KW - adiabatic limit KW - quantum adiabati Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3817 ER - TY - GEN A1 - Stalling, Detlev A1 - Zöckler, Malte A1 - Sander, Oliver A1 - Hege, Hans-Christian T1 - Weighted Labels for 3D Image Segmentation N2 - Segmentation tools in medical imaging are either based on editing geometric curves or on the assignment of region labels to image voxels. While the first approach is well suited to describe smooth contours at subvoxel accuracy, the second approach is conceptually more simple and guarantees a unique classification of image areas. However, contours extracted from labeled images typically exhibit strong staircase artifacts and are not well suited to represent smooth tissue boundaries. In this paper we describe how this drawback can be circumvented by supplementing region labels with additional weights. We integrated our approach into an interactive segmentation system providing a well-defined set of manual and semi-automatic editing tools. All tools update both region labels as well as the corresponding weights simultaneously, thus allowing one to define segmentation results at high resolution. We applied our techniques to generate 3D polygonal models of anatomical structures. T3 - ZIB-Report - SC-98-39 KW - image processing KW - segmentation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3828 ER - TY - THES A1 - Stalling, Detlev T1 - Fast Texture-Based Algorithms for Vector Field Visualization N2 - In this thesis we develop new methods for visualizing vector fields which specifically address three design goals: accuracy, performance, and cognition. Our methods will be general-purpose and can be applied to arbitrary vector fields in two- and three-dimensional space. The methodology behind our approach is {\em texture-based visualization}. Texture-based visualization methods imitate techniques known from experimental flow visualization, namely, the observation of randomly dispersed particles or dye injection patterns. Instead of depicting individual lines or symbols, a contiguous high-resolution image or texture is generated. This texture clearly reveals the directional structure of the field. In this way intuitive insight can be obtained and even small details of the field become visible. However, it remains unclear what kind of textures are best suited for our purpose. How do we generate them? Can we apply these methods in three-dimensional space? In particular, we focus on a technique known as {\em line integral convolution} or LIC. This method turns out to be quite versatile and well-suited for visualizing many interesting vector fields. LIC images display the integral curves or field lines of a vector field at high spatial resolution. Although conceptually quite simple, line integral convolution implies a number of interesting mathematical and algorithmic questions. T3 - ZIB-Report - SC-98-40 KW - computer graphics KW - line integral convolution KW - stream surfaces Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3838 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Strubbe, Uwe A1 - Völker, Manfred T1 - Zielorientierte Dienstplanoptimierung N2 - Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im ÖPNV. Der Ansatz zielt auf die vollständige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Berücksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenwärtig in einem vom Bundesministerium für Bildung und Forschung ({\tt bmb+f}) geförderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum für Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben über eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten über den Stand der Entwicklung. T3 - ZIB-Report - SC-98-41 KW - Dienstplanung KW - Optimierung KW - Zielorientierte Planung Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3847 ER - TY - GEN A1 - Best, Christoph A1 - Hege, Hans-Christian T1 - Visualizing conformations in molecular dynamics N2 - The Monte Carlo simulation of the dynamics of complex molecules produces trajectories with a large number of different configurations to sample configuration space. It is expected that these configurations can be classified into a small number of conformations representing essential changes in the shape of the molecule. We present a method to visualize these conformations by point sets in the plane based on a geometrical distance measure between individual configurations. It turns out that different conformations appear as well-separated point sets. The method is further improved by performing a cluster analysis of the data set. The point-cluster representation is used to control a three-dimensional molecule viewer application to show individual configurations and conformational changes. The extraction of essential coordinates and visualization of molecular shape is discussed. T3 - ZIB-Report - SC-98-42 KW - Molecular Dynamics KW - Conformations KW - Visualization KW - Cluster Analysis Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3859 ER - TY - GEN A1 - Athanasiadis, Christos A. A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes II N2 - Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d < d' < n$. T3 - ZIB-Report - SC-98-43 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3862 ER - TY - GEN A1 - Huber, Birkett A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings N2 - In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos. T3 - ZIB-Report - SC-98-44 KW - Polyhedral subdivision KW - fiber polytope KW - mixed subdivision KW - lifting subdivision KW - Minkowski sum KW - Cayley Trick KW - Bohne-Dress Theorem Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3874 ER - TY - GEN A1 - Schütte, Christof A1 - Fischer, Alexander A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - A Direct Approach to Conformational Dynamics based on Hybrid Monte Carlo N2 - Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of $T$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted. T3 - ZIB-Report - SC-98-45 KW - conformation KW - conformational dynamics KW - hybrid Monte Carlo KW - reweighting KW - essential degrees of freedom KW - transition probabilities KW - Markov operator Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3889 ER - TY - GEN A1 - Wolf, Thomas T1 - A comparison of four approaches to the calculation of conservation laws N2 - The paper compares computational aspects of four approaches to compute conservation laws of single differential equations or systems of them, ODEs and PDEs. The only restriction, required by two of the four corresponding computer algebra programs, is that each DE has to be solvable for a leading derivative. Extra constraints may be given. Examples of new conservation laws include non-polynomial expressions, an explicit variable dependence and conservation laws involving arbitrary functions. Examples involve the following equations: Ito, Liouville, Burgers, Kadomtsev-Petviashvili, Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney. T3 - ZIB-Report - SC-99-01 Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3896 ER - TY - GEN A1 - Sokolov, Vladimir V. A1 - Wolf, Thomas T1 - A symmetry test for quasilinear coupled systems N2 - It is well known that the following class of systems of evolution equations \begin{eqnarray} \label{nsgen} \cases{ u_{t}=u_{xx}+F(u,v,u_x,v_x),\cr v_{t}=-v_{xx}+G(u,v,u_x,v_x),\cr} \end{eqnarray} is very rich in integrable cases. The complete classification problem is very difficult. Here we consider only the most interesting (from our opinion) subclass of systems (1). Namely, we consider equations linear in all derivatives of the form \begin{eqnarray} \label{kvazgen} \cases{ u_t = u_{xx} + A_{1}(u,v) u_x + A_{2}(u,v) v_x + A_{0}(u,v)\cr v_t = - v_{xx} + B_{1}(u,v) v_x + B_{2}(u,v) u_x + B_{0}(u,v). \cr} \end{eqnarray} without any restrictions on the functions $A_{i}(u,v), B_{i}(u,v)$. T3 - ZIB-Report - SC-99-02 Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3901 ER - TY - GEN A1 - Nettesheim, Peter A1 - Schütte, Christof T1 - Numerical Integrators for Quantum-Classical Molecular Dynamics N2 - It was revealed that the QCMD model is of canonical Hamiltonian form with symplectic structure, which implies the conservation of energy. An efficient and reliable integrator for transfering these properties to the discrete solution is the symplectic and explicit {\sc Pickaback} algorithm. The only drawback of this kind of integrator is the small stepsize in time induced by the splitting techniques used to discretize the quantum evolution operator. Recent investigations concerning Krylov iteration techniques result in alternative approaches which overcome this difficulty for a wide range of problems. By using iterative methods in the evaluation of the quantum time propagator, these techniques allow for the stepsize to adapt to the coupling between the classical and the quantum mechanical subsystem. This yields a drastic reduction of the numerical effort. The pros and cons of both approaches as well as the suitable applications are discussed in the last part. T3 - ZIB-Report - SC-97-42 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3111 ER - TY - GEN A1 - Ehrig, Rainald A1 - Nowak, Ulrich A1 - Deuflhard, Peter T1 - Massively Parallel Linearly-Implicit Extrapolation Algorithms as a Powerful Tool in Process Simulation. N2 - We study the parallelization of linearly--implicit extrapolation codes for the solution of large scale PDE systems and differential algebraic equations on distributed memory machines. The main advantage of these algorithms is that they enable adapativity both in time and space. Additive Krylov--Schwarz methods yield high parallel perfomance for such extrapolation methods. Our approach combines a slightly overlapping domain decomposition together with a polynomial block Neumann preconditioner and a reduced system technique. Furthermore we get important advantages through the explicit computation of the matrix--products of the preconditioner and the matrix of the linear system. The parallel algorithms exhibit scalability up to 64 processors already for medium--sized test problems. We show that the codes are really efficient in large application systems for chemical engineering problems. T3 - ZIB-Report - SC-97-43 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3127 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Globally Convergent Multigrid Methods for Porous Medium Type Problems N2 - We consider the fast solution of large, piecewise smooth minimization problems as typically arising from the finite element discretization of porous media flow. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with {\em constrained} Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give logarithmic upper bounds for the asymptotic convergence rates. T3 - ZIB-Report - SC-97-45 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3142 ER - TY - GEN A1 - Wagler, Annegret T1 - Critical Edges in Perfect Graphs and Some Polyhedral Consequences N2 - An edge $e$ of a perfect graph $G$ is called critical if $G-e$ is imperfect. For certain graphs $G-e$ of this type, we determine all minimally imperfect subgraphs. We use this knowledge to describe inequalities inducing facets of the stable set polytope associated with $G-e$.\\ T3 - ZIB-Report - SC-97-46 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3153 ER - TY - GEN A1 - Lang, Jens A1 - Merz, Wilhelm T1 - Numerical Simulation of Single Species Dopant Diffusion in Silicon under Extrinsic Conditions N2 - In this article we consider a general model for phosphorus diffusion in silicon under extrinsic doping conditions. At such high concentrations we have to include the charged species and the internal electric field of the crystal, both of which can have profound effects on diffusion. In principle, this leads to a very large number of drift--diffusion--reaction equations: one for each charge state of every species, plus one Poisson equation to describe the internal electric field (in terms of the electron/hole concentration). The number of equations can be reduced substantially by making additional assumptions on the distribution of charge states and local equilibrium assumptions concerning the reaction terms. The resulting model turns out to be very interesting for numerical investigation. We solve the problem numerically in two space dimensions with the adaptive finite element program KARDOS and describe the numerical method used here to treat the resulting drift--diffusion--reaction problem. T3 - ZIB-Report - SC-97-47 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3163 ER - TY - THES A1 - Bornemann, Folkmar A. T1 - Homogenization in Time of Singularly Perturbed Conservative Mechanical Systems N2 - We present a particular method for the explicit elimination of rapidly oscillating micro-scales in certain singularly perturbed conservative mechanical systems. Non-linear effects call for a non-trivial averaging procedure that we call {\em homogenization in time.} This method is based on energy principles and weak convergence techniques. Since non-linear functionals are in general {\em not} weakly sequentially continuous, we have to study {\em simultaneously} the weak limits of all those non-linear quantities of the rapidly oscillating components which are of importance for the underlying problem. Using the physically motivated concepts of {\em virial theorems}, {\em adiabatic invariants}, and {\em resonances}, we will be able to establish sufficiently many relations between all these weak limits, allowing to calculate them explicitly. Our approach will be {\em paradigmatical} rather than aiming at the largest possible generality. This way, we can show most clearly how concepts and notions from the physical background of the underlying mathematical problem enter and help to determine relations between weak limit quantities. In detail we will discuss natural mechanical systems with a strong constraining potential on Riemannian manifolds, the questions of realization of holonomic constraints, and singular limits of mixed quantum-classical coupling models. This latter class of problems also leads to a new proof for the adiabatic theorem of quantum mechanics. The strength of our methodology will be illustrated by applications to problems from plasma physics, molecular dynamics and quantum chemistry. T3 - ZIB-Report - SC-97-48 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3170 ER - TY - GEN A1 - Reich, Sebastian T1 - Modified potential energy functions for constrained molecular dynamics N2 - In molecular dynamics the highly oscillatory vibrations in the chemical bonds are often replaced by holonomic constraints that freeze the bond length/angle to its equilibrium value. In some cases this approach can be justified if the force constants of the bond vibrations are sufficiently large. However, for moderate values of the force constant, the constrained system might lead to a dynamical behavior that is too ``rigid'' compared to the flexible model. To compensate for this effect, the concept of soft constraints was introduced [Reich 1997, Reich 1995, Reich 1996]. However, its implementation is rather expensive. In this paper, we suggest an alternative approach that modifies the force field instead of the constraint functions. This leads to a more efficient method that avoids the resonance induced instabilities of multiple-time-stepping [Bishop 1996] and the above described effect of standard constrained dynamics. T3 - ZIB-Report - SC-97-49 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3189 ER - TY - GEN A1 - Ascher, Uri A1 - Reich, Sebastian T1 - On some difficulties in integrating highly oscillatory Hamiltonian systems N2 - The numerical integration of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or Hamiltonian partial differential equations, is a challenging task. Various methods have been suggested to overcome the step-size restrictions of explicit methods such as the Verlet method. Among these are multiple-time-stepping, constrained dynamics, and implicit methods. In this paper, we investigate the suitability of time-reversible, semi-implicit methods. Here semi-implicit means that only the highly oscillatory part is integrated by an implicit method such as the midpoint method or an energy-conserving variant of it. The hope is that such methods will allow one to use a step-size $k$ which is much larger than the period $\varepsilon$ of the fast oscillations. However, our results are discouraging. Even in the absence of resonance-type instabilities, we show that in general one must require that $k^2/\varepsilon$ be small enough. Otherwise the method might become unstable and/or it might lead to a wrong approximation of the slowly varying solution components. The latter situation might, in some cases, even require that $k/\varepsilon$ be small in order to avoid this danger. While certain (semi-implicit) energy conserving methods prove to be robust for some model problems, they may also yield deceptively-looking, wrong solutions for other simple model problems, in circumstances where the corresponding constrained dynamics formulation may not be easily derived and used. T3 - ZIB-Report - SC-97-50 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3193 ER - TY - GEN A1 - Ascher, Uri A1 - Reich, Sebastian T1 - The midpoint scheme and variants for Hamiltonian systems: advantages and pitfalls N2 - The (implicit) midpoint scheme, like higher order Gauss-collocation schemes, is algebraically stable and symplectic, and it preserves quadratic integral invariants. It may appear particularly suitable for the numerical solution of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or structural mechanics, because there is no stability restriction when it is applied to a simple harmonic oscillator. Although it is well-known that the midpoint scheme may also exhibit instabilities in various stiff situations, one might still hope for good results when resonance-type instabilities are avoided. In this paper we investigate the suitability of the midpoint scheme for highly oscillatory, frictionless mechanical systems, where the step-size $k$ is much larger than the system's small parameter $\varepsilon$, in case that the solution remains bounded as $\varepsilon \rightarrow 0$. We show that in general one must require that $k^2/\varepsilon$ be small enough, or else, even the errors in slowly varying quantities like the energy may grow undesirably (especially when fast and slow modes are tightly coupled) or, worse, the computation may yield misleading information. In some cases this may already happen when $k = O(\varepsilon )$. The same holds for higher order collocation at Gaussian points. The encountered restrictions on $k$ are still better than the corresponding ones for explicit schemes. T3 - ZIB-Report - SC-97-51 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3201 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Conjunctive Cuts for Integer Programs N2 - This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view. T3 - ZIB-Report - SC-98-18 KW - Polyhedral Combinatorics KW - Integer Programming KW - Separation Algorithm Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3618 ER - TY - THES A1 - Reich, Sebastian T1 - Dynamical Systems, Numerical Integration, and Exponentially Small Estimates N2 - Dynamical systems with two well-separated time-scales are investigated using normal form theory. Exponential estimates for the normal form truncation error are derived and applied to the numerical integration of differential equations (backward error analysis) and the reduction of highly oscillatory Hamiltonian systems (constrained dynamics and correcting potentials). The theoretical results are used to formulate new algorithms for the time integration of conservative Hamiltonian systems (projected multiple time stepping, soft constraints, rigid bodies, symplectic variable step-size methods). T3 - ZIB-Report - SC-98-19 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3622 ER - TY - GEN A1 - Bley, Andreas T1 - On the Complexity of Vertex-Disjoint Length-Restricted Path Problems N2 - Let $G=(V,E)$ be a simple graph and $s$ and $t$ be two distinct vertices of $G$. A path in $G$ is called $\ell$-bounded for some $\ell\in\mathbb{N}$, if it does not contain more than $\ell$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint $\ell$-bounded $s,t$-paths in $G$. First, we show that computing the maximum number of vertex-disjoint $\ell$-bounded $s,t$-paths is $\mathcal{AP\kern-1pt X}$--complete for any fixed length bound $\ell\geq 5$. Second, for a given number $k\in\mathbb{N}$, $1\leq k \leq |V|-1$, and non-negative weights on the edges of $G$, the problem of finding $k$ vertex-disjoint $\ell$-bounded $s,t$-paths with minimal total weight is proven to be $\mathcal{NPO}$--complete for any length bound $\ell\geq 5$. Furthermore, we show that, even if $G$ is complete, it is $\mathcal{NP}$--complete to approximate the optimal solution value of this problem within a factor of $2^{\langle\phi\rangle^\epsilon}$ for any constant $0<\epsilon<1$, where $\langle\phi\rangle$ denotes the encoding size of the given problem instance $\phi$. We prove that these results are tight in the sense that for lengths $\ell\leq 4$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to $\ell$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results. T3 - ZIB-Report - SC-98-20 KW - disjoint paths KW - length bounded paths KW - approximation KW - reducibility KW - completeness Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3639 ER - TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - On a Two-Queue Priority System with Impatience and its Application to a Call Center N2 - We consider a $s$-server system with two FCFS queues, where the arrival rates at the queues and the service rate may depend on the number $n$ of customers being in service or in the first queue, but the service rate is assumed to be constant for $n>s$. The customers in the first queue are impatient. If the offered waiting time exceeds a random maximal waiting time $I$, then the customer leaves the first queue after time $I$. If $I$ is less than a given deterministic time then he leaves the system else he transits to the end of the second queue. The customers in the first queue have priority. The service of a customer from the second queue will be started if the first queue is empty and more than a given number of servers become idle. For the model being a generalization of the $M(n)/M(n)/s\!+\!GI$ system balance conditions for the density of the stationary state process are derived yielding the stability conditions and the probabilities that precisely $n$ customers are in service or in the first queue. For obtaining performance measures for the second queue a system approximation basing on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server. For an important special case a stochastic decomposition is derived illuminating the connection to the dynamics of the $M(n)/M(n)/s\!+\!GI$ system. T3 - ZIB-Report - SC-98-21 KW - two queues KW - many server KW - server reservation KW - impatience KW - occupancy distribution KW - waiting time distribution KW - approximate system KW - $M(n)/M(n)/s+GI Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3641 ER - TY - GEN A1 - Lourenco, Maria José A1 - Rosa, Samuel Costa S. A1 - Castro, Carlos Alberto Nieto de A1 - Albuquerque, C. A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Roitzsch, Rainer T1 - Simulation of the Transient Heating in an Unsymmetrical Coated Hot--Strip Sensor with a Self--Adaptive Finite Element Method N2 - The transient heating in an unsymmetrical coated hot--strip sensor was simulated with a self--adaptive finite element method. The first tests of this model show that it can determine with a small error the thermal conductivity of liquids, from the transient temperature rise in the hot--strip, deposited in a substrate and coated by an alumina spray. T3 - ZIB-Report - SC-98-22 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3656 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering N2 - Multistage stochastic programs can be seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm. T3 - ZIB-Report - SC-98-23 KW - multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - finance Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3661 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Grötschel, Martin A1 - Dalitz, Wolfgang A1 - Winczewski, Vincent T1 - Math-Net: Ein Informationssystem der Mathematik N2 - In diesem Artikel geben wir einen Überblick über das Math-Net-Projekt. Wir berichten über die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems für die Mathematik in Deutschland. T3 - ZIB-Report - SC-98-25 KW - Information System KW - Math-Net KW - Math-Net-Links KW - Dublin Core KW - Harvest Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3680 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Scientific Information Systems and Metadata N2 - This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} . T3 - ZIB-Report - SC-98-26 KW - elektronisches Publizieren KW - Metadaten KW - Dublin Core KW - Klassifikation KW - Math-Net Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3698 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs N2 - The paper presents a new algorithmic approach for multistage stochastic programs which are seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within a primal-dual interior point method. Convergence is drastically enhanced by a successive refinement technique providing both primal and dual initial estimates. Test runs on a multistage portfolio selection problem demonstrate the performance of the method. T3 - ZIB-Report - SC-98-27 KW - Multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - successive refinement Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3706 ER - TY - GEN A1 - Schiermeyer, Ingo A1 - Tuza, Zsolt A1 - Voigt, Margit T1 - On-line rankings of graphs N2 - A (vertex) $k$-ranking of a graph $G=(V,E)$ is a mapping $ p:V\to \{1,\dots,k\}$ such that each path with endvertices of the same color $i$ contains an internal vertex of color $\ge i+1$. In the on-line coloring algorithms, the vertices $v_1,\dots,v_n$ arrive one by one in an unrestricted order, and only the edges inside the set $\{v_1,\dots,v_i\}$ are known when the color of $v_i$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a $(3\log_2 n)$-ranking for the path with $n \geq 2$ vertices, independently of the order in which the vertices are received. T3 - ZIB-Report - SC-97-32 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3011 ER - TY - GEN A1 - Tuza, Zsolt A1 - Voloshin, Vitaly I. T1 - Uncolorable mixed hypergraphs N2 - A mixed hypergraph ${\cal H}=(X,{\cal A},{\cal E})$ consists of the vertex set $X$ and two families of subsets: the family of edges ${\cal E}$ and the family of co-edges ${\cal A}$. In a coloring every edge $E \in {\cal E}$ has at least two vertices of different colors, while every co-edge $A \in {\cal A}$ has at least two vertices of the same color. The smallest (largest) number of colors for which there exists a coloring of a mixed hypergraph $\cal H$ using all the colors is called the lower (upper) chromatic number and is denoted $\chi ({\cal H})$ $(\bar {\chi} ({\cal H}) )$. A mixed hypergraph is called uncolorable if it admits no coloring. \par We show that there exist uncolorable mixed hypergraphs ${\cal H}=$ $(X, {\cal A}, {\cal E})$ with arbitrary difference between the upper chromatic number $\bar{\chi } ({\cal H}_{\cal A}) $ of ${\cal H}_{\cal A}=(X,{\cal A})$ and the lower chromatic number ${\chi }({\cal H}_{\cal E})$ of ${\cal H}_{\cal E}=(X,{\cal E}).$ Moreover, for any $k=\bar \chi ({\cal H}_{\cal A})- \chi ({\cal H}_{\cal E})$, the minimum number $v(k)$ of vertices of an inclusionwise minimal uncolorable mixed hypergraph is exactly $k+4.$ \par We introduce the measure of uncolorability which is called the vertex uncolorability number and propose a greedy algorithm that finds an estimate on it, and is a mixed hypergraph coloring heuristic at the same time. \par We show that the colorability problem can be expressed as an integer linear programming problem. \par Concerning particular cases, we describe those complete $(l,m)$-uniform mixed hypergraphs which are uncolorable, and observe that for given $(l,m)$ almost all complete $(l,m)$-uniform mixed hypergraphs are uncolorable, whereas generally almost all complete mixed hypergraphs are colorable. T3 - ZIB-Report - SC-97-33 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3024 ER - TY - GEN A1 - Kratochvil, Jan A1 - Tuza, Zsolt T1 - Rankings of Directed graphs N2 - A ranking of a graph is a coloring of the vertex set with positive integers such that on every path connecting two vertices of the same color, there is a vertex of larger color. We consider the directed variant of this problem, where the above condition is imposed only on those paths in which all edges are oriented in the same direction. We show that the ranking number of a directed tree is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time. Unlike the undirected case, however, deciding if the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard. T3 - ZIB-Report - SC-97-34 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3030 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Frequency Assignment in Cellular Phone Networks N2 - We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice. T3 - ZIB-Report - SC-97-35 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3044 ER - TY - GEN A1 - Lipnikov, Konstantin A1 - Deuflhard, Peter T1 - Domain Decomposition with Subdomain CCG for Material Jump Elliptic Problems. N2 - A combination of the cascadic conjugate gradient (CCG) method for homogeneous problems with a non-overlapping domain decomposition (DD) method is studied. Mortar finite elements on interfaces are applied to permit non-matching grids in neighboring subdomains. For material jump problems, the method is designed as an alternative to the cascadic methods. T3 - ZIB-Report - SC-97-36 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3057 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz T1 - A Spectral Bundle Method for Semidefinite Programming N2 - A central drawback of interior point methods for semidefinite programs is their lack of ability to exploit problem structure in cost and coefficient matrices. This restricts applicability to problems of small dimension. Typically semidefinite relaxations arising in combinatorial applications have sparse and well structured cost and coefficient matrices of huge order. We present a method that allows to compute acceptable approximations to the optimal solution of large problems within reasonable time. Semidefinite programming problems with constant trace on the primal feasible set are equivalent to eigenvalue optimization problems. These are convex nonsmooth programming problems and can be solved by bundle methods. We propose to replace the traditional polyhedral cutting plane model constructed by means of subgradient information by a semidefinite model that is tailored for eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficacy of the approach on combinatorial examples. T3 - ZIB-Report - SC-97-37 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3067 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Contributions to General Mixed Integer Knapsack Problems N2 - This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view. T3 - ZIB-Report - SC-97-38 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3075 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Henk, Martin T1 - On a series of Gorenstein cyclic quotient singularities admitting a unique projective crepant resolution. N2 - Let $G$ be a finite subgroup of SL$\left( r,% {\mathbb{C}}\right) $. In dimensions $r=2$ and $r=3$, McKay correspondence provides a natural bijection between the set of irreducible representations of $G$ and a cohomology-ring basis of the overlying space of a projective, crepant desingularization of ${\mathbb{C}}^r/G$. For $r=2$ this desingularization is unique and is known to be determined by the Hilbert scheme of the $G$% -orbits. Similar statements (including a method of distinguishing just {\it{one}} among all possible smooth minimal models of ${\mathbb{C}}^3/G$), are very probably true for all $G$'s $\subset $ SL$\left( 3,{\mathbb{C}}\right) $ too, and recent Hilbert-scheme-techniques due to Ito, Nakamura and Reid, are expected to lead to a new fascinating uniform theory. For dimensions $r\geq 4 $, however, to apply analogous techniques one needs extra modifications. In addition, minimal models of ${\mathbb{C}}^r/G$ are smooth only under special circumstances. ${\mathbb{C}}^4/\left( \hbox{\rm involution}\right) $, for instance, cannot have any smooth minimal model. On the other hand, all abelian quotient spaces which are c.i.'s can always be fully resolved by torus-equivariant, crepant, projective morphisms. Hence, from the very beginning, the question whether a given Gorenstein quotient space ${\mathbb{C}}% ^r/G$, $r\geq 4$, admits special desingularizations of this kind, seems to be absolutely crucial.\noindent In the present paper, after a brief introduction to the existence-problem of such desingularizations (for abelian $G$'s) from the point of view of toric geometry, we prove that the Gorenstein cyclic quotient singularities of type \[ \frac 1l\,\left( 1,\ldots ,1,l-\left( r-1\right) \right) \] with $l\geq r\geq 2$, have a \textit{unique }torus-equivariant projective, crepant, partial resolution, which is full'' iff either $l\equiv 0$ mod $% \left( r-1\right) $ or $l\equiv 1$ mod $\left( r-1\right) $. As it turns out, if one of these two conditions is fulfilled, then the exceptional locus of the full desingularization consists of $\lfloor\frac{l}{r-1} \rfloor $ prime divisors, $\lfloor\frac{l}{r-1} \rfloor -1$ of which are isomorphic to the total spaces of ${\mathbb{P}}_{{\mathbb{C}}}^1$-bundles over ${\mathbb{P}}_{{\mathbb{C}}% }^{r-2}$. Moreover, it is shown that intersection numbers are computable explicitly and that the resolution morphism can be viewed as a composite of successive (normalized) blow-ups. Obviously, the monoparametrized singularity-series of the above type contains (as its first member'') the well-known Gorenstein singularity defined by the origin of the affine cone which lies over the $r$-tuple Veronese embedding of ${\mathbb{P}}_{\mathbb{C}}^{r-1}$. T3 - ZIB-Report - SC-97-39 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3084 ER - TY - GEN A1 - Lang, Jens A1 - Erdmann, Bodo A1 - Roitzsch, Rainer T1 - Adaptive Time-Space Discretization for Combustion Problems N2 - We present a self--adaptive finite element method to solve combustion problems in 1D, 2D, and 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. A posteriori error estimates are obtained by constructing locally higher order solutions involving all variables of the problem. Adaptive strategies such as step size control, spatial refinement and coarsening allow us to get economically an accurate solution. Various examples are presented to demonstrate practical applications of the proposed method. T3 - ZIB-Report - SC-97-40 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3094 ER - TY - GEN A1 - Schütte, Christof A1 - Bornemann, Folkmar A. T1 - Approximation Properties and Limits of the Quantum-Classical Molecular Dynamics Model N2 - In molecular dynamics applications there is a growing interest in including quantum effects for simulations of larger molecules. This paper is concerned with {\em mixed quantum-classical} models which are currently discussed: the so-called QCMD model with variants and the time-dependent Born-Oppenheimer approximation. All these models are known to approximate the full quantum dynamical evolution---under different assumptions, however. We review the meaning of these assumptions and the scope of the approximation. In particular, we characterize those typical problematic situations where a mixed model might largely deviate from the full quantum evolution. One such situation of specific interest, a non-adiabatic excitation at certain energy level crossings, can promisingly be dealt with by a modification of the QCMD model that we suggest. T3 - ZIB-Report - SC-97-41 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3102 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin T1 - Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs N2 - We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems. T3 - ZIB-Report - SC-98-08 KW - Traveling Salesman Problem KW - Online-Algorithm KW - Automatic Storage System Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3519 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Optimization of Transportation Systems N2 - The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far. T3 - ZIB-Report - SC-98-09 KW - Transportation Systems KW - Optimization KW - Discrete Mathematics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3529 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Monotone Iterations for Elliptic Variational Inequalities N2 - A wide range of free boundary problems occurring in engineering andindustry can be rewritten as a minimization problem for astrictly convex, piecewise smooth but non--differentiable energy functional.The fast solution of related discretized problemsis a very delicate question, because usual Newton techniquescannot be applied. We propose a new approach based on convex minimization and constrained Newton type linearization. While convex minimization provides global convergence of the overall iteration, the subsequent constrained Newton type linearization is intended to accelerate the convergence speed. We present a general convergence theory and discuss several applications. T3 - ZIB-Report - SC-98-10 KW - finite elements KW - multigrid methods KW - variational inequalities Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3539 ER - TY - GEN A1 - Caröe, Claus C. A1 - Schultz, Rüdiger T1 - A Two-Stage Stochastic Program for Unit Commitment Under Uncertainty in a Hydro-Thermal Power System N2 - We develop a two-stage stochastic programming model with integer first-stage and mixed-integer recourse for solving the unit commitment problem in power generation in the presence of uncertainty of load profiles. The solution methodology rests on a novel scenario decomposition method for stochastic integer programming. This method combines Lagrangian relaxation of non-anticipativity constraints with branch-and-bound. It can be seen as a decomposition algorithm for large-scale mixed-integer linear programs with block-angular structure. With realistic data from a German utility we validate our model and carry out test runs. Sizes of these problems go up to 20.000 integer and 150.000 continuous variables together with up to 180.000 constraints. T3 - ZIB-Report - SC-98-11 KW - Programming KW - stochastic:Scenario Decomposition if mixed-integer programs KW - Natural resourses KW - energy:Unit commitment under uncertainty Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3543 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Haus, Utz-Uwe A1 - Henk, Martin T1 - On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities N2 - \noindent An immediate generalization of the classical McKay correspondence for Gorenstein quotient spaces $\Bbb{C}^{r}/G$ in dimensions $r\geq 4$ would primarily demand the existence of projective, crepant, full desingularizations. Since this is not always possible, it is natural to ask about special classes of such quotient spaces which would satisfy the above property. In this paper we give explicit necessary and sufficient conditions under which 2-parameter series of Gorenstein cyclic quotient singularities have torus-equivariant resolutions of this specific sort in all dimensions. T3 - ZIB-Report - SC-98-12 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3559 ER - TY - GEN A1 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Design of Broadband Virtual Private Networks: Model and Heuristics for the B–WiN N2 - We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data. T3 - ZIB-Report - SC-98-13 KW - Telecommunication Network Design KW - Survivable Networks KW - Network Capacity Planning KW - OSPF Routing KW - Shortest Path Routing KW - Heuristics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3565 ER - TY - GEN A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes I. N2 - The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve. T3 - ZIB-Report - SC-98-14 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations KW - Flip Defici Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3579 ER - TY - GEN A1 - Roitzsch, Rainer A1 - Erdmann, Bodo A1 - Lang, Jens T1 - The Benefits of Modularization: from KASKADE to KARDOS N2 - KARDOS solves nonlinear evolution problems in 1, 2, and 3D. An adaptive multilevel finite element algorithm is used to solve the spatial problems arising from linearly implicit discretization methods in time. Local refinement and derefinement techniques are used to handle the development of the mesh over time. The software engineering techniques used to implement the modules of the KASKADE toolbox are reviewed and their application to the extended problem class is described. A notification system and dynamic construction of records are discussed and their values for the implementation of a mesh transfer operation are shown. The need for low-level and high--level interface elements of a module is discussed for the assembling procedure of KARDOS. At the end we will summarize our experiences. T3 - ZIB-Report - SC-98-15 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3586 ER - TY - GEN A1 - Lang, Jens T1 - Adaptive Incompressible Flow Computations with Linearly Implicit Time Discretization and Stabilized Finite Elements N2 - Fully adaptive solutions of imcompressible flow problems employing the discretization sequence first in time then in space are presented. The time discretization is done by linearly implicit one--step methods possibly of high order with automatic step size control. A posteriori error estimates for the stabilized finite element discretization in space are obtained by solving local Dirichlet problems with higher accuracy. Once those estimates have been computed, we are able to control time and space grids with respect to required tolerances and necessary computational work. The devised method is applied to two benchmark problems in 2D. T3 - ZIB-Report - SC-98-16 KW - Incompressible Flow KW - Adaptive Stabilized Finite Element KW - Linearly Implicit Time Discretization Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3599 ER - TY - GEN A1 - Holder, Thomas A1 - Leimkuhler, Benedict A1 - Reich, Sebastian T1 - Explicit Variable Step-Size and Time-Reversible Integration N2 - A variable step-size, semi-explicit variant of the explicit Störmer-Verlet method has been proposed for the time-reversible integration of Newton's equations of motion by Huang & Leimkuhler. Here we propose a fully explicit version of this approach applicable to explicit and symmetric integration methods for general time-reversible differential equations. As applications, we discuss the variable step-size, time-reversible, and fully explicit integration of rigid body motion and reversible Nos\'e-Hoover dynamics. T3 - ZIB-Report - SC-98-17 KW - reversible differential equations KW - time integration KW - adaptive methods Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3607 ER - TY - GEN A1 - Wolf, Thomas T1 - Structural equations for Killing tensors of arbitrary rank N2 - An algorithm is given for bringing the equations of monomial first integrals of arbitrary degree of the geodesic motion in a Riemannian space $V_n$ into the form $(F_A)_{;k} = \sum_B \Gamma_{kAB} F_B$. The $F_A$ are the components of a Killing tensor $K_{i_1\ldots i_r}$ of arbitrary rank $r$ and its symmetrized covariant derivatives. Explicit formulas are given for rank 1,2 and 3. %The maximal number of Killing tensors %(reducible + non-reducible) is found to be %$\frac{1}{r+1}\left( ^{n + r - 1}_{\;\;\;\;\,r} \right) % \left( ^{ n+r}_{\;\;\,r} \right)$. Killing tensor equations in structural form allow the formulation of algebraic integrability conditions and are supposed to be well suited for integration as it is demonstrated in the case of flat space. An alternative proof of the reducibility of these Killing tensors is given which shows the correspondence to structural equations for rank 2 Killing tensors as formulated by Hauser & Malhiot. They used tensors with different symmetry properties. T3 - ZIB-Report - SC-97-62 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3310 ER - TY - GEN A1 - Ehrig, Rainald A1 - Deuflhard, Peter T1 - GMERR - an Error Minimizing Variant of GMRES N2 - The paper analyzes a recently proposed iterative error minimizing method for the solution of linear systems. Sufficient and necessary conditions for convergence are studied, which show that the method essentially requires normal matrices. An efficient implementation similar to GMRES has been worked out in detail. Numerical tests on general non--normal matrices, of course, indicate that this approach is not competitive with GMRES. Summarizing, if error minimizing is important, one should rather choose CGNE. A computational niche for GMERR might be problems, where normal but non--symmetric matrices occur, like dissipative quantum mechanics. T3 - ZIB-Report - SC-97-63 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3323 ER - TY - GEN A1 - Schmidt, Frank T1 - Computation of Discrete Transparent Boundary Conditions for the 2D Helmholtz Equation N2 - We present a family of nonlocal transparent boundary conditions for the 2D Helmholtz equation. The whole domain, on which the Helmholtz equation is defined, is decomposed into an interior and an exterior domain. The corresponding interior Helmholtz problem is formulated as a variational problem in standard manner, representing a boundary value problem, whereas the exterior problem is posed as an initial value problem in the radial variable. This problem is then solved approximately by means of the Laplace transformation. The derived boundary conditions are asymptotically correct, model inhomogeneous exterior domains and are simple to implement. T3 - ZIB-Report - SC-97-64 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3330 ER - TY - GEN A1 - Bornemann, Folkmar A. T1 - Homogenization in Time II: Mechanical Systems Subject to Friction and Gyroscopic Forces N2 - In our previous work [Preprint SC 97-48] we have studied natural mechanical systems on Riemannian manifolds with a strong constraining potential. These systems establish fast nonlinear oscillations around some equilibrium manifold. Important in applications, the problem of elimination of the fast degrees of freedom, or {\em homogenization in time}, leads to determine the singular limit of infinite strength of the constraining potential. In the present paper we extend this study to systems which are subject to external forces that are non-potential, depending in a mixed way on positions {\em and}\/ velocities. We will argue that the method of weak convergence used in [1997] covers such forces if and only if they result from viscous friction and gyroscopic terms. All the results of [1997] directly extend if there is no friction transversal to the equilibrium manifold; elsewise we show that instructive modifications apply. T3 - ZIB-Report - SC-97-65 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3348 ER - TY - GEN A1 - Beck, Rudolf A1 - Deuflhard, Peter A1 - Hiptmair, Ralf A1 - Hoppe, Ronald H. W. A1 - Wohlmuth, Barbara T1 - Adaptive Multilevel Methods for Edge Element Discretizations of Maxwell's Equations N2 - The focus of this paper is on the efficient solution of boundary value problems involving the double-- curl operator. Those arise in the computation of electromagnetic fields in various settings, for instance when solving the electric or magnetic wave equation with implicit timestepping, when tackling time--harmonic problems or in the context of eddy--current computations. Their discretization is based on on N\'ed\'elec's {\bf H(curl}; $\Omega$)--conforming edge elements on unstructured grids. In order to capture local effects and to guarantee a prescribed accuracy of the approximate solution adaptive refinement of the grid controlled by a posteriori error estimators is employed. The hierarchy of meshes created through adaptive refinement forms the foundation for the fast iterative solution of the resulting linear systems by a multigrid method. The guiding principle underlying the design of both the error estimators and the multigrid method is the separate treatment of the kernel of the curl--operator and its orthogonal complement. Only on the latter we have proper ellipticity of the problem. Yet, exploiting the existence of computationally available discrete potentials for edge element spaces, we can switch to an elliptic problem in potential space to deal with nullspace of curl. Thus both cases become amenable to strategies of error estimation and multigrid solution developed for second order elliptic problems. The efficacy of the approach is confirmed by numerical experiments which cover several model problems and an application to waveguide simulation. T3 - ZIB-Report - SC-97-66 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3356 ER - TY - GEN A1 - Fischer, Alexander A1 - Cordes, Frank A1 - Schütte, Christof T1 - Hybrid Monte Carlo with Adaptive Temperature in a Mixed-Canonical Ensemble: Efficient Conformational Analysis of RNA N2 - A hybrid Monte Carlo method with adaptive temperature choice is presented, which exactly generates the distribution of a mixed-canonical ensemble composed of two canonical ensembles at low and high temperature. The analysis of resulting Markov chains with the reweighting technique shows an efficient sampling of the canonical distribution at low temperature, whereas the high temperature component facilitates conformational transitions, which allows shorter simulation times. \\The algorithm was tested by comparing analytical and numerical results for the small n-butane molecule before simulations were performed for a triribonucleotide. Sampling the complex multi-minima energy landscape of these small RNA segments, we observed enforced crossing of energy barriers. T3 - ZIB-Report - SC-97-67 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3364 ER - TY - GEN A1 - Nowak, Ulrich A1 - Gebauer, Susanna T1 - A New Test Frame for Ordinary Differential Equation Solvers N2 - Benchmarking of ODE methods has a long tradition. Several sets of test problems have been developed and new problems are still collected. So, a whole variety of problems can be used to check the efficiency of a method under investigation. In general, efficiency is measured by the amount of work whi ch is necessary to get a reliable solution for a prescribed accura cy. In order to quantify the term ``amount of work'' usually not only the computing time is measured but also the number of calls of functional units. To quantify the term ``quality of a numerical solution'' usually the $l_2$--norm of the true error at the final point of the integration interval is used. In our contribution we first discuss some general aspects of benchmarking. Then we present a new test frame which allows to solve typical benchmark problems with some of the state of the art integrators within a unified framework. Finally we show some results of our benchmark tests. Part of the test frame can be used interactively in the World Wide Web. T3 - ZIB-Report - SC-97-68 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3370 ER - TY - GEN A1 - Nowak, Ulrich A1 - Ehrig, Rainald A1 - Oeverdieck, Lars T1 - Parallel Extrapolation Methods and Their Application in Chemical Engineering N2 - We study the parallelization of linearly--implicit extrapolation methods for the solution of large scale systems of differential algebraic equations arising in a method of lines (MOL ) treatment of partial differential equations. In our approach we combine a slightly overlapping domain decomposi tion together with a polynomial block Neumann preconditioner. Through the explicit computation of the matrix products of the pre conditioner and the system matrix a significant gain in overall efficiency is achieved for medium--sized problems. The parallel algorithm exhibits a good scalability up to 32 proces sors on a Cray T3E. Preliminary results for computations on a workstation cluster are reported. T3 - ZIB-Report - SC-97-69 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3387 ER - TY - GEN A1 - Foupouagnigni, Mama A1 - Ronveaux, Andre A1 - Hounkonnou, Mahouton Norbert T1 - The Fourth-Order Difference Equation Satisfied by the Associated Orthogonal Polynomials of the Delta-Laguerre-HahnClass N2 - Starting from the $ D_{ \omega}$-Riccati Difference equation satisfied by the Stieltjes function of a linear functional, we work out an algorithm which enables us to write the unique fourth-order difference equation satisfied by the associated of any integer order of orthogonal polynomials of the $ \Delta$-Laguerre-Hahn class. Moreover, in classical situations (Meixner, Charlier, Kravtchouk and Hahn), we give explicitely these difference equations; and from Hahn difference equation, we recover by limit process the difference equations satisfied by the associated of classical discrete orthogonal polynomials and differential equations satisfied by the associated of classical continuous orthogonal polynomials. T3 - ZIB-Report - SC-97-71 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3409 ER - TY - GEN A1 - Bruns, Winfried A1 - Gubeladze, Joseph A1 - Henk, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - A counterexample to an integer analogue of Caratheodorys theorem N2 - For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed. T3 - ZIB-Report - SC-98-28 KW - Integral pointed cones KW - Hilbert basis KW - integral Carathéodory property Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3718 ER - TY - GEN A1 - Huisinga, Wilhelm A1 - Pesce, Lorenzo A1 - Kosloff, Ronnie A1 - Saalfrank, Peter T1 - Faber and Newton Polynomial Integrators for Open-System Density Matrix Propagation N2 - Two polynomial expansions of the time-evolution superoperator to directly integrate Markovian Liouville-von Neumann (LvN) equations for quantum open systems, namely the Newton interpolation and the Faber approximation, are presented and critically compared. Details on the numerical implementation including error control, and on the performance of either method are given. In a first physical application, a damped harmonic oscillator is considered. Then, the Faber approximation is applied to compute a condensed phase absorption spectrum, for which a semi--analytical expression is derived. Finally, even more general applications are discussed. In all applications considered here it is found that both the Newton and Faber integrators are fast, general, stable, and accurate. T3 - ZIB-Report - SC-98-29 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3725 ER - TY - GEN A1 - Deuflhard, Peter A1 - Seebass, Martin T1 - Adaptive Multilevel FEM as Decisive Tools in the Clinical Cancer Therapy Hyperthermia N2 - The paper surveys recent progress in a joint mathematical-medical project on cancer therapy planning. Within so-called regional hyperthermia the computational task is to tune a set of coupled radiofrequency antennas such that a carefully measured tumor is locally heated, but any outside hot spots are avoided. A mathematical model of the whole clinical system -- air, applicator with antennas, water bolus, individual patient body -- involves Maxwell's equations in inhomogeneous media and a parabolic bioheat transfer equation, which represents a simplified model of heat transfer in the human body (ignoring strong blood vessel heat transport). Both PDEs need to be computed fast and to medical reliability (!) on a workstation within a clinical environment. This requirement triggered a series of new algorithmic developments to be reported here, among which is an adaptive multilevel FEM for Maxwell's equations, which dominates the numerical simulation time. In total, however, the main bulk of computation time (see Table 3 in Section 4 below) still goes into segmentation -- a necessary preprocessing step in the construction a 3D virtual patient from the input of a stack of 2D computed tomograms (left out here). T3 - ZIB-Report - SC-98-30 KW - hyperthermia KW - Maxwell's equations KW - nonlinear heat transfer KW - finite elements Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3739 ER - TY - GEN A1 - Schneider, Thomas A1 - Botta, Nicola A1 - Geratz, Karl Josef A1 - Klein, Rupert T1 - Extension of finite volume compressible flow solvers to multi-dimensional, variable density zero Mach number flow N2 - When attempting to compute unsteady, variable density flows at very small or zero Mach number using a standard finite volume compressible flow solver one faces at least the following difficulties: (i) Spatial pressure variations vanish as the Mach number $M \rightarrow 0$, but they do affect the velocity field at leading order; (ii) the resulting spatial homogeneity of the leading order pressure implies an elliptic divergence constraint for the energy flux; (iii) violation of this constraint would crucially affect the transport of mass, thereby disabling a code to properly advect even a constant density distribution. A previous companion paper derived the above observations from a single time - multiple length scale asymptotic analysis for $M \ll 1$, applied to the conservation form of the governing equations and assuming an ideal gas with constant specific heats. The paper then restricted to weakly compressible one-dimensional flows and introduced a semi-implicit extension of a compressible flow solver, designed to handle the interaction of long wavelength acoustics with small scale, large amplitude density fluctuations. In the present paper we concentrate on the limit of zero Mach number for multi-dimensional, variable density flows. The construction of numerical fluxes for all conserved quantities involves: An explicit upwind step (1) yielding predictions for the nonlinear convective flux components. This procedure still neglects the influence of pressure gradients on the convective fluxes during the time step. Suitable corrections are applied in step (2), which guarantees compliance of the convective fluxes with the divergence constraint. This step requires the solution of a Poisson-type equation to obtain the relevant pressure gradients. Step (3), which requires the solution of a second Poisson-type equation, yields the yet unknown (non-convective) pressure contribution to the total flux of momentum. The final, cell centered velocity field exactly satisfies a discrete divergence constraint consistent with the asymptotic limit. Notice that step (1) can be done by any standard finite volume compressible flow solver and that the input to steps (2) and (3) involves solely the fluxes from step (1), but is independent on how these were obtained. Thus, we claim that our approach allows any such solver to be extended to simulate incompressible flows. Extensions to the weakly compressible regime $0 < M \ll 1$, reactive flows and more complex equations of state will be addressed in follow-up publications. T3 - ZIB-Report - SC-98-31 KW - Incompressible variable density flows KW - conservation laws Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3749 ER - TY - GEN A1 - Schmidt, Frank T1 - An Alternative Derivation of the Exact DtN-Map on a Circle N2 - The paper supplies an alternative derivation of the exact boundary conditions needed for the solution of time-harmonic acoustic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior domain problem as an initial value problem with initial data given on the boundary of a disc or sphere. The solution of the exterior domain problem is obtained via Laplace transformation techniques, where the asymptotic Sommerfeld radiation condition is reformulated accordingly. T3 - ZIB-Report - SC-98-32 KW - Helmholtz equation KW - Dirichlet-to-Neumann map KW - Sommerfeld radiation condition Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3752 ER - TY - GEN A1 - Kühn, Wolfgang A1 - Korzen, Manfred A1 - Paetsch, Olaf T1 - Fast Data Assimilation in Fire Tests of Steel Members N2 - This report presents a fast data assimilation method to produce an interpolating time and space temperature distribution for steel members subject to fire testing. The method assimilates collected temperature data into the numerical integration of the heat equation. This physically based method also allows the computation of lateral and axial heat flux into and inside the member. T3 - ZIB-Report - SC-98-33 KW - data assimilation KW - heat equation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3766 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Krumke, Sven A1 - Rambau, Jörg T1 - The Online Transportation Problem: Competitive Scheduling of Elevators N2 - In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service. T3 - ZIB-Report - SC-98-34 KW - online optimization KW - competitive analysis KW - elevator Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3779 ER - TY - GEN A1 - Deuflhard, Peter A1 - Weiser, Martin A1 - Seebass, Martin T1 - A New Nonlinear Elliptic Multilevel FEM Applied to Regional Hyperthermia N2 - In the clinical cancer therapy of regional hyperthermia nonlinear perfusion effects inside and outside the tumor seem to play a not negligible role. A stationary model of such effects leads to a nonlinear Helmholtz term within an elliptic boundary value problem. The present paper reports about the application of a recently designed adaptive multilevel FEM to this problem. For several 3D virtual patients, nonlinear versus linear model is studied. Moreover, the numerical efficiency of the new algorithm is compared with a former application of an adaptive FEM to the corresponding instationary model PDE. T3 - ZIB-Report - SC-98-35 KW - hyperthermia KW - nonlinear elliptic KW - multilevel FEM Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3785 ER - TY - GEN A1 - Huisinga, Wilhelm A1 - Best, Christoph A1 - Cordes, Frank A1 - Roitzsch, Rainer A1 - Schütte, Christof T1 - From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods N2 - Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide. T3 - ZIB-Report - SC-98-36 KW - conformational ensemble KW - cluster method KW - structural and dynamical similarity KW - representative KW - conformation KW - essential degrees of freedom KW - transi Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3797 ER - TY - GEN A1 - Nettesheim, Peter T1 - Second Order Transitions in Quantum-Classical Molecular Dynamics N2 - Mixed quantum--classical models have attracted considerable interest due to the expectation that they correctly describe non--adiabatic processes of full quantum dynamics. One of these models, the so--called QCMD model, represents most degrees of freedom of the molecular system by the means of classical mechanics but an important, small portion of the system is modeled by a wavefunction: the wavefunction is nonlinearly coupled to the classical motion via a singularly perturbed Schrödinger equation. In extension to the analysis given by F.A.~Bornemann [{\em Homogenization in Time of Singularly Perturbed Mechanical Systems}, Lecture Notes in Mathematics, no.~1687, 1998, Springer, Berlin], the article presents an asymptotic expansion up to second order in the perturbation parameter. This result allows for the construction of new models and numerical integration schemes. T3 - ZIB-Report - SC-98-37 KW - quantum-classical molecular dynamics KW - mixed quantum-classical models KW - asymptotics KW - quantum populations Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3805 ER - TY - GEN A1 - Schintke, Florian T1 - Ermittlung von Programmlaufzeiten anhand von Speicherzugriffen, Microbenchmarks und Simulation vonSpeicherhierarchien N2 - \\{\bf Zusammenfassung:} Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten berü{}cksichtigt. In dieser Diplomarbeit wird ein Simulator fü{}r Speicherhierarchien prä{}sentiert, der die Berechnung von Programmausfü{}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These geprü{}ft, da\ss{} mit diesem Modell die Ausfü{}hrungszeit eines Programms adä{}quat abgeschä{}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel mö{}glich, Programmausfü{}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann fü{}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterstü{}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Kohä{}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse bestä{}tigen die These nicht nur fü{}r Einzelprozessorsysteme, sondern auch fü{}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffssequenz auf Zwischenspeicher beeinflussen. Zusä{}tzlich wurde eine neue Einsatzmö{}glichkeit des LDA-Modells entwickelt, um die Ausfü{}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten kö{}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch kö{}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch prä{}zise und gezielte Informationsproduktion.Cost models are used to determine the execution time of programs, to compare the efficiency of algorithms, and to analyse the behaviour of memory hierarchies. The Latency-of-Data-Access (LDA) model that takes into account multiple hierarchical memory levels with different latencies, is a newly proposed, innovative cost model. In this diploma-thesis, a simulator for memory hierarchies is presented that allows the calculation of execution times using the LDA-model. The simulator is used to prove the claim that the execution time of a program can be accurately estimated with the LDA-model. With the simulator, it is for the first time possible to determine the execution time of programs with this model in a practical way. The simulator can be configured for systems with various cache architectures and supports shared memory (SMP) multiprocessor systems with different cache coherence protocols. The simulator can be configured with the results from microbenchmarks which measure the architectural properties of a memory hierarchy. The results confirm the claim not only for single processor systems, but also for SMP systems, where concurrently interacting processors influence each others cache access sequence. Additionally, a new field of usage of the LDA-model was developed to determine execution times of program parts. Single access costs can be assigned to one of several parallel running models. As an example the costs of accesses to different memory areas can be split and determined separately. This profiling technique allows to optimise data structures and memory access patterns of sequential and parallel SMP programs by precise production of information. T3 - ZIB-Report - 00-33 KW - Cache-Simulator KW - Microbenchmarks KW - SMP-System KW - Kostenmodell KW - Speicherhierarchie Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6018 ER - TY - GEN A1 - Helmberg, Christoph T1 - SBmethod --- A C++ Implementation of the Spectral Bundle Method. Manual to Version 1.1 N2 - \texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables $y_i$ may be sign constrained, $C$ and and $A_i$ are given real symmetric matrices, $b\in\mathbf{R}^m$ allows to specify a linear cost term, and $a>0$ is a constant multiplier for the maximum eigenvalue function $\lambda_{\max}(\cdot)$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode. T3 - ZIB-Report - 00-35 KW - semidefinite programming KW - semidefinite relaxations KW - spectral bundle method KW - eigenvalue optimization KW - large-scale problems Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6039 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Stable Multi-Sets N2 - In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks. T3 - ZIB-Report - 00-36 KW - stable multi-sets KW - polyhedral combinatorics Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6047 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Voß, Stefan T1 - SteinLib: An Updated Library on Steiner Tree Problems in Graphs N2 - In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances. T3 - ZIB-Report - 00-37 KW - Steiner Trees KW - Mathematical Programming Testdata Library Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6056 ER - TY - GEN A1 - Keller, Axel A1 - Reinefeld, Alexander T1 - Anatomy of a Resource Management System for HPC-Clusters N2 - Workstation clusters are often not only used for high-throughput computing in time-sharing mode but also for running complex parallel jobs in space-sharing mode. This poses several difficulties to the resource management system, which must be able to reserve computing resources for exclusive use and also to determine an optimal process mapping for a given system topology. On the basis of our CCS software, we describe the anatomy of a modern resource management system. Like Codine, Condor, and LSF, CCS provides mechanisms for the user-friendly system access and management of clusters. But unlike them, CCS is targeted at the effective support of space-sharing parallel and even metacomputers. Among other features, CCS provides a versatile resource description facility, topology-based process mapping, pluggable schedulers, and hooks to metacomputer management. T3 - ZIB-Report - 00-38 KW - Resource Management System KW - Metacomputer Management Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6063 ER - TY - GEN A1 - Kuberek, Monika T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV) - Konzept, Erfahrungen, Ausblick - N2 - Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten auf dem 2. BSZ-Kolloquium des Bibliotheksservice-Zentrums Baden-Württemberg (BSZ) am 10. Oktober 2000 in Konstanz. Der Kooperative Bibliotheksverbund Berlin-Brandenburg, kurz KOBV, ist ein sehr junger Verbund - genauer gesagt, befindet er sich im Oktober 2000 immer noch in der Aufbauphase. Das KOBV-Projekt hat am 1. April 1997 begonnen und wird am 31. Dezember 2000 enden. Ab 2001 wird der KOBV in eine institutionalisierte Form überführt, die - wie bereits das Projekt - am Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) - angesiedelt wird. Mit dem KOBV wurde ein in technischer wie auch in organisatorischer Hinsicht neuartiger Bibliotheksverbund aufgebaut, der auf der \glqq Internetphilosophie\grqq basiert: Den technischen Kern bildet eine eigens entwickelte Suchmaschine; die Organisation ist dezentral ausgerichtet und gründet sich auf der Kooperation der KOBV-Partner. In dem Vortrag werden das technische und das organisatorische Verbundkonzept vorgestellt, über die Erfahrungen nach einjähriger Betriebsdauer berichtet und ein kurzer Ausblick darüber gegeben, wie es mit dem KOBV weitergeht. T3 - ZIB-Report - 00-39 KW - Bibliotheksverbund KW - KOBV KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6079 ER - TY - GEN A1 - Steinbach, Marc T1 - Autos, Ziegen und Streithähne N2 - Das aus den Medien bekannte umstrittene Ziegenproblem (auch Drei-Türen-Problem genannt) wird vollständig analysiert und gelöst. In der Streitfrage spielen sprachliche Mehrdeutigkeiten der Problemformulierung eine wesentliche Rolle; zudem werden Zufallsereignisse mit willkürlicher Information über deren Ergebnisse verwechselt. Tatsächlich erweisen sich beide strittigen Lösungen als teilweise richtige Bestandteile der Gesamtlösung. Die Argumentation wird in allgemeinverständlicher Sprache geführt und anschliessend durch eine formale mathematische Betrachtung ergänzt. T3 - ZIB-Report - 00-40 KW - Ziegenproblem KW - Zufall KW - Willkür Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6087 ER - TY - GEN A1 - Heidl, Sebastian A1 - Staudemeyer, Ralf T1 - Implementation von WAP-Diensten für die SGI/CRAY T3E des ZIB N2 - Die zunehmende Verfügbarkeit von mobilen Geräten, die mit einem Internetanschluß ausgerüstet sind, bringt auch eine steigende Nachfrage nach Informationsdiensten für diese Art von Clients mit sich. Das ZIB stellt mit seinem Höchstleistungsrechner vom Typ SGI/CRAY T3E Wissenschaftlern große Rechenkapazitäten zur Verfügung. Im Rahmen dieser Studienarbeit wurde ein WAP-Interface zur T3E entwickelt, das es den Nutzern ermöglicht, über ein mobiles, WAP-fähiges Gerät Informationen zur Betriebsbereitschaft und zur Auslastung des Höchstleistungsrechners, sowie Informationen zu den von ihnen in Auftrag gegebenen Rechenjobs abzurufen. Die Untersuchung der aktuellen Möglichkeiten in der mobilen Kommunikation brachte einige Einschränkungen für das geplante Informationsangebot mit sich. So mußte auf Grund von Sicherheitsbedenken auf eine tatsächliche Interaktionsmöglichkeit (z.B. neue Rechenjobs zu starten) verzichtet werden. Demgegenüber konnte gezeigt werden, daß die Bereitstellung der gleichen Informationen für unterschiedliche Arten von Clients (WWW-Browser $\rightarrow$ HTML, WAP-Browser $\rightarrow$ WML) durch die Verwendung von XML als internes Datenformat problemlos möglich ist. Es hat sich gezeigt, daß die Bereitstellung eines WAP-Informationsdienstes auf Grund verschiedener Inkompatibilitätsprobleme (verschiedene Gateways, verschiedene WAP-Browser) mit erheblichem Aufwand verbunden sein kann. An dieser Stelle besteht noch Handlungsbedarf seitens der Hersteller dieser Softwarepakete. T3 - ZIB-Report - 00-41 KW - WAP KW - T3E KW - wireless KW - supercomputing KW - kannel KW - XML KW - cocoon Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6098 ER - TY - GEN A1 - Kuberek, Monika A1 - Lill, Monika A1 - Lohrum, Stefan A1 - Rusch, Beate T1 - Spezifikation der Schnittstelle zwischen KOBV-Suchmaschine und Lokalsystemen N2 - Die Kommunikation zwischen der KOBV-Suchmaschine und entfernten Bibliotheksinformationssystemen unterschiedlicher Hersteller wird über das Standardprotokoll Z39.50 abgewickelt. Die Suchmaschine ermöglicht Online-Recherchen in lokalen Bibliotheksinformationssystemen, die dazu ein Z39.50 Target (Server) zur Verfügung stellen müssen. Die Suchmaschine liefert ihre Daten ebenfalls über Z39.50 aus. Ein Lokalsystem benötigt hierfür einen Z39.50 Origin (Client). In dem Papier wird die Schnittstelle zwischen der KOBV-Suchmaschine und lokalen Bibliothekssystemen spezifiziert: Es werden die grundlegenden Anforderungen an Lokalsysteme definiert und die Konfigurationsparameter für die Z39.50-Kommunikation zwischen KOBV-Suchmaschine und Lokalsystemen beschrieben. T3 - ZIB-Report - 00-42 KW - Bibliotheksverbund KW - KOBV KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg KW - Web-Link KW - Z39.50 KW - Z39.50-Protokoll Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6106 ER - TY - GEN A1 - Bley, Andreas T1 - A Lagrangian Approach for Integrated Network Design and Routing in IP Networks N2 - We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported. T3 - ZIB-Report - 03-29 KW - Network Planning KW - Routing KW - IP Routing KW - Lagrangian relaxation Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7515 ER - TY - GEN A1 - Khan, Arifa Ali A1 - Bakeyev, Timur A1 - Göckeler, Meinulf A1 - Horsley, Roger A1 - Pleiter, Dirk A1 - Rakow, Paul A1 - Schäfer, Andreas A1 - Schierholz, Gerrit A1 - Stüben, Hinnerk T1 - Accelerating Hasenbusch's Acceleration of Hybrid Monte Carlo N2 - Hasenbusch has proposed splitting the pseudo-fermionic action into two parts, in order to speed-up Hybrid Monte Carlo simulations of QCD. We have tested a different splitting, also using clover-improved Wilson fermions. An additional speed-up between 5 and 20\% over the original proposal was achieved in production runs. T3 - ZIB-Report - 03-30 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7520 ER - TY - GEN A1 - Bley, Andreas A1 - Koster, Arie M.C.A. A1 - Kröller, Alexander A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Kosten- und Qualitätsoptimierung in Kommunikationsnetzen N2 - Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuführen. Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der mathematischen Optimierung für die Praxis. T3 - ZIB-Report - 03-31 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7537 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Koster, Arie M.C.A. T1 - Safe separators for treewidth N2 - A set of vertices $S\subseteq V$ is called a safe separator for treewidth, if $S$ is a separator of $G$, and the treewidth of $G$ equals the maximum of the treewidth over all connected components $W$ of $G-S$ of the graph, obtained by making $S$ a clique in the subgraph of $G$, induced by $W\cup S$. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every minimal separator of size one or two is safe, every minimal separator of size three that does not split off a component with only one vertex is safe, and every minimal separator that is an almost clique is safe; an almost clique is a set of vertices $W$ such that there is a $v\in W$ with $W-\{v\}$ a clique. We report on experiments that show significant reductions of instance sizes for graphs from proba! bilistic networks and frequency assignment. T3 - ZIB-Report - 03-32 KW - treewidth KW - safe separators KW - preprocessing Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7544 ER - TY - GEN A1 - Helling, Christiane A1 - Klein, Rupert A1 - Woitke, Peter A1 - Nowak, Ulrich A1 - Sedlmayr, Erwin T1 - Dust in Brown Dwarfs IV. Dust formation and driven turbulence on mesoscopic scales N2 - Dust formation {in brown dwarf atmospheres} is studied by utilizing a model for driven turbulence in the mesoscopic scale regime. We apply a pseudo-spectral method where waves are created and superimposed {within} a {limited} wavenumber interval. The turbulent kinetic energy distribution follows the Kolmogoroff spectrum which is assumed to be the most likely value. Such superimposed, stochastic waves may occur in a convectively active environment. They cause nucleation fronts and nucleation events and thereby initiate the dust formation process which { continues until} all condensible material is consumed. Small disturbances {are found to} have a large impact on the dust forming system. An initially dust-hostile region, which may originally be optically thin, becomes optically thick in a patchy way showing considerable variations in the dust properties during the formation process. The dust appears in lanes and curls as a result of the interaction with waves, i.e. turbulence, which form larger and larger structures with time. Aiming on a physical understanding of the variability of brown dwarfs, related to structure formation in substellar atmospheres, we work out first necessary criteria for small-scale closure models to be applied in macroscopic simulations of dust forming astrophysical systems. T3 - ZIB-Report - 03-33 KW - substellar atmospheres KW - dust formation KW - turbulence Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7555 ER - TY - GEN A1 - Helling, Christiane A1 - Klein, Rupert A1 - Sedlmayr, Erwin T1 - The multi-scale dust formation in substellar atmospheres N2 - Substellar atmospheres are observed to be irregularly variable for which the formation of dust clouds is the most promising candidate explanation. The atmospheric gas is convectively unstable and, last but not least, colliding convective cells are seen as cause for a turbulent fluid field. Since dust formation depends on the local properties of the fluid, turbulence influences the dust formation process and may even allow the dust formation in an initially dust-hostile gas. A regime-wise investigation of dust forming substellar atmospheric situations reveals that the largest scales are determined by the interplay between gravitational settling and convective replenishment which results in a dust-stratified atmosphere. The regime of small scales is determined by the interaction of turbulent fluctuations. Resulting lane-like and curled dust distributions combine to larger and larger structures. We compile necessary criteria for a subgrid model in the frame of large scale simulations as result of our study on small scale turbulence in dust forming gases. T3 - ZIB-Report - 03-34 KW - dust formation KW - turbuelnce KW - multi-scale problem KW - substellar atmosphere Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7567 ER - TY - GEN A1 - Lutz, Frank H. T1 - Triangulated Manifolds with Few Vertices: Geometric 3-Manifolds N2 - We explicitly construct small triangulations for a number of well-known $3$-dimensional manifolds and give a brief outline of some aspects of the underlying theory of $3$-manifolds and its historical development. T3 - ZIB-Report - 03-36 KW - triangulating manifolds KW - 3-manifolds KW - geometrization conjecture KW - 3-dimensional geometries KW - Seifert manifolds KW - torus bundles Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7583 ER - TY - GEN A1 - Bley, Andreas A1 - Zymolka, Adrian T1 - Planung kostenoptimaler Informations- und Kommunikations-Infrastrukturen N2 - Beim Entwurf und Ausbau von Informations- und Kommunikationsnetzwerken m{ü}ssen zahlreiche interdependente Entscheidungen getroffen und gleichzeitig mannigfaltige Bedingungen ber{ü}cksichtigt werden. Die verf{ü}gbaren technischen und organisatorischen Alternativm{ö}glichkeiten sind normalerweise so vielf{ä}ltig und komplex, dass eine manuelle Planung praktisch nicht m{ö}glich ist. In diesem Artikel wird das Potential und die Methodik der mathematischen Optimierung bei der kostenoptimalen Planung von Kommunikationsnetzen vorgestellt. Als Ausgangspunkt wird exemplarisch eine typische praktische Aufgabe, die Struktur- und Konfigurationsplanung mehrstufiger Telekommunikationsnetzwerke, dargestellt. Anschließend werden kurz die wesentlichen Modellierungstechniken und Verfahrensans{ä}tze der mathematischen Optimierung skizziert. Abschließend gehen wir auf die Planung einer ad{ä}quaten Informations- und Kommunikations- Infrastruktur f{ü}r ein dezentrales Energieversorgungsnetz ein. T3 - ZIB-Report - 03-37 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7591 ER - TY - GEN A1 - Burger, Sven A1 - Klose, Roland A1 - Schädle, Achim A1 - Zschiedrich, Lin T1 - HelmPole - A finite element solver for scattering problems on unbounded domains: Implementation based on PML N2 - The solution of scattering problems described by the Helmholtz equation on unbounded domains is of importance for a wide variety of applications, for example in electromagnetics and acoustics. An implementation of a solver for scattering problems based on the programming language Matlab is introduced. The solver relies on the finite-element-method and on the perfectly-matched-layer-method, which allows for the simulation of scattering problems on complex geometries surrounded by inhomogeneous exterior domains. This report gives a number of detailed examples and can be understood as a user manual to the freely accessible code of the solver HelmPole. T3 - ZIB-Report - 03-38 KW - Helmholtz equation KW - finite element method KW - perfectly matched layer Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7609 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing Decisions N2 - We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results. T3 - ZIB-Report - 03-09 KW - survivable network design KW - link and path restoration KW - hardware configuration KW - branch-and-cut algorithm KW - routing Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7316 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Polyhedral Investigations on Stable Multi-Sets N2 - Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities. T3 - ZIB-Report - 03-10 KW - stable multi-sets KW - polyhedral combinatorics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7324 ER - TY - GEN A1 - Woitke, Peter A1 - Helling, Christiane T1 - Formation and structure of quasi-static cloud-layers in brown dwarf atmospheres N2 - In this paper, first solutions of the dust moment equations developed in [{\sl Woitke & Helling 2002}] for the description of dust formation and precipitation in brown dwarf and giant gas planet atmospheres are presented. We consider the special case of a static brown dwarf atmosphere, where dust particles continuously nucleate from the gas phase, grow by the accretion of molecules, settle gravitationally and re-evaporate thermally. Applying a kinetic description of the relevant microphysical and chemical processes for TiO$_2$-grains, the model makes predictions about the large-scale stratification of dust in the atmosphere, the depletion of molecules from the gas phase, the supersaturation of the gas in the atmosphere as well as the mean size and the mass fraction of dust grains as function of depth. Our results suggest that the nucleation occu in the upper atmosphere where the gas is cool, strongly depleted, but nevertheless highly supersaturated ($S\!\gg\!1$). These particles settle gravitationally and populate the warmer layers below, where the in-situ formation (nucleation) is ineffective or even not possible. During their descent, the particles grow up to radii $\approx\!0.3\,\mu{\rm m}\,...\,150\,\mu{\rm m}$, depending gas around the cloud base. The particles finally sink into layers which are sufficiently hot to cause their thermal evaporation. Hence, an effective transport mechanism for condensable elements exi considered solid/liquid material. In the stationary case studied here, this downward directed element transport by precipitating dust grains is balanced by an upward directed flux of condensable elements from the deep interior of the star via convective mixing (no dust without mixing). We find a self-regulation mechanism which leads to an approximate phase equilibrium ($S\!\approx\!1$) around the cloud base. The mass fraction of dust present in the atmosphere results be to approximately given by the mass fraction of condensable elements in the gas being mixed up. T3 - ZIB-Report - 03-11 KW - dust KW - precipitation KW - clouds KW - atmosphere Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7338 ER - TY - GEN A1 - Coja-Oghlan, Amin A1 - Krumke, Sven A1 - Nierhoff, Till T1 - Average Case Analysis of a Hard Dial-a-Ride Problem N2 - In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case. T3 - ZIB-Report - 03-12 KW - dial-a-ride-problem KW - average case analysis KW - MST-heuristic KW - Steiner trees KW - NP-hardness Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7348 ER - TY - GEN A1 - Becchetti, Luca A1 - Leonardi, Stefano A1 - Marchetti-Spaccamela, Alberto A1 - Schäfer, Guido A1 - Vredeveld, Tjark T1 - Smoothening Helps: A Probabilistic Analysis of the Multi-Level Feedback Algorithm N2 - In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by [{\sl Spielman and Teng} STOC 2001] to explain the behaviour of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, where the initial processing times are smoothened by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O(max((2^k/\sigma)^3, (2^k/\sigma)^2 2^K-k))$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^K-k)$ if $\sigma = \Theta(2^k)$. %The analysis holds for an oblivious as well as for a stronger adaptive %adversary. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, including the additive symmetric smoothening model used by [{\sl Spielman and Teng}], we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution. T3 - ZIB-Report - 03-14 KW - smoothed analysis KW - competitive analysis KW - scheduling Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7366 ER - TY - GEN A1 - Dalitz, Wolfgang A1 - Neun, Winfried A1 - Sperber, Wolfram T1 - Semantic Annotation in Mathematics and Math-Net N2 - The Web of the future will provide a huge amount of information. We need better ways for dealing with and managing the information. A qualified semantic annotation of the information plays a key role for the Web of the future. This article gives an overview about the efforts of the mathematical community to build up a distributed and open information and communication system for mathematics: the Math-Net. The Math-Net Initiative has developed metadata schemas for some classes of Web resources which are relevant in mathematics. Math-Net Services process this information and enable the user to efficiently search and access the information. T3 - ZIB-Report - 03-15 KW - information and communication system for mathematics KW - Math-Net Semantic Webdata schemas Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7379 ER - TY - GEN A1 - Kähler, Ralf A1 - Hege, Hans-Christian T1 - Visualization of Time-Dependent Adaptive Mesh Refinement Data N2 - Analysis of phenomena that simultaneously occur on quite different spatial and temporal scales require adaptive, hierarchical schemes to reduce computational and storage demands. For data represented as grid functions, the key are adaptive, hierarchical, time-dependent grids that resolve spatio-temporal details without too much redundancy. Here, so-called AMR grids gain increasing popularity. For visualization and feature identification/tracking, the underlying continuous function has to be faithfully reconstructed by spatial and temporal interpolation. Well designed interpolation methods yield better results and help to reduce the amount of data to be stored. We address the problem of temporal interpolation of AMR grid data, e.g.\ for creation of smooth animations or feature tracking. Intermediate grid hierarchies are generated by merging the cells on all refinement levels that are present in the key frames considered. Utilizing a clustering algorithm a structure of nested grids is induced on the resulting collection of cells. The grid functions are mapped to the intermediate hierarchy, thus allowing application of appropriate interpolation techniques. T3 - ZIB-Report - 03-16 KW - AMR KW - non-conforming hexahedral grids KW - multi-resolution techniques Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7384 ER - TY - GEN A1 - Benger, Werner A1 - Hege, Hans-Christian T1 - Tensor Splats N2 - An improved general-purpose technique for the visualization of symmetric positive definite tensor fields of rank two is described. It is based on a splatting technique that is built from tiny transparent glyph primitives which are capable to incorporate the full directional information content of a tensor. The result is an information-rich image that allows to read off the preferred directions in a tensor field at each point of a three-dimensional volume or two-dimensional surface. It is useful for analyzing slices or volumes of a three-dimensional tensor field and can be overlayed with standard volume rendering or color mapping. The application of the rendering technique is demonstrated on general relativistic data and the diffusion tensor field of a human brain. T3 - ZIB-Report - 03-17 KW - tensor field visualization KW - metric KW - splatting KW - volume rendering KW - general relativity KW - diffusion tensor images Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7393 ER - TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - A sample path relation for the sojourn times in G/G/1-PS systems and its applications N2 - For the general G/G/1 processor sharing (PS) system a sample path result for the sojourn times in a busy period is proved, which yields a relation between the sojourn times under PS and FCFS discipline. In particular, the result provides a formula for the mean sojourn time in G/D/1-PS in terms of the mean sojourn time in the corresponding G/D/1-FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of the formula provide the basis for a two-moment approximation of the mean sojourn time in G/GI/1-PS in terms of a related G/D/1-FCFS. T3 - ZIB-Report - 03-18 KW - G/G/1 KW - G/GI/1 KW - G/D/1 KW - G/M/1 KW - processor sharing KW - sojourn time KW - waiting time KW - busy period KW - sample path KW - first come first served KW - two-moment ap Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7401 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Online-Dispatching of Automobile Service Units N2 - We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association. T3 - ZIB-Report - 02-44 KW - vehicle dispatching KW - soft time windows KW - online KW - real-time KW - ADAC Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7117 ER -