@misc{KoepfSchmersau1996, author = {Koepf, Wolfram and Schmersau, Dieter}, title = {Algorithms for Classical Orthogonal Polynomials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2340}, number = {SC-96-23}, year = {1996}, abstract = {\begin{enumerate} \item[] {{\small In this article explicit formulas for the recurrence equation \[ p_{n+1}(x)=(A_n\,x+B_n)\,p_n(x)-C_n\,p_{n-1}(x) \] and the derivative rules \[ \sigma(x)\,p_n'(x)=\alpha_n\,p_{n+1}(x)+\beta_n\,p_n(x)+\gamma_n\,p_{n-1}(x) \] and \[ \sigma(x)\,p_n'(x)=(\tilde\alpha_n\,x+\tilde\beta_n)\,p_n(x)+ \tilde\gamma_n\,p_{n-1}(x) \] respectively which are valid for the orthogonal polynomial solutions \$p_n(x)\$ of the differential equation \[ \sigma(x)\,y''(x)+\tau(x)\,y'(x)+\lambda_n\,y(x)=0 \] of hypergeometric type are developed that depend {\sl only} on the coefficients \$\sigma(x)\$ and \$\tau(x)\$ \% and \$\lambda_n\$ which themselves are polynomials w.r.t.\ \$x\$ of degrees not larger than \$2\$ and \$1\$\% and \$0\$ , respectively. Partial solutions of this problem had been previously published by Tricomi, and recently by Y\'a\~nez, Dehesa and Nikiforov. Our formulas yield an algorithm with which it can be decided whether a given holonomic recurrence equation (i.e.\ one with polynomial coefficients) generates a family of classical orthogonal polynomials, and returns the corresponding data (density function, interval) including the standardization data in the affirmative case. In a similar way, explicit formulas for the coefficients of the recurrence equation and the difference rule \[ \sigma(x)\,\nabla p_n(x)= \alpha_n\,p_{n+1}(x)+\beta_n\,p_n(x)+\gamma_n\,p_{n-1}(x) \] of the classical orthogonal polynomials of a discrete variable are given that depend only on the coefficients \$\sigma(x)\$ and \$\tau(x)\$ of their difference equation \[ \sigma(x)\,\Delta\nabla y(x)+\tau(x)\,\Delta y(x)+\lambda_n\,y(x)=0 \;. \] Here \[ \Delta y(x)=y(x+1)-y(x) \quad\quad\mbox{and}\quad\quad \nabla y(x)=y(x)-y(x-1) \] denote the forward and backward difference operators, respectively. In particular this solves the corresponding inverse problem to find the classical discrete orthogonal polynomial solutions of a given holonomic recurrence equation. \iffalse Furthermore, an algorithmic approach to deduce these and similar properties is presented which is implementable in computer algebra, and which moreover generates relations between different standardizations of the polynomial system considered. \fi }} \end{enumerate}}, language = {en} } @misc{Koepf1996, author = {Koepf, Wolfram}, title = {Gr{\"o}bner Bases and Triangles}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2350}, number = {SC-96-24}, year = {1996}, abstract = {It is well-known that by polynomial elimination methods, in particular by the computation of Gr{\"o}bner bases, proofs for geometric theorems can be automatically generated. \%\% Several monographs On the other hand, it is much less known that Gr{\"o}bner bases, in combination with rational factorization, can be even used to {\sl find} new geometric theorems. In this article such a method is described, and some new theorems on plane triangles are deduced.}, language = {en} } @misc{BornemannKrause1996, author = {Bornemann, Folkmar A. and Krause, Rolf}, title = {Classical and Cascadic Multigrid - A Methodical Comparison}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2368}, number = {SC-96-25}, year = {1996}, abstract = {Using the full multigrid method {\em without} any coarse grid correction steps but with an a posteriori control of the number of smoothing iterations was shown by Bornemann and Deuflhard [1996] to be an optimal iteration method with respect to the energy norm. They named this new kind of multigrid iteration the {\em cascadic multigrid method}. However, numerical examples with {\em linear} finite elements raised serious doubts whether the cascadic multigrid method can be made optimal with respect to the {\em \$L^2\$-norm}. In this paper we prove that the cascadic multigrid method cannot be optimal for linear finite elements and show that the case might be different for higher order elements. We present a careful analysis of the two grid variant of the cascadic multigrid method providing a setting where one can understand the methodical difference between the cascadic multigrid method and the classical multigrid \$V\$-cycle almost immediately. As a rule of thumb we get that whenever the cascadic multigrid works the classical multigrid will work too but not vice versa.}, language = {en} } @misc{Loebel1996, author = {L{\"o}bel, Andreas}, title = {Vehicle Scheduling in Public Transit and Lagrangean Pricing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2375}, number = {SC-96-26}, year = {1996}, abstract = {This paper investigates the solution of the linear programming (LP) relaxation of the multicommodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. We develop a column generation technique that makes it possible to solve the huge linear programs that come up there. The technique, which we call {\em Lagrangean pricing}, is based on two different Lagrangean relaxations. We describe in detail the basic ingredients of our approach and give computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies. Because of these results, we propose Lagrangean pricing as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality.}, language = {en} } @misc{DeuflhardHerothMaas1996, author = {Deuflhard, Peter and Heroth, J{\"o}rg and Maas, Ulrich}, title = {Towards Dynamical Dimension Reduction in Reactive Flow Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2383}, number = {SC-96-27}, year = {1996}, abstract = {The paper addresses the possibilities of reducing the overall number of degrees of freedom in large scale reactive flow computations. Attention focusses on the dimension reduction technique ILDM due to {\sc Maas and Pope}, which treats certain automatically detected fast dynamic components as algebraic equations (so-called slow manifold). In earlier papers, the dimension of the reduction had been kept constant throughout each computation. Recently, a mathematically sound and nevertheless cheap dimension monitor for the chemistry part only has been suggested by {\sc Deuflhard and Heroth}. The present paper reports about first steps taken towards the implementation of that monitor into a flame code. Moreover, a sparse grid storage scheme is advocated and analyzed in view of the construction of efficient table look--ups for nested manifolds.}, language = {en} } @misc{Lang1996, author = {Lang, Jens}, title = {Adaptive FEM for Reaction-Diffusion Equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2393}, number = {SC-96-28}, year = {1996}, abstract = {An integrated time--space adaptive finite element method for solving mixed systems of nonlinear parabolic, elliptic, and differential algebraic equations is presented. The approach is independent of the spatial dimension. For the discretization in time we use singly diagonally linearly implicit Runge--Kutta methods of Rosenbrock type. Local time errors for the step size control are defined by an embedded strategy. A multilevel finite element Galerkin method is subsequently applied for the discretization in space. A posteriori estimates of local spatial discretization errors are obtained solving local problems with higher order approximation. Superconvergence arguments allow to simplify the required computations. Two different strategies to obtain the start grid of the multilevel process are compared. The devised method is applied to a solid--solid combustion problem.}, language = {en} } @misc{DeuflhardWeiser1996, author = {Deuflhard, Peter and Weiser, Martin}, title = {Local Inexact Newton Multilevel FEM for Nonlinear Elliptic Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2401}, number = {SC-96-29}, year = {1996}, abstract = {The finite element setting for nonlinear elliptic PDEs directly leads to the minimization of convex functionals. Uniform ellipticity of the underlying PDE shows up as strict convexity of the arising nonlinear functional. The paper analyzes computational variants of Newton's method for convex optimization in an affine conjugate setting, which reflects the appropriate affine transformation behavior for this class of problems. First, an affine conjugate Newton--Mysovskikh type theorem on the local quadratic convergence of the exact Newton method in Hilbert spaces is given. It can be easily extended to inexact Newton methods, where the inner iteration is only approximately solved. For fixed finite dimension, a special implementation of a Newton--PCG algorithm is worked out. In this case, the suggested monitor for the inner iteration guarantees quadratic convergence of the outer iteration. In infinite dimensional problems, the PCG method may be just formally replaced by any Galerkin method such as FEM for linear elliptic problems. Instead of the algebraic inner iteration errors we now have to control the FE discretization errors, which is a standard task performed within any adaptive multilevel method. A careful study of the information gain per computational effort leads to the result that the quadratic convergence mode of the Newton--Galerkin algorithm is the best mode for the fixed dimensional case, whereas for an adaptive variable dimensional code a special linear convergence mode of the algorithm is definitely preferable. The theoretical results are then illustrated by numerical experiments with a {\sf NEWTON--KASKADE} algorithm.}, language = {en} } @misc{BixbyMartin1996, author = {Bixby, Robert E. and Martin, Alexander}, title = {Parallelizing the Dual Simplex Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2112}, number = {SC-95-45}, year = {1996}, abstract = {We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Sun S20-502, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.}, language = {en} } @misc{StallingSteinke1996, author = {Stalling, Detlev and Steinke, Thomas}, title = {Visualization of Vector Fields in Quantum Chemistry}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2124}, number = {SC-96-01}, year = {1996}, abstract = {\small Many interesting phenomena in molecular systems like interactions between macro-molecules, protein-substrate docking, or channeling processes in membranes are gouverned to a high degree by classical Coulomb or van-der-Waals forces. The visualization of these force fields is important for verifying numerical simulations. Moreover, by inspecting the forces visually we can gain deeper insight into the molecular processes. Up to now the visualization of vector fields is quite unusual in computational chemistry. In fact many commercial software packages do not support this topic at all. The reason is not that vector fields are considered unimportant, but mainly because of the lack of adequate visualization methods. In this paper we survey a number of methods for vector field visualization, ranging from well-known concepts like arrow or streamline plots to more advanced techniques like line integral convolution, and show how these can be applied to computational chemistry. A combination of the most meaningful methods in an interactive 3D visualization environment can provide a powerful tool box for analysing simulations in molecular dynamics.}, language = {en} } @misc{DeuflhardFrieseSchmidtetal.1996, author = {Deuflhard, Peter and Friese, Tilmann and Schmidt, Frank and M{\"a}rz, Reinhard and Nolting, Hans-Peter}, title = {Effiziente Eigenmodenberechnung f{\"u}r den Entwurf integriert-optischer Chips}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2131}, number = {SC-96-02}, year = {1996}, abstract = {{\bf Efficient eigenmode computation for the design of integrated optical chips.}The paper deals with adaptive multigrid methods for 2D Helmholtz eigenvalue problems arising in the design of integrated optical chips. Typical features of the technological problem are its geometric complexity, its multiscale structure, the possible occurrence of eigenvalue clusters, and the necessity of quite stringent required relative error tolerances. For reasons of sheer computational complexity, multigrid methods must be used to solve the discretized eigenvalue problems and adaptive grids must be automatically constructed to avoid an undesirable blow-up of the required number of nodes for these accuracies. In view of the problem specifications, an adaptive multigrid method based on Rayleigh quotient minimization, simultaneous eigenspace iteration, and conjugate gradient method as smoother is carefully selected. Its performance in the numerical simulation of a component of a rather recent optical chip (heterodyne receiver of HHI) is documented.}, language = {de} } @misc{DentchevaMoellerReehetal.1996, author = {Dentcheva, Darinka and M{\"o}ller, Andris and Reeh, Peter and R{\"o}misch, Werner and Schultz, R{\"u}diger and Schwarzbach, Gert and Thomas, J{\"o}rg}, title = {Optimale Blockauswahl bei der Kraftwerkseinsatzplanung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2144}, number = {SC-96-03}, year = {1996}, abstract = {The paper addresses the unit commitment problem in power plant operation planning. For a real power system comprising coal and gas fired thermal as well as pumped storage hydro plants a large-scale mixed integer optimization model for unit commitment is developed. Then primal and dual approaches to solving the optimization problem are presented and results of test runs are reported.}, language = {de} } @misc{Reich1996, author = {Reich, Sebastian}, title = {Smoothed Langevin dynamics of highly oscillatory systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2157}, number = {SC-96-04}, year = {1996}, abstract = {In this paper we generalize a result by Rubin and Ungar on Hamiltonian systems containing a strong constraining potential to Langevin dynamics. Such highly oscillatory systems arise, for example, in the context of molecular dynamics. We derive constrained equations of motion for the slowly varying solution components. This includes in particular the derivation of a correcting force-term that stands for the coupling of the slow and fast degrees of motion. We will identify two limiting cases: (i) the correcting force becomes, over a finite interval of time, almost identical to the force term suggested by Rubin and Ungar (weak thermal coupling) and (ii) the correcting force can be approximated by the gradient of the Fixman potential as used in statistical mechanics (strong thermal coupling). The discussion will shed some light on the question which of the two correcting potentials is more appropriate under which circumstances for molecular dynamics. In Sec.~7, we also discuss smoothing in the context of constant temperature molecular dynamics.}, language = {en} } @misc{FroehlichLang1996, author = {Fr{\"o}hlich, Jochen and Lang, Jens}, title = {Twodimensional Cascadic Finite Element Computations of Combustion Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2167}, number = {SC-96-05}, year = {1996}, abstract = {We present an integrated time--space adaptive finite element method for solving systems of twodimensional nonlinear parabolic systems in complex geometry. The partial differential system is first discretized in time using a singly linearly implicit Runge--Kutta method of order three. Local time errors for the step size control are defined by an embedding strategy. These errors are used to propose a new time step by a PI controller algorithm. A multilevel finite element method with piecewise linear functions on unstructured triangular meshes is subsequently applied for the discretization in space. The local error estimate of the finite element solution steering the adaptive mesh refinement is obtained solving local problems with quadratic trial functions located essentially at the edges of the triangulation. This two--fold adaptivity successfully ensures an a priori prescribed tolerance of the solution. The devised method is applied to laminar gaseous combustion and to solid--solid alloying reactions. We demonstrate that for such demanding applications the employed error estimation and adaption strategies generate an efficient and versatile algorithm.}, language = {en} } @misc{KoepfSchmersau1996, author = {Koepf, Wolfram and Schmersau, Dieter}, title = {Weinstein's Functions and the Askey-Gasper Identity}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2175}, number = {SC-96-06}, year = {1996}, abstract = {\iffalse Recently, Todorov and Wilf independently realized that de Branges' original proof of the Bieberbach and Milin conjectures and the proof that was later given by Weinstein deal with the same special function system that de Branges had introduced in his work. In this article, we present an elementary proof of this statement based on the defining differential equations system rather than the closed representation of de Branges' function system. Our proof does neither use special functions (like Wilf's) nor the residue theorem (like Todorov's) nor the closed representation (like both), but is purely algebraic. On the other hand, by a similar algebraic treatment, the closed representation of de Branges' function system is derived. Our whole contribution can be looked at as the study of properties of the Koebe function. Therefore, in a very elementary manner it is shown that the known proofs of the Bieberbach and Milin conjectures can be understood as a consequence of the L{\"o}wner differential equation, plus properties of the Koebe function. \fi In his 1984 proof of the Bieberbach and Milin conjectures de Branges used a positivity result of special functions which follows from an identity about Jacobi polynomial sums that was found by Askey and Gasper in 1973, published in 1976. In 1991 Weinstein presented another proof of the Bieberbach and Milin conjectures, also using a special function system which (by Todorov and Wilf) was realized to be the same as de Branges'. In this article, we show how a variant of the Askey-Gasper identity can be deduced by a straightforward examination of Weinstein's functions which intimately are related with a L{\"o}wner chain of the Koebe function, and therefore with univalent functions.}, language = {en} } @misc{Loebel1996, author = {L{\"o}bel, Andreas}, title = {Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2184}, number = {SC-96-07}, year = {1996}, abstract = {This paper presents a large-scale real-world application of the minimum-cost flow problem, describes some details of a new implementation of the network simplex algorithm, and reports on computational comparisions. The real-world test sets include minimum-cost flow problems that are based on single-depot vehicle scheduling problems and on a Lagrangean relaxation of multiple-depot vehicle scheduling problems. Some of the problems are extremely large with up to 42,000 nodes and 20,000,000 arcs. The standard test problems are generated with NETGEN and include parts of the DIMACS standard problems. Our network simplex code is compared with \mbox{RELAX-IV}, Cost Scaling 2 version 3.4, and CPLEX's network solver NETOPT.}, language = {en} } @misc{GroetschelLoebelVoelker1996, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2195}, number = {SC-96-08}, year = {1996}, abstract = {This paper addresses the problem of scheduling vehicles in a public mass transportation system. We show how this problem can be modelled as a special multicommodity flow problem and outline the solution methodology we have developed. Based on polyhedral investigations, we have designed and implemented a branch\&cut algorithm and various heuristics with which real vehicle scheduling problems of truely large scale can be solved to optimality. We describe some implementation issues and report computational results.}, language = {de} } @misc{Rojas1996, author = {Rojas, Raul}, title = {Sixty Years of Computation - The Machines of Konrad Zuse}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2203}, number = {SC-96-09}, year = {1996}, abstract = {This paper provides the {\em first} detailed description of the architecture of the computing machines Z1 and Z3 designed by Konrad Zuse in Berlin between 1936 to 1941. The necessary information was obtained from a careful evaluation of the patent application filed by Zuse in 1941. Additional insight was gained from a software simulation of the machine's logic. The Z1 was built using purely mechanical components, the Z3 using electromechanical relays. However, both machines shared a common logical structure and the programming model was exactly the same. We argue that both the Z1 and the Z3 possessed features akin to those of modern computers: memory and processor were separate units, the processor could handle floating-point numbers and compute the four basic arithmetical operations as well as the square root of a number. The program was stored on punched tape and was read sequentially. In the last section of this paper we bring the architecture of the Z1 and Z3 into historical perspective by offering a comparison with computing machines built in other countries.}, language = {en} } @misc{HelmbergRendl1995, author = {Helmberg, Christoph and Rendl, Franz}, title = {Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cuttings Planes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2012}, number = {SC-95-35}, year = {1995}, abstract = {We present computational experiments for solving quadratic \$(0,1)\$ problems. Our approach combines a semidefinite relaxation with a cutting plane technique, and is applied in a Branch and Bound setting. Our experiments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 binary variables, in a routine manner.}, language = {en} } @misc{ThomasWeismantel1995, author = {Thomas, Rekha R. and Weismantel, Robert}, title = {Test sets and inequalities for integer programs: extended abstract}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2021}, number = {SC-95-36}, year = {1995}, abstract = {This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix \$A\$ transforms to the state polytope as we pass from linear programs that have \$A\$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.}, language = {en} } @misc{HelmbergRendlWeismantel1995, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2031}, number = {SC-95-37}, year = {1995}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} } @misc{LoebelStrubbe1995, author = {L{\"o}bel, Andreas and Strubbe, Uwe}, title = {Wagenumlaufoptimierung - Methodischer Ansatz und praktische Anwendung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2047}, number = {SC-95-38}, year = {1995}, abstract = {Im Rahmen des EDV-gest{\"u}tzten Systems zur {\bf{}BE}t{\bf{}R}iebseinsa{\bf{}T}zplanung und -{\bf{}A}uswertung (BERTA) der Berliner Verkehrsbetriebe (BVG) wird ein Modul zur Wagenumlaufoptimierung realisiert. In diesem Aufsatz berichten wir {\"u}ber die betrieblichen Anforderungen und Nebenbedingungen an eine mathematische Optimierung und erl{\"a}utern unsere Konzepte zur Realisierung eines exakten mathematischen Verfahrens.}, language = {de} } @misc{BornemannSchuette1995, author = {Bornemann, Folkmar A. and Sch{\"u}tte, Christof}, title = {Homogenization of Highly Oscillatory Hamiltonian Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2050}, number = {SC-95-39}, year = {1995}, abstract = {The paper studies Hamiltonian systems with a strong potential forcing the solutions to oscillate on a very small time scale. In particular, we are interested in the limit situation where the size \$\epsilon\$ of this small time scale tends to zero but the velocity components remain oscillating with an amplitude variation of order \${\rm O}(1)\$. The process of establishing an effective initial value problem for the limit positions will be called {\em homogenization} of the Hamiltonian system. This problem occurs in mechanics as the problem of realization of holonomic constraints, in plasma physics as the problem of guiding center motion, in the simulation of biomolecules as the so called smoothing problem. We suggest the systematic use of the notion of {\em weak convergence} in order to approach this problem. This methodology helps to establish unified and short proofs of the known results which throw light on the inherent structure of the problem. Moreover, we give a careful and critical review of the literature.}, language = {en} } @misc{Nettesheim1995, author = {Nettesheim, Peter}, title = {An Explicit and Symplectic Integrator for Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2062}, number = {SC-95-40}, year = {1995}, abstract = {This paper presents an explicit and symplectic integrator called PICKABACK for quantum-classical molecular dynamics. This integration scheme is time reversible and unitary in the quantum part. We use the Lie formalism in order to construct a formal evolution operator which then is split using the Strang splitting yielding the symplectic discretization PICHABACK. Finally the new method is compared with a hybrid method in application to two examples: a collinear collision with a quantum oscillator and additionally a photodissociation process of a collinear ArHCI-molecule.}, language = {en} } @misc{DahlMartinStoer1995, author = {Dahl, Geir and Martin, Alexander and Stoer, Mechthild}, title = {Routing through virtual paths in layered telecommunication networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2070}, number = {SC-95-41}, year = {1995}, abstract = {We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0-1 variables represent different paths. An associated integral polytope is studied and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported.}, language = {en} } @misc{Koepf1995, author = {Koepf, Wolfram}, title = {Efficient Computation of Orthogonal Polynomials in Computer Algebra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2080}, number = {SC-95-42}, year = {1995}, abstract = {Orthogonal polynomials \%like the Chebyshev polynomials can be calculated by computation of determinants, by the use of generating functions, in terms of Rodrigues formulas, by iterating recurrence equations, calculating the polynomial solutions of differential equations, through closed form representations and by other means. In this article, we give an overview about the efficiency of the above methods in Maple, Mathematica, and REDUCE. As a noncommercial package we include the MuPAD system.}, language = {en} } @misc{BunkeDrogePolzehl1995, author = {Bunke, Olaf and Droge, Bernd and Polzehl, J{\"o}rg}, title = {Model Selection, Transformations and Variance Estimation in Nonlinear Regression}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2096}, number = {SC-95-43}, year = {1995}, abstract = {The results of analyzing experimental data using a parametric model may heavily depend on the chosen model. In this paper we propose procedures for the adequate selection of nonlinear regression models if the intended use of the model is among the following: 1. prediction of future values of the response variable, 2. estimation of the unknown regression function, 3. calibration or 4. estimation of some parameter with a certain meaning in the corresponding field of application. Moreover, we propose procedures for variance modelling and for selecting an appropriate nonlinear transformation of the observations which may lead to an improved accuracy. We show how to assess the accuracy of the parameter estimators by a "moment oriented bootstrap procedure". This procedure may also be used for the construction of confidence, prediction and calibration intervals. Programs written in Splus which realize our strategy for nonlinear regression modelling and parameter estimation are described as well. The performance of the selected model is discussed, and the behaviour of the procedures is illustrated by examples.}, language = {en} } @misc{BunkeDrogePolzehl1995, author = {Bunke, Olaf and Droge, Bernd and Polzehl, J{\"o}rg}, title = {Splus Tools for Model Selection in Nonlinear Regression}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2104}, number = {SC-95-44}, year = {1995}, abstract = {The results of analyzing experimental data using a parametric model may heavily depend on the chosen model. With this paper we describe computational tools in Splus for the adequate selection of nonlinear regression models if the intended use of the model is among the following: 1. estimation of the unknown regression function, 2. prediction of future values of the response variable, 3. calibration or 4. estimation of some parameter with a certain meaning in the corresponding field of application. Moreover, we provide programs for variance modelling and for selecting an appropriate nonlinear transformation of the observations which may lead to an improved accuracy. We describe how the accuracy of the parameter estimators is assessed by a "moment oriented bootstrap procedure". This procedure is also used for the construction of confidence, prediction and calibration intervals. The use of our tools is illustrated by an example. Help files are given in an appendix.}, language = {en} } @misc{HelmbergWeismantel1997, author = {Helmberg, Christoph and Weismantel, Robert}, title = {Cutting Plane Algorithms for Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2719}, number = {SC-97-02}, year = {1997}, abstract = {We investigate the potential and limits of interior point based cutting plane algorithms for semidefinite relaxations on basis of implementations for max-cut and quadratic 0-1 knapsack problems. Since the latter has not been described before we present the algorithm in detail and include numerical results.}, language = {en} } @misc{SteinbachBockKostinetal.1997, author = {Steinbach, Marc and Bock, H. Georg and Kostin, Georgii V. and Longman, Richard W.}, title = {Mathematical Optimization in Robotics: Towards Automated High Speed Motion Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2722}, number = {SC-97-03}, year = {1997}, abstract = {\def\KukaRob {{\sf KUKA IR\,761}} {\small Industrial robots have greatly enhanced the performance of automated manufacturing processes during the last decades. International competition, however, creates an increasing demand to further improve both the accuracy of off-line programming and the resulting cycle times on production lines. To meet these objectives, validated dynamic robot models are required. We describe in detail the development of a generic dynamic model, specialize it to an actual industrial robot \KukaRob, and discuss the problem of dynamic calibration. Efficient and robust trajectory optimization algorithms are then presented which, when integrated into a CAD system, are suitable for routine application in an industrial environment. Our computational results for the \KukaRob\ robot performing a real life transport maneuver show that considerable gains in productivity can be achieved by minimizing the cycle time.}}, language = {en} } @misc{PflugRuszczynskiSchultz1997, author = {Pflug, Georg Ch. and Ruszczynski, Andrzej and Schultz, R{\"u}diger}, title = {On the Glivenko-Cantelli Problem in Stochastic Programming: Mixed-Integer Linear Recourse}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2739}, number = {SC-97-04}, year = {1997}, abstract = {Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.}, language = {en} } @misc{HegeSeebassStallingetal.1997, author = {Hege, Hans-Christian and Seebass, Martin and Stalling, Detlev and Z{\"o}ckler, Malte}, title = {A Generalized Marching Cubes Algorithm Based on Non-Binary Classifications}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2741}, number = {SC-97-05}, year = {1997}, abstract = {We present a new technique for generating surface meshes from a uniform set of discrete samples. Our method extends the well-known marching cubes algorithm used for computing polygonal isosurfaces. While in marching cubes each vertex of a cubic grid cell is binary classified as lying above or below an isosurface, in our approach an arbitrary number of vertex classes can be specified. Consequently the resulting surfaces consist of patches separating volumes of two different classes each. Similar to the marching cubes algorithm all grid cells are traversed and classified according to the number of different vertex classes involved and their arrangement. The solution for each configuration is computed based on a model that assigns probabilities to the vertices and interpolates them. We introduce an automatic method to find a triangulation which approximates the boundary surfaces - implicitly given by our model - in a topological correct way. Look-up tables guarantee a high performance of the algorithm. In medical applications our method can be used to extract surfaces from a 3D segmentation of tomographic images into multiple tissue types. The resulting surfaces are well suited for subsequent volumetric mesh generation, which is needed for simulation as well as visualization tasks. The proposed algorithm provides a robust and unique solution, avoiding ambiguities occuring in other methods. The method is of great significance in modeling and animation too, where it can be used for polygonalization of non-manifold implicit surfaces.}, language = {en} } @misc{KoepfSchmersau1997, author = {Koepf, Wolfram and Schmersau, Dieter}, title = {Representations of Orthogonal Polynomials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2756}, number = {SC-97-06}, year = {1997}, abstract = {{\small Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computes recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions. In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation. In this article we extend these results be presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible. The main technique is again to use explicit formulas for structural identities of the given polynomial systems.}}, language = {en} } @misc{BornemannSchuette1997, author = {Bornemann, Folkmar A. and Sch{\"u}tte, Christof}, title = {On the Singular Limit of the Quantum-Classical Molecular Dynamics Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2761}, number = {SC-97-07}, year = {1997}, abstract = {\noindent In molecular dynamics applications there is a growing interest in so-called {\em mixed quantum-classical} models. These models describe most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of quantum mechanics. A particularly extensively used model, the QCMD model, consists of a {\em singularly perturbed}\/ Schr{\"o}dinger equation nonlinearly coupled to a classical Newtonian equation of motion. This paper studies the singular limit of the QCMD model for finite dimensional Hilbert spaces. The main result states that this limit is given by the time-dependent Born-Oppenheimer model of quantum theory---provided the Hamiltonian under consideration has a smooth spectral decomposition. This result is strongly related to the {\em quantum adiabatic theorem}. The proof uses the method of {\em weak convergence} by directly discussing the density matrix instead of the wave functions. This technique avoids the discussion of highly oscillatory phases. On the other hand, the limit of the QCMD model is of a different nature if the spectral decomposition of the Hamiltonian happens not to be smooth. We will present a generic example for which the limit set is not a unique trajectory of a limit dynamical system but rather a {\em funnel} consisting of infinitely many trajectories.}, language = {en} } @misc{MarsWolf1997, author = {Mars, Marc and Wolf, Thomas}, title = {G2 Perfect-Fluid Cosmologies with a proper conformal Killing vector}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2774}, number = {SC-97-08}, year = {1997}, abstract = {We study the Einstein field equations for spacetimes admitting a maximal two-dimensional abelian group of isometries acting orthogonally transitively on spacelike surfaces and, in addition, with at least one conformal Killing vector. The three-dimensional conformal group is restricted to the case when the two-dimensional abelian isometry subalgebra is an ideal and it is also assumed to act on non-null hypersurfaces (both, spacelike and timelike cases are studied). We consider both, diagonal and non-diagonal metrics and find all the perfect-fluid solutions under these assumptions (except those already known). We find four families of solutions, each one containing arbitrary parameters for which no differential equations remain to be integrated. We write the line-elements in a simplified form and perform a detailed study for each of these solutions, giving the kinematical quantities of the fluid velocity vector, the energy-density and pressure, values of the parameters for which the energy conditions are fulfilled everywhere, the Petrov type, the singularities in the spacetimes and the Friedmann-Lema\^{\i}tre-Robertson-Walker metrics contained in each family.}, language = {en} } @misc{Giloi1997, author = {Giloi, Wolfgang K.}, title = {Die Ungnade der fr{\"u}hen Geburt}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2780}, number = {SC-97-09}, year = {1997}, abstract = {Konrad Zuse ist unserem Land bekannt als der Computerpionier, der den ersten funktionst{\"u}chtigen Rechner in der Geschichte der Menschheit realisierte. Weniger bekannt ist aber immer noch die Tatsache, daß er mit seinem Plankalk{\"u}l auch die erste h{\"o}here Programmiersprache der Welt entwickelte. Zuse hatte bereits 1945 nicht nur klare Vorstellungen {\"u}ber die Konzepte von h{\"o}heren Programmiersprachen, sondern auch {\"u}ber die Programmierung von Anwendungen der k{\"u}nstlichen Intelligenz wie der relationalen Datenspeicherung oder dem Schachspiel. Dies macht ihn auch zum ersten Informatiker der Welt und dar{\"u}ber hinaus zum Erfinder der k{\"u}nstlichen Intelligenz.}, language = {en} } @misc{AscheuerFischettiGroetschel1997, author = {Ascheuer, Norbert and Fischetti, Matteo and Gr{\"o}tschel, Martin}, title = {A polyhedral study of the asymmetric travelling salesman problem with time windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2807}, number = {SC-97-11}, year = {1997}, abstract = {The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, \$P_{TW}\$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of \$P_{TW}\$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for \$P_{TW}\$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Cost-Efficient Network Synthesis from Leased Lines}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2912}, number = {SC-97-22}, year = {1997}, abstract = {Given a communication demand between each pair of nodes of a network we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. We treat, in addition, several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real world data.}, language = {en} } @misc{AlevrasGroetschelWessaely1997, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Capacity and Survivability Models for Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2931}, number = {SC-97-24}, year = {1997}, abstract = {Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice.}, language = {en} } @misc{DalitzGroetschelLuegger1997, author = {Dalitz, Wolfgang and Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Information Services for Mathematics in the Internet (Math-Net)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2949}, number = {SC-97-25}, year = {1997}, abstract = {The present paper gives a brief description of the Math-Net project which is carried out by nine mathematical institutions in Germany, supported by Deutsches Forschungsnetz (DFN) and Deutsche Telekom. The project aims at setting up the technical and organizational infrastructure for efficient, inexpensive and user-driven information services for mathematics. With the aid of active (structured retrieval mechanisms) and passive (profile services) components, electronic mathematical information in Germany will be made available to the scientist at his workplace. The emphasis is put on information about publications, software and data collections, teaching and research activities, but also on organizational and bibliographical information. Decentral organization structures, distributed search systems as well as the use of meta-information (metadata) in accordance with the Dublin Core (hopefully) guarantee a longterm, high-quality repository of data. The well-known mathematical software and data collection netlib\/ will be used as an example to illustrate how such a collection can be adapted to Math-Net. An integration of netlib into HyperWave offers additional perspectives and functionalities.}, language = {en} } @misc{DeuflhardSeebassStallingetal.1997, author = {Deuflhard, Peter and Seebass, Martin and Stalling, Detlev and Beck, Rudolf and Hege, Hans-Christian}, title = {Hyperthermia Treatment Planning in Clinical Cancer Therapy: Modelling, Simulation and Visualization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2958}, number = {SC-97-26}, year = {1997}, abstract = {\noindent The speaker and his co-workers in Scientific Computing and Visualization have established a close cooperation with medical doctors at the Rudolf--Virchow--Klinikum of the Humboldt University in Berlin on the topic of regional hyperthermia. In order to permit a patient--specific treatment planning, a special software system ({\sf\small HyperPlan}) has been developed. \noindent A mathematical model of the clinical system ({\it radio frequency applicator with 8 antennas, water bolus, individual patient body}) involves Maxwell's equations in inhomogeneous media and a so--called bio--heat transfer PDE describing the temperature distribution in the human body. The electromagnetic field and the thermal phenomena need to be computed at a speed suitable for the clinical environment. An individual geometric patient model is generated as a quite complicated tetrahedral ``coarse'' grid (several thousands of nodes). Both Maxwell's equations and the bio--heat transfer equation are solved on that 3D--grid by means of {\em adaptive} multilevel finite element methods, which automatically refine the grid where necessary in view of the required accuracy. Finally optimal antenna parameters for the applicator are determined . \noindent All steps of the planning process are supported by powerful visualization methods. Medical images, contours, grids, simulated electromagnetic fields and temperature distributions can be displayed in combination. A number of new algorithms and techniques had to be developed and implemented. Special emphasis has been put on advanced 3D interaction methods and user interface issues.}, language = {en} } @misc{Eisenblaetter1997, author = {Eisenbl{\"a}tter, Andreas}, title = {A Frequency Assignment Problem in Cellular Phone Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2965}, number = {SC-97-27}, year = {1997}, abstract = {We present a mathematical formulation of a \emph{frequency assignment problem} encountered in cellular phone networks: frequencies have to be assigned to stationary transceivers (carriers) such that as little interference as possible is induced while obeying several technical and legal restrictions. The optimization problem is NP-hard, and no good approximation can be guaranteed---unless P = NP. We sketch some starting and improvement heuristics, and report on their successful application for solving the frequency assignment problem under consideration. Computational results on real-world instances with up to 2877 carriers and 50 frequencies are presented.}, language = {en} } @misc{TuzaWagler1997, author = {Tuza, Zsolt and Wagler, Annegret}, title = {Minimally non-preperfect graphs of small maximum degree}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2971}, number = {SC-97-28}, year = {1997}, abstract = {A graph \$G\$ is called preperfect if each induced subgraph \$G' \subseteq G\$ of order at least 2 has two vertices \$x,y\$ such that either all maximum cliques of \$G'\$ containing \$x\$ contain \$y\$, or all maximum indepentent sets of \$G'\$ containing \$y\$ contain \$x\$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph \$G\$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if \$G\$ is bipartite, 3-edge-connected, regular of degree \$d\$ for some \$d \ge 3\$, and contains no 3-edge-connected \$d'\$-regular subgraph for any \$3 \le d' \le d\$. \end{itemize}}, language = {en} } @misc{HenkWeismantel1997, author = {Henk, Martin and Weismantel, Robert}, title = {Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2989}, number = {SC-97-29}, year = {1997}, abstract = {This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.}, language = {en} } @misc{Tuza1997, author = {Tuza, Zsolt}, title = {Graph coloring with local constraints - A survey}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3003}, number = {SC-97-31}, year = {1997}, abstract = {We survey the literature on those variants of the {\em chromatic number\/} problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the {\em list colorings\/} and the {\em precoloring extensions\/} are considered. \par In one of the most general formulations, a graph \$G=(V,E)\$, sets \$L(v)\$ of admissible colors, and natural numbers \$c_v\$ for the vertices \$v\in V\$ are given, and the question is whether there can be chosen a subset \$C(v)\subseteq L(v)\$ of cardinality \$c_v\$ for each vertex in such a way that the sets \$C(v),C(v')\$ are disjoint for each pair \$v,v'\$ of adjacent vertices. The particular case of constant \$|L(v)|\$ with \$c_v=1\$ for all \$v\in V\$ leads to the concept of {\em choice number}, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. \par To illustrate typical techniques, some of the proofs are sketched.}, language = {en} } @misc{BeckHiptmair1996, author = {Beck, Rudolf and Hiptmair, Ralf}, title = {Multilevel Solution of the Time-Harmonic Maxwell's Equations Based on Edge Elements}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2619}, number = {SC-96-51}, year = {1996}, abstract = {A widely used approach for the computation of time-harmonic electromagnetic fields is based on the well-known double-curl equation for either \$\vec E\$ or \$\vec H\$. An appealing choice for finite element discretizations are edge elements, the lowest order variant of a \$H(curl)\$-conforming basis. However, the large nullspace of the curl-operator gives rise to serious drawbacks. It comprises a considerable part of all spectral modes on the finite element grid, polluting the solution with non-physical contributions and causing the deterioration of standard iterative solvers. We tackle these problems by a nested multilevel algorithm. After every V-cycle in the \$H(curl)\$-conforming basis, the non-physical contributions are removed by a projection scheme. It requires the solution of Poisson's equation in the nullspace, which can be carried out efficiently by another multilevel iteration. The whole procedure yields convergence rates independent of the refinement level of the mesh. Numerical examples demonstrate the efficiency of the method.}, language = {en} } @misc{Koepf1996, author = {Koepf, Wolfram}, title = {On a Problem of Koornwinder}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2629}, number = {SC-96-52}, year = {1996}, abstract = {In this note we solve a problem about the rational representability of hypergeometric terms which represent hypergeometric sums. This problem was proposed by Koornwinder in Koornwinder, T. H.: Hypergeometric series evaluation by Zeilberger's algorithm. In: Open Problems, ed. by Walter van Assche. J. of Comput. and Appl. Math.48, 1993, 225--243.}, language = {en} } @misc{Koepf1996, author = {Koepf, Wolfram}, title = {A Package on Orthogonal Polynomials and Special Functions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2639}, number = {SC-96-53}, year = {1996}, abstract = {In many applications (hypergeometric-type) special functions like orthogonal polynomials are needed. For example in more than 50 \\% of the published solutions for the (application-oriented) questions in the Problems Section'' of SIAM Review special functions occur. In this article the Mathematica package {\tt SpecialFunctions} which can be obtained from the URL {\tt http://www.zib.de/koepf} is introduced. Algorithms to convert between power series representations and their generating functions is the main topic of this package, extending the previous package {\tt PowerSeries}. Moreover the package automatically finds differential and recurrence equations for expressions and for sums (the latter using Zeilberger's algorithm. As an application the fast computation of polynomial approximations of solutions of linear differential equations with polynomial coefficients is presented. This is the asymptotically fastest known algorithm for series computations, and it is much faster than Mathematica's builtin {\tt Series} command if applicable. Many more applications are considered. Finally the package includes implementations supporting the efficient computation of classical continuous and discrete orthogonal polynomials.}, language = {en} } @misc{BeckDeuflhardHegeetal.1996, author = {Beck, Rudolf and Deuflhard, Peter and Hege, Hans-Christian and Seebass, Martin and Stalling, Detlev}, title = {Numerical Algorithms and Visualization in Medical Treament Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2643}, number = {SC-96-54}, year = {1996}, abstract = {After a short summary on therapy planning and the underlying technologies we discuss quantitative medicine by giving a short overview on medical image data, summarizing some applications of computer based treatment planning, and outlining requirements on medical planning systems. Then we continue with a description of our medical planning system {\sf HyperPlan}. It supports typical working steps in therapy planning, like data aquisition, segmentation, grid generation, numerical simulation and optimization, accompanying these with powerful visualization and interaction techniques.}, language = {en} } @misc{BrandtBrandt1996, author = {Brandt, Andreas and Brandt, Manfred}, title = {A Note on the Stability of the Many-Queue Head-of-the Line Processor-Sharing System with Permanent Customers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2659}, number = {SC-96-55}, year = {1996}, abstract = {We consider a single server system consisting of \$n\$ queues with different types of customers and \$k\$ permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). By means of Loynes' monotonicity method a stationary work load process is constructed and using sample path analysis general stability conditions are derived. They allow to decide which queues are stable and moreover to compute the fraction of processor capacity devoted to the permanent customers. In case of a stable system the constructed stationary state process is the only one and for any initial state the system converges pathwise to the steady state.}, language = {en} } @misc{MaasNowak1996, author = {Maas, Ulrich and Nowak, Ulrich}, title = {An adaptive method of lines for the simulation of complex laminar combustion processes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2665}, number = {SC-96-56}, year = {1996}, abstract = {For the simulation of one-dimensional flame configurations reliabl e numerical tools are needed which have to be both highly efficient (large num ber of parametric calculations) and at the same time accurate (in order t o avoid numerical errors). This can only be accomplished using fully adapt ive discretization techniques both in space and time together with a c ontrol of the discretization error. We present a method which accomplishes this task. It is based on a n adative MOL (method of lines) treatment. Space discretization is done by means of finite difference approxi mations on non-uniform grids. Time is discretized by the linearly-implicit Euler method. In order to control the discretization errors an extrapolation pro cedure is used in space and time. Results are presented for simple laser-induced ignition processes. The method, however, can be applied to other combustion processes, too.}, language = {en} } @misc{FrauhammerKleinEigenbergeretal.1996, author = {Frauhammer, J{\"o}rg and Klein, Harald and Eigenberger, Gerhart and Nowak, Ulrich}, title = {Solving moving boundary problems with an adaptive moving grid method: Rotary heat exchangers with condensation and evaporation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2679}, number = {SC-96-57}, year = {1996}, abstract = {A numerical method for the treatment of moving discontinuities in the model equations of chemical engineering systems is presented. The derived model describing the effects of condensation and evaporation in a regenerative air to air heat exchanger yields an illustrative example for these so called moving boundary problems. The presented adaptive moving grid method is based on the algorithm {\sc Pdex} for parabolic partial differential equations. It is shown that the method is suited for problems where the arising discontinuities cause low rates of convergence if the equations are solved with a static grid.}, language = {en} } @misc{StallingZoecklerHege1997, author = {Stalling, Detlev and Z{\"o}ckler, Malte and Hege, Hans-Christian}, title = {Fast Display of Illuminated Field Lines}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2686}, number = {SC-96-58}, year = {1997}, abstract = {A new technique for interactive vector field visualization using large numbers of properly illuminated field lines is presented. Taking into account ambient, diffuse, and specular reflection terms as well as transparency and depth cueing, we employ a realistic shading model which significantly increases quality and realism of the resulting images. While many graphics workstations offer hardware support for illuminating surface primitives, usually no means for an accurate shading of line primitives are provided. However, we show that proper illumination of lines can be implemented by exploiting the texture mapping capabilities of modern graphics hardware. In this way high rendering performance with interactive frame rates can be achieved. We apply the technique to render large numbers of integral curves of a vector field. The impression of the resulting images can be further improved by a number of visual enhancements, like transparency and depth-cueing. We also describe methods for controlling the distribution of field lines in space. These methods enable us to use illuminated field lines for interactive exploration of vector fields.}, language = {en} } @misc{BattkeStallingHege1997, author = {Battke, Henrik and Stalling, Detlev and Hege, Hans-Christian}, title = {Fast Line Integral Convolution for Arbitrary Surfaces in 3D}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2690}, number = {SC-96-59}, year = {1997}, abstract = {We describe an extension of the line integral convolution method (LIC) for imaging of vector fields on arbitrary surfaces in 3D space. Previous approaches were limited to curvilinear surfaces, i.e.~surfaces which can be parametrized globally using 2D-coordinates. By contrast our method also handles the case of general, possibly multiply connected surfaces. The method works by tesselating a given surface with triangles. For each triangle local euclidean coordinates are defined and a local LIC texture is computed. No scaling or distortion is involved when mapping the texture onto the surface. The characteristic length of the texture remains constant. In order to exploit the texture hardware of modern graphics computers we have developed a tiling strategy for arranging a large number of triangular texture pieces within a single rectangular texture image. In this way texture memory is utilized optimally and even large textured surfaces can be explored interactively.}, language = {en} } @misc{DaisHenkZiegler1997, author = {Dais, Dimitrios I. and Henk, Martin and Ziegler, G{\"u}nter M.}, title = {All Abelian Quotient C.I.-Singularities Admit Projective Crepant Resolutions in All Dimensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2708}, number = {SC-97-01}, year = {1997}, abstract = {\def\Bbb{\mathbb} For Gorenstein quotient spaces \$\Bbb{C}^d/G\$, a direct generalization of the classical McKay correspondence in dimensions \$d\geq 4\$ would primarily demand the existence of projective, crepant desingularizations. Since this turned out to be not always possible, Reid asked about special classes of such quotient spaces which would satisfy the above property. We prove that the underlying spaces of all Gorenstein abelian quotient singularities, which are embeddable as complete intersections of hypersurfaces in an affine space, have torus-equivariant projective crepant resolutions in all dimensions. We use techniques from toric and discrete geometry.}, language = {en} } @misc{BorndoerferGroetschelHerzogetal.1996, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Herzog, Werner and Klostermeier, Fridolin and Konsek, Wilhelm and K{\"u}ttner, Christian}, title = {K{\"u}rzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2510}, number = {SC-96-41}, year = {1996}, abstract = {M{\"u}ssen Etatk{\"u}rzungen bei staatlichen Dienstleistungseinrichtungen notwendig zu Leistungseinschr{\"a}nkungen oder Geb{\"u}hrenerh{\"o}hungen f{\"u}hren? Wir zeigen am Beispiel des Berliner Behindertenfahrdienstes {\em Telebus}, da\ss{} Sparzwang auch als Chance zur Verbesserung der eigenen Verwaltungs- und Arbeitsabl{\"a}ufe genutzt werden kann. Durch st{\"a}rkere Dienstleistungsorientierung, Vereinfachung der Arbeitsabl{\"a}ufe und durch den Einsatz von moderner EDV und von mathematischen Optimierungsmethoden zur Fahrzeugeinsatzplanung werden bei Telebus heute staatliche Leistungen trotz geringeren Etats besser erbracht als vorher.}, language = {de} } @misc{KochMartin1996, author = {Koch, Thorsten and Martin, Alexander}, title = {Solving Steiner Tree Problems in Graphs to Optimality}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2526}, number = {SC-96-42}, year = {1996}, abstract = {In this paper we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms and primal heuristics. We are able to solve all problem instances discussed in literature to optimality, including one to our knowledge not yet solved problem. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called {\em SteinLib} that is accessible via World Wide Web.}, language = {en} } @misc{Helmberg1996, author = {Helmberg, Christoph}, title = {Fixing Variables in Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2530}, number = {SC-96-43}, year = {1996}, abstract = {The standard technique of reduced cost fixing from linear programming is not trivially extensible to semidefinite relaxations as the corresponding Lagrange multipliers are usually not available. We propose a general technique for computing reasonable Lagrange multipliers to constraints which are not part of the problem description. Its specialization to the semidefinite \$\left\{-1,1\right\}\$ relaxation of quadratic 0-1 programming yields an efficient routine for fixing variables. The routine offers the possibility to exploit problem structure. We extend the traditional bijective map between \$\left\{0,1\right\}\$ and \$\left\{-1,1\right\}\$ formulations to the constraints such that the dual variables remain the same and structural properties are preserved. In consequence the fixing routine can efficiently be applied to optimal solutions of the semidefinite \$\left\{0,1\right\}\$ relaxation of constrained quadratic 0-1 programming, as well. We provide numerical results showing the efficacy of the approach.}, language = {en} } @misc{AwyongHenkScott1996, author = {Awyong, Poh Wah and Henk, Martin and Scott, Paul R.}, title = {Note on lattice-point-free convex bodies}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2546}, number = {SC-96-44}, year = {1996}, abstract = {We prove inequalities relating the inradius of a convex body with interior containing no point of the integral lattice, with the volume or surface area of the body. These inequalities are tight and generalize previous results.}, language = {en} } @misc{DeuflhardDellnitzJungeetal.1996, author = {Deuflhard, Peter and Dellnitz, Michael and Junge, Oliver and Sch{\"u}tte, Christof}, title = {Computation of Essential Molecular Dynamics by Subdivision Techniques I: Basic Concept}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2553}, number = {SC-96-45}, year = {1996}, abstract = {The paper presents the concept of a new type of algorithm for the numerical computation of what the authors call the {\em essential dynamics\/} of molecular systems. Mathematically speaking, such systems are described by Hamiltonian differential equations. In the bulk of applications, individual trajectories are of no specific interest. Rather, time averages of physical observables or relaxation times of conformational changes need to be actually computed. In the language of dynamical systems, such information is contained in the natural invariant measure (infinite relaxation time) or in almost invariant sets ("large" finite relaxation times). The paper suggests the direct computation of these objects via eigenmodes of the associated Frobenius-Perron operator by means of a multilevel subdivision algorithm. The advocated approach is different to both Monte-Carlo techniques on the one hand and long term trajectory simulation on the other hand: in our setup long term trajectories are replaced by short term sub-trajectories, Monte-Carlo techniques are just structurally connected via the underlying Frobenius-Perron theory. Numerical experiments with a first version of our suggested algorithm are included to illustrate certain distinguishing properties. A more advanced version of the algorithm will be presented in a second part of this paper.}, language = {en} } @misc{CaroeeSchultz1996, author = {Car{\"o}e, Claus C. and Schultz, R{\"u}diger}, title = {Dual Decomposition in Stochastic Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2560}, number = {SC-96-46}, year = {1996}, abstract = {We present an algorithm for solving stochastic integer programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-integer variables in each time stage. \%We outline a branch-and-bound algorithm for obtaining primal feasible and \%possibly optimal solutions. Numerical experience is presented for some two-stage test problems.}, language = {en} } @misc{NettesheimHuisingaSchuette1996, author = {Nettesheim, Peter and Huisinga, Wilhelm and Sch{\"u}tte, Christof}, title = {Chebyshev-Approximation for Wavepacket-Dynamics: better than expected}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2575}, number = {SC-96-47}, year = {1996}, abstract = {The aim of this work is to study the accuracy and stability of the Chebyshev--approximation method as a time--discretization for wavepacket dynamics. For this frequently used discretization we introduce estimates of the approximation and round--off error. These estimates mathematically confirm the stability of the Chebyshev--approximation with respect to round--off errors, especially for very large stepsizes. But the results also disclose threads to the stability due to large spatial dimensions. All theoretical statements are illustrated by numerical simulations of an analytically solvable example, the harmonic quantum oszillator.}, language = {en} } @misc{AlevrasGroetschelJonasetal.1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Jonas, Peter and Paul, Ulrich and Wess{\"a}ly, Roland}, title = {Survivable Mobile Phone Architectures: Models and Solution Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2582}, number = {SC-96-48}, year = {1996}, abstract = {In the highly competitive area of telecommunications, cost, quality, and network management are among the most important aspects to be considered when designing a network. We study the problem of dimensioning a telecommunication network that is still operating in case of a failure of a network component. Given a demand between each pair of nodes of a telecommunication network and a finite set of possible capacities for each edge of the network, we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes, even if a network component fails. The routing of the demands must satisfy the following additional restrictions: (a) there is a maximum number of nodes allowed in each path between any pair of nodes (path length restriction), and (b) there is a maximum percentage of the demand between each pair of nodes that can be routed through any network component (diversification restriction). Moreover, the chosen capacities must be such that, for every single node or single edge failure, a certain percentage of the demand between any pair of nodes is reroutable (i.e. it ``survives'' the particular failure). We formulate the problem as a mixed integer linear programming problem and present a cutting plane algorithm as well as several heuristics for its solution. Furthermore, we discuss several ways to implement survivability into a telecommunication network.}, language = {en} } @misc{AlevrasGroetschelWessaely1996, author = {Alevras, Dimitris and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {A Network Dimensioning Tool}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2591}, number = {SC-96-49}, year = {1996}, abstract = {Designing low cost networks that survive certain failure situations belongs to one of the prime tasks in the telecommunications industry. In this paper we describe a mathematical model combining several aspects of survivability that are elsewhere treated in a hierarchical fashion. We present mathematical investigations of this integrated model, a cutting plane algorithm, as well as several heuristics for its solution. Moreover, we report computational results with real world data. The problem we address is the following. Suppose, between each pair of nodes in a region, a communication demand is given. We want to determine the topology of a telecommunication network connecting the given nodes and to dimension all potential physical links. For each link, the possible capacities are restricted to a given finite set. The capacities must be chosen such that the communication demands are satisfied, even if certain network components fail, and such that the network building costs are as small as possible. Moreover, for each pair of nodes and each failure situation, we want to determine the paths on which the demand between the nodes is routed.}, language = {en} } @misc{Wagler1996, author = {Wagler, Annegret}, title = {On Critically Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2609}, number = {SC-96-50}, year = {1996}, abstract = {A perfect graph is critical if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We investigate the relationship of critically perfect graphs to well-known classes of perfect graphs and study operations preserving critical perfectness.}, language = {en} } @misc{HelmbergRendlWeismantel1996, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {A Semidefinite Programming Approach to the Quadratic Knapsack Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2211}, number = {SC-96-10}, year = {1996}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} } @misc{FroehlichSchneider1996, author = {Fr{\"o}hlich, Jochen and Schneider, Kai}, title = {Computation of Decaying Turbulence in an Adaptive Wavelet Basis}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2227}, number = {SC-96-11}, year = {1996}, abstract = {The paper presents computations of decaying two--dimensional turbulence in an adaptive wavelet basis. At each time step the vorticity is represented by an adaptively selected set of wavelet functions which adjusts to the instantaneous distribution of vorticity. The results of this new algorithm are compared to a classical Fourier method and a Fourier method supplemented with wavelet compression in each time step.}, language = {en} } @misc{HenkWeismantel1996, author = {Henk, Martin and Weismantel, Robert}, title = {On Hilbert bases of polyhedral cones}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2230}, number = {SC-96-12}, year = {1996}, abstract = {For a polyhedral cone \$C=\$ pos \$\{a^1,\dots,a^m\}\subset R^d\$, \$a^i\in Z^d\$, a subset of integral vectors \$H(C)\subset C \cap Z^d\$ is called a Hilbert basis of \$C\$ iff (i) each element of \$C\cap Z^d\$ can be written as a non-negative integer combination of elements of \$H(C)\$ and (ii) \$H(C)\$ has minimal cardinality with respect to all subsets of \$C \cap Z^d\$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.}, language = {en} } @misc{NowakPoehleRoitzsch1996, author = {Nowak, Ulrich and P{\"o}hle, Uwe and Roitzsch, Rainer}, title = {Eine graphische Oberfl{\"a}che f{\"u}r numerische Programme}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2242}, number = {SC-96-13}, year = {1996}, abstract = {Der Entwurf und die Implementierung des auf Tcl/Tk basierenden Werkzeugkastens ZGUI wird beschrieben und an einigen Beispielen erl{\"a}utert. ZGUI unterst{\"u}tzt die Entwicklung einer graphischen Benutzeroberfl{\"a}che (GUI) f{\"u}r die am ZIB erstellte numerische Software. Es sollen folgende Ziele erreicht werden: \begin{itemize} \item einfaches Ausprobieren anhand vordefinierter Testprobleme,\vspace*{-2mm} \item Kennenlernen numerischer Steuergr{\"o}\ss en und Verfahrensvarianten,\vspace*{-2mm} \item einfache Eingabe neuer Probleme,\vspace*{-2mm} \item einfache Nutzung graphischer Ausgabem{\"o}glichkeiten und\vspace*{-2mm} \item einheitliche Darstellung gleicher oder {\"a}hnlicher Optionen. \end{itemize}}, language = {de} } @misc{StephaniWolf1996, author = {Stephani, Hans and Wolf, Thomas}, title = {Spherically symmetric perfect fluids in shearfree motion - the symmetry approach}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2253}, number = {SC-96-14}, year = {1996}, abstract = {In General Relativity, the motion of expanding shearfree perfect fluids is governed by the ordinary differential equation \$y^{\prime \prime }=\$ \$\% F(x)\,y^2\$ , where \$F\$ is an arbitrary function from which the equation of state can be computed. A complete symmetry analysis of this differential equation is given; its solutions are classified according to this scheme, and in particular the relation to Wyman's Painlev\'e analysis is clarified.}, language = {en} } @misc{GoeckelerHorsleyLinkeetal.1996, author = {G{\"o}ckeler, Meinulf and Horsley, Roger and Linke, Volkard and Rakow, Paul and Schierholz, Gerrit and St{\"u}ben, Hinnerk}, title = {Seeking the Equation of State of Non-Compact Lattice QED}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2263}, number = {SC-96-15}, year = {1996}, abstract = {We perform a high statistics calculation of the equation of state for non-compact QED on large lattices. The calculation extends to fermionic correlation lengths of \$\approx 8\$, and it is combined with a finite size scaling analysis of the lattice data.}, language = {en} } @misc{FroehlichLangRoitzsch1996, author = {Fr{\"o}hlich, Jochen and Lang, Jens and Roitzsch, Rainer}, title = {Selfadaptive Finite Element Computations with Smooth Time Controller and Anisotropic Refinement}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2270}, number = {SC-96-16}, year = {1996}, abstract = {We present Multilevel Finite Element computations for twodimensional reaction-diffusion systems modelling laminar flames. These systems are prototypes for extreme stiffness in time and space. The first of these two rather general features is accounted for by an improved control mechanism for the time step. The second one is reflected through very thin travelling reaction fronts for which we propose an anisotropic discretization by local directional refinement.}, language = {en} } @misc{SchmidtYevick1996, author = {Schmidt, Frank and Yevick, David}, title = {Discrete Transparent Boundary Conditions for Schr{\"o}dinger-Type Equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2289}, number = {SC-96-17}, year = {1996}, abstract = {We present a general technique for constructing nonlocal transparent boundary conditions for one-dimensional Schr{\"o}dinger-type equations. Our method supplies boundary conditions for the \$\theta\$-family of implicit one-step discretizations of Schr{\"o}dinger's equation in time. The use of Mikusi\'nski's operator approach in time avoids direct and inverse transforms between time and frequency domains and thus implements the boundary conditions in a direct manner.}, language = {en} } @misc{NiemannSchmidtMaas1996, author = {Niemann, Holger and Schmidt, Dietmar and Maas, Ulrich}, title = {An Efficient Storage Scheme for Reduced Chemical Kinetics Based on Orthogonal Polynomials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2294}, number = {SC-96-18}, year = {1996}, abstract = {Simplified chemical kinetic schemes are a crucial prerequisite for the simulation of complex three-dimensional turbulent flows, and various methods for the generation of reduced mechanisms have been developed in the past. The method of intrinsic low-dimensional manifolds (ILDM), e.g., provides a mathematical tool for the automatic simplification of chemical kinetics, but one problem of this method is the fact that the information which comes out of the mechanism reduction procedure has to be stored for subsequent use in reacting flow calculations. In most cases tabulation procedures are used which store the relevant data (such as reduced reaction rates) in terms of the reaction progress variables, followed by table look-up during the reacting flow calculations. This can result in huge amounts of storage needed for the multi-dimensional tabulation. In order to overcome this problem we present a storage scheme which is based on orthogonal polynomials. Instead of using small tabulation cells and local mesh refinement, the thermochemical state space is divided into a small number of coarse cells. Within these coarse cells polynomial approximations are used instead of frequently used multi-linear interpolation. This leads to a considerable decrease of needed storage. The hydrogen-oxygen system is considered as an example. Even for this small chemical system we obtain a decrease of the needed storage requirement by a factor of 100.}, language = {en} } @misc{BornemannSchuette1996, author = {Bornemann, Folkmar A. and Sch{\"u}tte, Christof}, title = {A Mathematical Investigation of the Car-Parrinello Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2302}, number = {SC-96-19}, year = {1996}, abstract = {The Car-Parrinello method for ab-initio molecular dynamics avoids the explicit minimization of energy functionals given by functional density theory in the context of the quantum adiabatic approximation (time-dependent Born-Oppenheimer approximation). Instead, it introduces a fictitious classical dynamics for the electronic orbitals. For many realistic systems this concept allowed first-principle computer simulations for the first time. In this paper we study the {\em quantitative} influence of the involved parameter \$\mu\$, the fictitious electronic mass of the method. In particular, we prove by use of a carefully chosen two-time-scale asymptotics that the deviation of the Car-Parrinello method from the adiabatic model is of order \${\rm O}(\mu^{1/2})\$ --- provided one starts in the ground state of the electronic system and the electronic excitation spectrum satisfies a certain non-degeneracy condition. Analyzing a two-level model problem we prove that our result cannot be improved in general. Finally, we show how to use the gained quantitative insight for an automatic control of the unphysical ``fake'' kinetic energy of the method.}, language = {en} } @misc{SchuetteBornemann1996, author = {Sch{\"u}tte, Christof and Bornemann, Folkmar A.}, title = {Homogenization Approach to Smoothed Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2410}, number = {SC-96-31}, year = {1996}, abstract = {{\footnotesize In classical Molecular Dynamics a molecular system is modelled by classical Hamiltonian equations of motion. The potential part of the corresponding energy function of the system includes contributions of several types of atomic interaction. Among these, some interactions represent the bond structure of the molecule. Particularly these interactions lead to extremely stiff potentials which force the solution of the equations of motion to oscillate on a very small time scale. There is a strong need for eliminating the smallest time scales because they are a severe restriction for numerical long-term simulations of macromolecules. This leads to the idea of just freezing the high frequency degrees of freedom (bond stretching and bond angles) via increasing the stiffness of the strong part of the potential to infinity. However, the naive way of doing this via holonomic constraints mistakenly ignores the energy contribution of the fast oscillations. The paper presents a mathematically rigorous discussion of the limit situation of infinite stiffness. It is demonstrated that the average of the limit solution indeed obeys a constrained Hamiltonian system but with a {\em corrected soft potential}. An explicit formula for the additive potential correction is given via a careful inspection of the limit energy of the fast oscillations. Unfortunately, the theory is valid only as long as the system does not run into certain resonances of the fast motions. Behind those resonances, there is no unique limit solution but a kind of choatic scenario for which the notion ``Takens chaos'' was coined. For demonstrating the relevance of this observation for MD, the theory is applied to a realistic, but still simple system: a single butan molecule. The appearance of ``Takens chaos'' in smoothed MD is illustrated and the consequences are discussed.}}, language = {en} } @misc{Schultz1996, author = {Schultz, R{\"u}diger}, title = {A Note on Preprocessing via Fourier-Motzkin Elimination in Two-Stage Stochastic Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2423}, number = {SC-96-32}, year = {1996}, abstract = {Preprocessing in two-stage stochastic programming is considered from the viewpoint of Fourier-Motzkin elimination. Although of exponential complexity in general, Fourier-Motzkin elimination is shown to provide valuable insights into specific topics such as solving integer recourse stochastic programs or verifying stability conditions. Test runs with the computer code PORTA [1994] are reported.}, language = {en} } @misc{DeuflhardWeiser1996, author = {Deuflhard, Peter and Weiser, Martin}, title = {Global Inexact Multilevel FEM for Nonlinear Elliptic Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2430}, number = {SC-96-33}, year = {1996}, abstract = {The paper deals with the multilevel solution of {\em elliptic} partial differential equations (PDEs) in a {\em finite element} setting: {\em uniform ellipticity} of the PDE then goes with {\em strict monotonicity} of the derivative of a nonlinear convex functional. A {\em Newton multigrid method} is advocated, wherein {\em linear residuals} are evaluated within the multigrid method for the computation of the Newton corrections. The globalization is performed by some {\em damping} of the ordinary Newton corrections. The convergence results and the algorithm may be regarded as an extension of those for local Newton methods presented recently by the authors. An {\em affine conjugate} global convergence theory is given, which covers both the {\em exact} Newton method (neglecting the occurrence of approximation errors) and {\em inexact} Newton--Galerkin methods addressing the crucial issue of accuracy matching between discretization and iteration errors. The obtained theoretical results are directly applied for the construction of adaptive algorithms. Finally, illustrative numerical experiments with a~{\sf NEWTON--KASKADE} code are documented.}, language = {en} } @misc{PflugRuszczynskiSchultz1996, author = {Pflug, Georg Ch. and Ruszczynski, Andrzej and Schultz, R{\"u}diger}, title = {On the Glivenko-Cantelli Problem in Stochastic Programming: Linear Recourse and Extensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2448}, number = {SC-96-34}, year = {1996}, abstract = {Integrals of optimal values of random optimization problems depending on a finite dimensional parameter are approximated by using empirical distributions instead of the original measure. Under fairly broad conditions, it is proved that uniform convergence of empirical approximations of the right hand sides of the constraints implies uniform convergence of the optimal values in the linear and convex case.}, language = {en} } @misc{DellnitzJunge1996, author = {Dellnitz, Michael and Junge, Oliver}, title = {On the Approximation of Complicated Dynamical Behavior}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2456}, number = {SC-96-35}, year = {1996}, abstract = {We present efficient techniques for the numerical approximation of complicated dynamical behavior. In particular, we develop numerical methods which allow to approximate SBR-measures as well as (almost) cyclic behavior of a dynamical system. The methods are based on an appropriate discretization of the Frobenius-Perron operator, and two essentially different mathematical concepts are used: the idea is to combine classical convergence results for finite dimensional approximations of compact operators with results from Ergodic Theory concerning the approximation of SBR-measures by invariant measures of stochastically perturbed systems. The efficiency of the methods is illustrated by several numerical examples.}, language = {en} } @misc{DellnitzJunge1996, author = {Dellnitz, Michael and Junge, Oliver}, title = {An Adaptive Box Refinement in Subdivision Techniques for the Approximation of Dynamical Behavior}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2464}, number = {SC-96-36}, year = {1996}, abstract = {Recently subdivision techniques have been introduced in the numerical investigation of complicated temporal behavior of dynamical systems. In this article we intertwine the subdivision process with the computation of invariant measures and propose an adaptive scheme for the box refinement which is based on the combination of these methods. Using this new algorithm the numerical effort for the computation of box coverings is in general significantly reduced, and we illustrate this fact by several numerical examples.}, language = {en} } @misc{GatermannGuyard1996, author = {Gatermann, Karin and Guyard, Frederic}, title = {Gr{\"o}bner bases, invariant theory and equivariant dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2470}, number = {SC-96-37}, year = {1996}, abstract = {This paper is about algorithmic invariant theory as it is required within equivariant dynamical systems. The question of generic bifurcation equations requires the knowledge of fundamental invariants and equivariants. We discuss computations which are related to this for finite groups and semisimple Lie groups. We consider questions such as the completeness of invariants and equivariants. Efficient computations are gained by the Hilbert series driven Buchberger algorithm. Applications such as orbit space reduction are presented.}, language = {en} } @misc{Kornhuber1996, author = {Kornhuber, Ralf}, title = {On Robust Multigrid Methods for Piecewise Smooth Variational Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2487}, number = {SC-96-38}, year = {1996}, abstract = {We consider the fast solution of large, piecewise smooth minimization problems as resulting from the approximation of elliptic free boundary problems. The most delicate question in constructing a multigrid method for a nonlinear, non--smooth problem is how to represent the nonlinearity on the coarse grids. This process usually involves some kind of linearization. The basic idea of monotone multigrid methods to be presented here is first to select a neighborhood of the actual smoothed iterate in which a linearization is possible and then to constrain the coarse grid correction to this neighborhood. Such a local linearization allows to control the local corrections at each coarse grid node in such a way that the energy functional is monotonically decreasing. This approach leads to globally convergent schemes which are robust with respect to local singularities of the given problem. The numerical performance is illustrated by approximating the well-known Barenblatt solution of the porous medium equation.}, language = {en} } @misc{BornemannSchemann1996, author = {Bornemann, Folkmar A. and Schemann, Martin}, title = {Adaptive Rothe's Method for the 2D Wave Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2492}, number = {SC-96-39}, year = {1996}, abstract = {The adaptive Rothe method approaches a time-dependent PDE as an ODE in function space. This ODE is solved {\em virtually} using an adaptive state-of-the-art integrator. The {\em actual} realization of each time-step requires the numerical solution of an elliptic boundary value problem, thus {\em perturbing} the virtual function space method. The admissible size of that perturbation can be computed {\em a priori} and is prescribed as a tolerance to an adaptive multilevel finite element code, which provides each time-step with an individually adapted spatial mesh. In this way, the method avoids the well-known difficulties of the method of lines in higher space dimensions. During the last few years the adaptive Rothe method has been applied successfully to various problems with infinite speed of propagation of information. The present study concerns the adaptive Rothe method for hyperbolic equations in the model situation of the wave equation. All steps of the construction are given in detail and a numerical example (diffraction at a corner) is provided for the 2D wave equation. This example clearly indicates that the adaptive Rothe method is appropriate for problems which can generally benefit from mesh adaptation. This should be even more pronounced in the 3D case because of the strong Huygens' principle.}, language = {en} } @misc{Bornemann1990, author = {Bornemann, Folkmar A.}, title = {An Adaptive Multilevel Approach to Parabolic Equations II.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-410}, number = {SC-90-13}, year = {1990}, abstract = {In continuation of part I this paper develops a variable-order time discretization in Hilbert space based on a multiplicative error correction. Matching of time and space errors as explained in part I allows to construct an adaptive multilevel discretization of the parabolic problem. In contrast to the extrapolation method in time, which has been used in part I, the new time discretization allows to separate space and time errors and further to solve fewer elliptic subproblems with less effort, which is essential in view of the application to space dimension greater than one. Numerical examples for space dimension one are included which clearly indicate the improvement.}, language = {en} } @misc{AckermannWulkow1990, author = {Ackermann, J{\"o}rg and Wulkow, Michael}, title = {MACRON - A Program Package for Macromalecular Reaction Kinetics.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-423}, number = {SC-90-14}, year = {1990}, abstract = {This paper presents the new program package MACRON for the simulation of macromolecular kinetics including standard chemical reactions. Such problems lead to countable (possibly) infinite systems of ordinary differential equations (CODE's), which are numerically treated by the so-called discrete Galerkin method here. By a chemical compiler the required analytical preprocessing is performed, such that the complete reaction system, standard kinetics as well as macromolecular reactions, can be entered in the chemical formalism. Typical macromolecular reaction steps are chain addition, termination, chain transfer and degradation (cracking). In order to ensure efficiency and reliability, high sophisticated numerical routines are built within the package. MACRON can be used without a detailed knowledge of the used numerical methods. As an illustration the application of MACRON to some realistic problems is presented.}, language = {en} } @misc{WulkowAckermann1990, author = {Wulkow, Michael and Ackermann, J{\"o}rg}, title = {Numerical Treatment of Polyreactions - Recent Developments.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-439}, number = {SC-90-15}, year = {1990}, abstract = {The mathematical modeling of macromolecular reactions leads to countable (possibly infinite) systems of ordinary differential equations (CODE's). This paper reviews two recent developments of the so-called discrete Galerkin method, which has been developed for the numerical treatment of countable systems, which arise e.g. in polymer chemistry. The first approach can be considered as a method of lines with moving basis functions and has been implemented recently in the program package MACRON. The second type of the Galerkin method is characterized by a so-called outer time discretization of the complete problem and an appropriate and efficient solution of the arising subproblems. This method is realized in the research code CODEX.}, language = {en} } @misc{HegeStueben1990, author = {Hege, Hans-Christian and St{\"u}ben, Hinnerk}, title = {Vectorization and Parallelization of Irregular Problems via Graph coloring.}, doi = {/10.1145/109025.109042}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-443}, number = {SC-90-16}, year = {1990}, abstract = {Efficient implementations of irregular problems on vector and parallel architectures are generally hard to realize. An important class of problems are Gauß-Seidel iteration schemes applied to irregular data sets. The unstructured data dependences arising there prevent restructuring compilers from generating efficient code for vector or parallel machines. It is shown, how to structure the data dependences by decomposing the underlying data set using graph coloring techniques and by specifying a particular execution order already on the algorithm level. Methods to master the irregularities originating from different types of tasks are proposed. An application is given and some open issues and future developments are discussed.}, language = {en} } @misc{Wang1990, author = {Wang, Daoliu}, title = {Symplectic Difference Schemes for Perturbed Hamiltonian Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-456}, number = {SC-90-17}, year = {1990}, abstract = {In this paper we consider symplectic difference schemes for perturbed Hamiltonian systems of integrable ones, which can cover many important problems. Symplectic difference schemes for general Hamiltonian systems can also be used to these problems. But the perturbation property has not been paid proper attention to, which is important in the method proposed here. Numerical simulation shows that, for this method the time step size can be taken quite large and the qualitative property , such as preserving invariant tori, is also better than usual symplectic difference schemes.}, language = {en} } @misc{CaprasseDemaretGatermannetal.1990, author = {Caprasse, H. and Demaret, J. and Gatermann, Karin and Melenk, Herbert}, title = {Power-Law Type Solutions of Fourth-Order Gravity}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-466}, number = {SC-90-18}, year = {1990}, abstract = {We study the power-law type solutions of the fourth order field equations derived from a generic quadratic Lagrangian density in the case of multidimensional Bianchi I cosmological models. All the solutions of the system of algebraic equations have been found, using computer algebra, from a search of the Groebner bases associated to it. While, in space dimension \$ d = 3 \$ , the Einsteinian Kasner metric is still the most general power-law type solution, for \$ d > 3 \$ , no solution, other than the Minkowski space-time, is common to the three systems of equations associated with the three contributions to the Lagrangian density. In the case of a pure Riemann-squared contribution (suggested by a recent calculation of the effective action for the heterotic string), the possibility exists to realize a splitting of the \$ d \$-dimensional space into a ( \$ d - 3 \$)-dimensional internal space and a physical 3- dimensional space, the latter expanding in time as a power bigger than 2 (about 4.5 when \$ d = 9 \$).}, language = {en} } @misc{Walter1990, author = {Walter, Artur}, title = {Sparse Secant Methods for the Iterative Solution of Large Nonsymmetric Linear Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-483}, number = {SC-90-20}, year = {1990}, abstract = {A variety of secant methods has been revisited in view of the construction of iterative solvers for large nonsymmetric linear systems \$ Ax = b \$ stemming from the discretization of convection diffusion equations. In the first section, we tried to approximate \$ A ^{-1} \$ directly. Since the sparsity structure of A- is not known, additional storage vectors are needed during the iteration. In the next section, an incomplete factorization \$ LU \$ of \$ A \$ is the starting point and we tried to improve this easy invertible approximation of \$ A \$. The update is constructed in such a way that the sparsity structure of \$ L \$ and \$ U \$ is maintained. Two different sparsity preserving updates are investigated from theoretical and practical point of view. Numerical experiments on discretized PDEs of convection diffusion type in 2- D with internal layers and on "arbitrary" matrices with symmetric sparsity structure are given. {\bf Key words:} nonsymmetric linear system, sparse secant method, Broyden's method, incomplete factorization.}, language = {en} } @misc{OPUS4-49, title = {Jahresbericht 2007}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-498}, number = {2007}, year = {2008}, language = {de} } @misc{Nowak1995, author = {Nowak, Ulrich}, title = {A Fully Adaptive MOL-Treatment of Parabolic 1D-Problems with Extrapolation Techniques}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1913}, number = {SC-95-25}, year = {1995}, abstract = {A fully adaptive method is presented for the numerical solution of highly nonlinear, coupled systems of parabolic differential equations in one space dimension. Time discretization is by means of the linearly--implicit Euler discretization. Space discretization is by finite differences on non--uniform grids. Both basic discretizations are combined with extrapolation. Based on local error estimates for both the time and the space discretization error, the accuracy of the numerical approximation is controlled and the discretization stepsizes are adapted automatically and simultaneously. The algorithm is implemented in a user friendly software package, PDEX1M. To be a powerful tool for users coming from applications the package has been equipped with some additional useful devices.}, language = {en} } @misc{BornemannNettesheimSchuette1995, author = {Bornemann, Folkmar A. and Nettesheim, Peter and Sch{\"u}tte, Christof}, title = {Quantum-Classical Molecular Dynamics as an Approximation to Full Quantum Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1922}, number = {SC-95-26}, year = {1995}, abstract = {This paper presents a mathematical derivation of a model for quantum-classical molecular dynamics (QCMD) as a {\em partial} classical limit of the full Schr{\"o}dinger equation. This limit is achieved in two steps: separation of the full wavefunction and short wave asymptotics for its ``classical'' part. Both steps can be rigorously justified under certain smallness assumptions. Moreover, the results imply that neither the time-dependent self-consistent field method nor mixed quantum-semi-classical models lead to better approximations than QCMD since they depend on the separation step, too. On the other hand, the theory leads to a characterization of the critical situations in which the models are in danger of largely deviating from the solution of the full Schr{\"o}dinger equation. These critical situations are exemplified in an illustrative numerical simulation: the collinear collision of an Argon atom with a harmonic quantum oscillator.}, language = {en} } @misc{FroehlichSchneider1995, author = {Fr{\"o}hlich, Jochen and Schneider, Kai}, title = {An adaptive Wavelet-Vaguelette Algorithm for the Solution of Nonlinear PDEs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1941}, number = {SC-95-28}, year = {1995}, abstract = {The paper describes a fast algorithm for the discrete periodic wavelet transform and its inverse without using the scaling function. The approach permits to compute the decomposition of a function into a lacunary wavelet basis, i.e. a basis constituted of a subset of all basis functions up to a certain scale, without modification. The construction is then extended to operator--adapted biorthogonal wavelets. This is relevant for the solution of non--linear evolutionary PDEs where a priori information about the significant coefficients is available. We pursue the approach described in FrSc94 which is based on the explicit computation of the scalewise contributions of the approximated function to the values at points of hierarchical grids. Here, we present an improved construction employing the cardinal function of the multiresolution. The new method is applied to the Helmholtz equation and illustrated by comparative numerical results. It is then extended for the solution of a nonlinear parabolic PDE with semi--implicit discretization in time and self--adaptive wavelet discretization in space. Results with full adaptivity of the spatial wavelet discretization are presented for a one--dimensional flame front as well as for a two--dimensional problem.}, language = {en} } @misc{DeuflhardHeroth1995, author = {Deuflhard, Peter and Heroth, J{\"o}rg}, title = {Dynamic Dimension Reduction in ODE Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1951}, number = {SC-95-29}, year = {1995}, abstract = {The paper analyzes a splitting technique into fast and slow dynamical components of ODE systems as suggested by {\sc Maas and Pope} recently. Their technique is based on a real block -- Schur decomposition of the Jacobian of the right hand side of the ODE. As a result of the analysis, a computationally cheap monitor for the possible necessary recovering of the splitting is derived by singular perturbation theory. Numerical experiments on moderate size, but challenging reaction kinetics problems document the efficiency of the new device within a linearly-implicit stiff integrator.}, language = {en} } @misc{BornemannSchuette1995, author = {Bornemann, Folkmar A. and Sch{\"u}tte, Christof}, title = {A Mathematical Approach to Smoothed Molecular Dynamics: Correcting Potentials for Freezing Bond Angles}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1960}, number = {SC-95-30}, year = {1995}, abstract = {The interaction potential of molecular systems which are typically used in molecular dynamics can be split into two parts of essentially different stiffness. The strong part of the potential forces the solution of the equations of motion to oscillate on a very small time scale. There is a strong need for eliminating the smallest time scales because they are a severe restriction for numerical long-term simulations of macromolecules. This leads to the idea of just freezing the high frequency degrees of freedom (bond stretching and bond angles). However, the naive way of doing this via holonomic constraints is bound to produce incorrect results. The paper presents a mathematically rigorous discussion of the limit situation in which the stiffness of the strong part of the potential is increased to infinity. It is demonstrated that the average of the limit solution indeed obeys a constrained Hamiltonian system but with a {\em corrected soft potential}. An explicit formula for the additive potential correction is given and its significant contribution is demonstrated in an illustrative example. It appears that this correcting potential is definitely not identical with the Fixman-potential as was repeatedly assumed in the literature.}, language = {en} } @misc{GroetschelMartinWeismantel1995, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Consecutive Case}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1976}, number = {SC-95-31}, year = {1995}, abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.}, language = {en} } @misc{Reich1995, author = {Reich, Sebastian}, title = {Enhanced long-term simultation of Hamiltonian systems containing a strong non-convex potential}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1984}, number = {SC-95-32}, year = {1995}, abstract = {Many physical systems exhibit rapid motion coupled to a slowly varying motion. Often the rapid motion is associated with a stiff contribution in the potential energy function. In this context, the situation typically considered in the literature is the one with a strictly convex potential. Under some technical assumptions, one can then show that the slow motion is reproduced by a properly constrained system. In this paper we are concerned with a different situation: Often different time-scales can be found because of many local minima and barrier crossing between these minima. We suggest here to replace the detailed motion in the minima and the local barrier crossings by a statistical model which is then coupled to the slow equations of motion over long periods of time. This leads to Langevin type equations of motion subject to an appropriate time transformation.}, language = {en} } @misc{Brandt1995, author = {Brandt, Manfred}, title = {Approximations for the Distribution Function of the Sum of iid Random Variables with Compact Support in R+}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1990}, number = {SC-95-33}, year = {1995}, abstract = {In this paper a unified approach to central and decentral approximations of the distribution function \$F(x,n)\$ of the sum of \$n\$ iid random variables with compact support in \$I\!\!R_+\$ is given. This approach yields direct Edgeworth expansion (especially the Central limit theorem) and indirect Edgeworth expansion (Theorem of Bahadur-Rao, large deviation results) within a unified framework. An approximative inversion of the LST of \$F(x,n)\$ (approximation of the complex inversion integral over a line by an integral over a proper bounded arc with a proper integrand) allows to get these approximations and moreover explicit error bounds.}, language = {en} } @misc{BrandtBrandt1995, author = {Brandt, Andreas and Brandt, Manfred}, title = {On the Sojourn Times for Many-Queue Head-of-the-Line Processor-Sharing Systems with Permanent Customers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2005}, number = {SC-95-34}, year = {1995}, abstract = {We consider a single server system consisting of \$n\$ queues with different types of customers (Poisson streams) and \$k\$ permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). The stability condition and a pseudo work conservation law will be given for arbitrary service time distributions; for exponential service times a pseudo conservation law for the mean sojourn times can be derived. In case of two queues and exponential service times, the generating function of the stationary distribution satisfies a functional equation being a Riemann-Hilbert problem which can be reduced to a Dirichlet problem for a circle. The solution yields the mean sojourn times as an elliptic integral, which can be computed numerically very efficiently. In case \$n\ge 2\$ a numerical algorithm for computing the performance measures is presented, which is efficient for \$n=2,3\$. Since for \$n\ge 4\$ an exact analytical or/and numerical treatment is too complex a heuristic approximation for the mean sojourn times of the different types of customers is given, which in case of a (complete) symmetric system is exact. The numerical and simulation results show that, over a wide range of parameters, the approximation works well.}, language = {en} }