@misc{LeimkuhlerReich1992, author = {Leimkuhler, Benedict and Reich, Sebastian}, title = {The Numerical Solution of Constrained Hamiltonian Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-868}, number = {SC-92-16}, year = {1992}, abstract = {A Hamiltonian system subject to smooth constraints can typically be viewed as a Hamiltonian system on a manifold. Numerical computations, however, must be performed in \$ R^n\$. In this paper, canonical transformations from ``Hamiltonian differential--algebraic equations'' to ODEs in Euclidean space are considered. In \S2, canonical parameterizations or local charts are developed and it is shown how these can be computed in a practical framework. In \S3 we consider the construction of unconstrained Hamiltonian ODE systems in the space in which the constraint manifold is embedded which preserve the constraint manifold as an integral invariant and whose flow reduces to the flow of the constrained system along the manifold. It is shown that certain of these unconstrained Hamiltonian systems force Lyapunov stability of the constraint--invariants, while others lead to an unstable invariant. In \S4, we compare various projection techniques which might be incorporated to better insure preservation of the constraint--invariants in the context of numerical discretization. Numerical experiments illustrate the degree to which the constraint and symplectic invariants are maintained under discretization of various formulations. {\bf Keywords:} differential--algebraic equations, Hamiltonian systems, canonical discretization schemes. {\bf AMS(MOS):} subject classification 65L05.}, language = {en} } @misc{Moeller1992, author = {M{\"o}ller, H. Michael}, title = {On decomposing systems of polynomial equations with finitely many solutions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-851}, number = {SC-92-15}, year = {1992}, abstract = {This paper deals with systems of \$m\$ polynomial equations in \$n\$ unknown, which have only finitely many solutions. A method is presented which decomposes the solution set into finitely many subsets, each of them given by a system of type \begin{displaymath} f_1(x_1)=0, f_2(x_1,x_2)=0,...,f_n(x_1,...,x_n)=0. \end{displaymath} The main tools for the decomposition are from ideal theory and use symbolical manipulations. For the ideal generated by the polynomials which describe the solution set, a lexicographical Gr{\"o}bner basis is required. A particular element of this basis allows the decomposition of the solution set. A recursive application of these decomposition techniques gives finally the triangular subsystems. The algorithm gives even for non-finite solution sets often also usable decompositions. {\bf Keywords:} Algebraic variety decomposition, Gr{\"o}bner bases, systems of nonlinear equations.}, language = {en} } @misc{BornemannErdmannKornhuber1992, author = {Bornemann, Folkmar A. and Erdmann, Bodo and Kornhuber, Ralf}, title = {Adaptive Multilevel-Methods in 3-Space Dimensions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-843}, number = {SC-92-14}, year = {1992}, abstract = {We consider the approximate solution of selfadjoint elliptic problems in three space dimensions by piecewise linear finite elements with respect to a highly non-uniform tetrahedral mesh which is generated adaptively. The arising linear systems are solved iteratively by the conjugate gradient method provided with a multilevel preconditioner. Here, the accuracy of the iterative solution is coupled with the discretization error. as the performance of hierarchical bases preconditioners deteriorate in three space dimensions, the BPX preconditioner is used, taking special care of an efficient implementation. Reliable a-posteriori estimates for the discretization error are derived from a local comparison with the approximation resulting from piecewise quadratic elements. To illustrate the theoretical results, we consider a familiar model problem involving reentrant corners and a real-life problem arising from hyperthermia, a recent clinical method for cancer therapy.}, language = {en} } @misc{Gatermann1992, author = {Gatermann, Karin}, title = {Computation of Bifurcation Graphs.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-837}, number = {SC-92-13}, year = {1992}, abstract = {The numerical treatment of Equivariant parameter-dependent onlinear equation systems, and even more its automation requires the intensive use of group theory. This paper illustrates the group theoretic computations which are done in the preparation of the numerical computations. The bifurcation graph which gives the bifurcation subgroups is determined from the interrelationship of the irreducible representations of a group and its subgroups. The Jacobian is transformed to block diagonal structure using a modification of the transformation which transforms to block diagonal structure with respect to a supergroup. The principle of conjugacy is used everywhere to make symbolic and numerical computations even more efficient. Finally, when the symmetry reduced problems and blocks of Jacobian matrices are evaluated numerically, the fact that the given representation is a quasi-permutation representation is exploited automatically.}, language = {en} } @misc{LubichNowakPoehleetal.1992, author = {Lubich, Christian and Nowak, Ulrich and P{\"o}hle, Uwe and Engstler, Ch.}, title = {MEXX - Numerical Software for the Integration of Constrained Mechanical Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-823}, number = {SC-92-12}, year = {1992}, abstract = {MEXX (short for MEXanical systems eXtrapolation integrator) is a Fortran code for time integration of constrained mechanical systems. MEXX is suited for direct integration of the equations of motion in descriptor form. It is based on extrapolation of a time stepping method that is explicit in the differential equations and linearly implicit in the nonlinear constraints. It only requires the solution of well--structured systems of linear equations which can be solved with a computational work growing linearly with the number of bodies, in the case of multibody systems with few closed kinematic loops. Position and velocity constraints are enforced throughout the integration interval, whereas acceleration constraints need not be formulated. MEXX has options for time--continuous solution representation (useful for graphics) and for the location of events such as impacts. The present article describes MEXX and its underlying concepts.}, language = {en} } @misc{Bixby1992, author = {Bixby, Robert E.}, title = {Das Implementieren des Simplex- Verfahrens: Die Startbasis.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-816}, number = {SC-92-11}, year = {1992}, abstract = {Dieses Paper enth{\"a}lt die ersten beiden Teile einer geplanten Serie von Aufs{\"a}tzen {\"u}ber die \$CPLEX^2\$-Implementierung des Simplex- Verfahrens. Der erste Teil ist eine Einf{\"u}hrung: er liefert eine kurze Beschreibung des Verfahrens f{\"u}r Probleme mit beschr{\"a}nkten Variablen, zusammen mit einer relativ ausf{\"u}hrlichen Diskussion der numerischen Eigenschaften der Netlib-Probleme. Diese Probleme bilden auch das Fundament der rechnerischen Untersuchungen in den folgenden Teilen. Der zweite Teil enth{\"a}lt die Hauptergebnisse dieses Papers, eine Beschreibung der Methode, die von CPLEX verwendet wird, um eine Startbasis zu konstruieren.}, language = {de} } @misc{JuengerMartinReineltetal.1992, author = {J{\"u}nger, Michael and Martin, Alexander and Reinelt, Gerhard and Weismantel, Robert}, title = {Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-803}, number = {SC-92-10}, year = {1992}, abstract = {The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about \$NP\$-hardness and the existence of \$\varepsilon\$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-792}, number = {SC-92-09}, year = {1992}, abstract = {In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Polyhedral Investigations.}, doi = {10.1007/BF02592085}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-786}, number = {SC-92-08}, year = {1992}, abstract = {Let \$G=(V,E)\$ be a graph and \$T\subseteq V\$ be a node set. We call an edge set \$S\$ a Steiner tree with respect to \$T\$ if \$S\$ connects all pairs of nodes in \$T\$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph \$G=(V,E)\$ with edge weights \$w_e\$, edge capacities \$c_e, e \in E,\$ and node sets \$T_1,\ldots,T_N\$, find edge sets \$S_1,\ldots,S_N\$ such that each \$S_k\$ is a Steiner tree with respect to \$T_k\$, at most \$c_e\$ of these edge sets use edge \$e\$ for each \$e\in E\$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch \& cut algorithm. This algorithm is described in our companion paper SC 92-09.}, language = {en} } @misc{SchuetteWulkow1992, author = {Sch{\"u}tte, Christof and Wulkow, Michael}, title = {Quantum Theory with Discrete Spectra and Countable Systems of Differential Equations - A Numerical Treatment of RamanSpectroscopy.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-778}, number = {SC-92-07}, year = {1992}, abstract = {Models for occupation dynamics in discrete quantum systems lead to large or even infinite systems of ordinary differential equations. Some new mathematical techniques, developed for the simulation of chemical processes, make a numerical solution of countable systems of ordinary differential equations possible. Both, a basic physical concept for the construction of such systems and the structure of the numerical tools for solving them are presented. These conceptual aspects are illustrated by a simulation of an occupation process from spectroscopy. In this example the structures of rotation spectra observed in infrared spectroscopy are explained and some possibilities for an extension of the model are shown.}, language = {en} } @misc{KornhuberWittum1992, author = {Kornhuber, Ralf and Wittum, Gabriel}, title = {Discretization and Iterative Solution of Convection Diffusion Equations.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-762}, number = {SC-92-06}, year = {1992}, abstract = {We propose an extended box method which turns out to be a variant of standard finite element methods in the case of pure diffusion and an extension of backward differencing to irregular grids if only convective transport is present. Together with the adaptive orientation proposed in a recent paper and a streamline ordering of the unknowns, this discretization leads to a highly efficient adaptive method for the approximation of internal layers in the case of large local Peclet numbers.}, language = {en} } @misc{LangWalter1992, author = {Lang, Jens and Walter, Artur}, title = {A Finite Element Method Adaptive in Space and Time for Nonlinear Reaction-Diffusion- Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-755}, number = {SC-92-05}, year = {1992}, abstract = {Large scale combustion simulations show the need for adaptive methods. First, to save computation time and mainly to resolve local and instationary phenomena. In contrast to the widespread method of lines, we look at the reaction- diffusion equations as an abstract Cauchy problem in an appropriate Hilbert space. This means, we first discretize in time, assuming the space problems solved up to a prescribed tolerance. So, we are able to control the space and time error separately in an adaptive approach. The time discretization is done by several adaptive Runge-Kutta methods whereas for the space discretization a finite element method is used. The different behaviour of the proposed approaches are demonstrated on many fundamental examples from ecology, flame propagation, electrodynamics and combustion theory. {\bf Keywords:} initial boundary value problem, Rothe- method, adaptive Runge-Kutta method, finite elements, mesh refinement. {\bf AMS CLASSIFICATION:} 65J15, 65M30, 65M50.}, language = {en} } @misc{Wakabayashi1992, author = {Wakabayashi, Yoshiko}, title = {Medians of Binary Relations: Computational Complexity.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-746}, number = {SC-92-04}, year = {1992}, abstract = {Let \$\Re\$ be the set of all binary relations on a finite set \$N\$ and \$d\$ be the symmetric difference distance defined on \$\Re\$. For a given profile \$\Pi = (R_1,...,R_m) \in R^m\$, a relation \$R* \in \Re \$ that minimizes the function \$\sum^m_{k=1} d(R_k,R) \$ is called a median relation of \$\Pi\$. A number of problems occuring in the social sciences, in qualitative data analysis and in multicriteria decision making can be modelled as problems of finding medians of a profile of binary relations. In these contexts the profile \$\Pi\$ represents collected data (preferences, similarities, games) and the objective is that of finding a median relation of \$\Pi\$ with some special feature (representing e. g., consensus of preferences, clustering of similar objects, ranking of teams, etc.). In this paper we analyse the computational complexity of all such problems in which the median is required to satisfy one or more of the properties: reflexitivity, symmetry, antisymmetry, transitivity and completeness. We prove that whenever transitivity is required (except when symmetry and completeness are also simultaneously required) then the corresponding median problem is \$NP\$-hard. In some cases we prove that they remain \$NP\$-hard when the profile \$\Pi\$ has a fixed number of binary relations.}, language = {en} } @misc{Groetschel1992, author = {Gr{\"o}tschel, Martin}, title = {Discrete Mathematics in Manufacturing.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-738}, number = {SC-92-03}, year = {1992}, abstract = {Manufacturing is a topic that provides rich opportunities for important mathematical contributions to real-world problems. The purpose of this paper is to show, by means of several examples, where and how mathematical problems of a discrete nature arise in manufacturing and to demonstrate the savings and improvements that can be achieved by employing the techniques of combinatorial optimization. The topics covered range from the design phase of a product (e. g.,routing, placement and via minimization in VLSI design), the control of CNC machines (e. g., drilling and plotting), to the management of assembly lines, storage systems and whole factories. We also point out difficulties in the modelling of complex situations and outline the algorithmic methods that are used for the solution of the mathematical problems arising in manufacturing. {\bf Key words:} discrete mathematics , combinatorial optimization, applications to manufacturing.}, language = {en} } @misc{AckermannHELFRICH1992, author = {Ackermann, J{\"o}rg and HELFRICH, K.}, title = {Radius of Convergence of the 1/Z-Expansion for Diatomic Molecules: The Ground State of the Isoelectronic H2Sequence.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-721}, number = {SC-92-02}, year = {1992}, abstract = {Using the perturbational-variational Rayleigh-Ritz matrix formalism, the 1/Z-expansion for the ground state of the isoelectronic \$H_2\$ sequence in the range of the internuclear distance \$0.2\le R \le 9.0\$ is calculated. Also lower bounds of the radius of convergence, based on Kato's theory of linear operators, are given. The numerical results of the 1/Z-expansion can be compared with the exact results and do not converge in the whole R-range. This behavior is in qualitative agreement with the lower bounds for the radius of convergence and enlights some still open properties of 1/Z- expansions for this sequence in the literature. {\bf PACS:} 31.15 + q; 31.20 Di; 31.20 Tz.}, language = {en} } @misc{BornemannYserentant1992, author = {Bornemann, Folkmar A. and Yserentant, Harry}, title = {A Basic Norm Equivalence for the Theory of Multilevel Methods.}, doi = {10.1007/BF01388699}, number = {SC-92-01}, year = {1992}, abstract = {Subspace decompositions of finite element spaces based on \$L2\$-like orthogonal projections play an important role for the construction and analysis of multigrid like iterative methods. Recently several authors proved the equivalence of the associated discrete norms with the \$H^1\$-norm. The present report gives an elementary, self-contained derivation of this result which is based on the use of \$ K\$-functionals known from the theory of interpolation spaces. {\bf Keywords:} multilevel methods, nonuniform meshes, optimal convergence rates. {\bf AMS(MOS) Subject classifications:} 65N55, 65N30, 65N50.}, language = {en} } @misc{Hohmann1992, author = {Hohmann, Andreas}, title = {An Adaptive Continuation Method for Implicitly Defined Surfaces.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-705}, number = {SC-91-20}, year = {1992}, abstract = {A new method for the numerical aproximation of an implicitly defined surface is presented. It is a generalization of the Euler- Gauss-Newton method for implicitly defined (one- parameter) curves to the case of (two-parameter) surfaces. The basic task in the more general case is an efficient combination of modern CAGD techniques (such as triangular Bernstein-Bzier patches and the nine parameter Hermite interpolant) and the rank deficient Gauss-Newton method.}, language = {en} } @misc{GodsilGroetschelWelsh1992, author = {Godsil, C. D. and Gr{\"o}tschel, Martin and Welsh, D. J. A.}, title = {Combinatorics in Statistical Physics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-694}, number = {SC-91-19}, year = {1992}, language = {en} } @misc{AckermannWulkow1991, author = {Ackermann, J{\"o}rg and Wulkow, Michael}, title = {The Treatment of Macromolecular Processes with Chain-Length-Dependent Reaction Coefficients - An Examplefrom Soot Formation.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-682}, number = {SC-91-18}, year = {1991}, abstract = {The description of chain length distributions in macromolecular reaction kinetics leads to so-called countable systems of differential equations. In particular, when the appearing reaction rate coefficients depend on the chain length of the reacting macromolecules itself, an efficient numerical treatment of these systems is very difficult. Then even the evaluation of the right-hand side of the system can become prohibitively expensive with respect to computing time. In this paper we show how the discrete Galerkin method can be applied to such problems. The existing algorithm CODEX is improved by use of a multiplicative error correction scheme for time discretization and a new type of numerical preprocessing by means of a Gauss summation. Both ideas are exemplary for a wide class of approximation types and are described very briefly here. The new numerical techniques are tested on an example from soot formation, where the coagulation of molecules is modeled in terms of reaction coefficients depending on the surface of the particles and their collision frequency.}, language = {en} } @misc{Wulkow1991, author = {Wulkow, Michael}, title = {Adaptive Treatment of Polyreactions in Weighted Sequence Spaces.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-673}, number = {SC-91-17}, year = {1991}, abstract = {Countable systems of ordinary differential equations appear frequently in chemistry, physics, biology and statistics. They can be considered as ordinary differential equations in sequence spaces. In this work, a fully adaptive algorithm for the computational treatment of such systems is developed. The method is based on a time discretization of an abstract Cauchy problem in Hilbert space and a discrete Galerkin approach for the discretization of the arising stationary subproblems. The Galerkin method uses orthogonal functions of a discrete variable, which are generated by certain weight functions. A theory of countable systems in the associated weighted sequence spaces is developed as well as a theory of the Galerkin method. The Galerkin equations are solved adaptively either by use of analytical properties of the orthogonal functions or by an appropriate numerical summation. The resulting algorithm CODEX is applied to examples of technological interest, in particular from polymer chemistry.}, language = {en} } @misc{HoppeKornhuber1991, author = {Hoppe, Ronald H. W. and Kornhuber, Ralf}, title = {Adaptive Multilevel - Methods for Obstacle Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-667}, number = {SC-91-16}, year = {1991}, abstract = {We consider the discretization of obstacle problems for the Laplacian by piecewise linear finite elements. Assuming that the discrete problems are reduced to a sequence of linear problems by suitable active set strategies, the linear problems are solved iteratively by preconditioned c-g iterations. The proposed preconditioners are treated theoretically as abstract additive Schwarz methods and are implemented as truncated hierarchical basis preconditioners. To allow for local mesh refinement we derive semi-local and local a posteriori error estimates, providing lower and upper estimates for the discretization error. The theoretical results are illustrated by numerical computations.}, language = {en} }