TY - GEN A1 - Koepf, Wolfram T1 - Gröbner Bases and Triangles N2 - It is well-known that by polynomial elimination methods, in particular by the computation of Gröbner bases, proofs for geometric theorems can be automatically generated. %% Several monographs On the other hand, it is much less known that Grö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. T3 - ZIB-Report - SC-96-24 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2350 ER - TY - GEN A1 - Bornemann, Folkmar A. A1 - Krause, Rolf T1 - Classical and Cascadic Multigrid - A Methodical Comparison N2 - 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. T3 - ZIB-Report - SC-96-25 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2368 ER - TY - GEN A1 - Löbel, Andreas T1 - Vehicle Scheduling in Public Transit and Lagrangean Pricing N2 - 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. T3 - ZIB-Report - SC-96-26 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2375 ER - TY - GEN A1 - Deuflhard, Peter A1 - Heroth, Jörg A1 - Maas, Ulrich T1 - Towards Dynamical Dimension Reduction in Reactive Flow Problems N2 - 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. T3 - ZIB-Report - SC-96-27 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2383 ER - TY - GEN A1 - Lang, Jens T1 - Adaptive FEM for Reaction-Diffusion Equations N2 - 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. T3 - ZIB-Report - SC-96-28 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2393 ER - TY - GEN A1 - Deuflhard, Peter A1 - Weiser, Martin T1 - Local Inexact Newton Multilevel FEM for Nonlinear Elliptic Problems N2 - 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. T3 - ZIB-Report - SC-96-29 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2401 ER - TY - GEN A1 - Bixby, Robert E. A1 - Martin, Alexander T1 - Parallelizing the Dual Simplex Method N2 - 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. T3 - ZIB-Report - SC-95-45 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2112 ER - TY - GEN A1 - Stalling, Detlev A1 - Steinke, Thomas T1 - Visualization of Vector Fields in Quantum Chemistry N2 - \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. T3 - ZIB-Report - SC-96-01 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2124 ER - TY - GEN A1 - Deuflhard, Peter A1 - Friese, Tilmann A1 - Schmidt, Frank A1 - März, Reinhard A1 - Nolting, Hans-Peter T1 - Effiziente Eigenmodenberechnung für den Entwurf integriert-optischer Chips N2 - {\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. T3 - ZIB-Report - SC-96-02 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2131 ER - TY - GEN A1 - Dentcheva, Darinka A1 - Möller, Andris A1 - Reeh, Peter A1 - Römisch, Werner A1 - Schultz, Rüdiger A1 - Schwarzbach, Gert A1 - Thomas, Jörg T1 - Optimale Blockauswahl bei der Kraftwerkseinsatzplanung N2 - 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. T3 - ZIB-Report - SC-96-03 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2144 ER - TY - GEN A1 - Reich, Sebastian T1 - Smoothed Langevin dynamics of highly oscillatory systems N2 - 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. T3 - ZIB-Report - SC-96-04 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2157 ER - TY - GEN A1 - Fröhlich, Jochen A1 - Lang, Jens T1 - Twodimensional Cascadic Finite Element Computations of Combustion Problems N2 - 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. T3 - ZIB-Report - SC-96-05 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2167 ER - TY - GEN A1 - Koepf, Wolfram A1 - Schmersau, Dieter T1 - Weinstein's Functions and the Askey-Gasper Identity N2 - \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ö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öwner chain of the Koebe function, and therefore with univalent functions. T3 - ZIB-Report - SC-96-06 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2175 ER - TY - GEN A1 - Löbel, Andreas T1 - Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method N2 - 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. T3 - ZIB-Report - SC-96-07 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2184 ER - TY - GEN A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr N2 - 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. T3 - ZIB-Report - SC-96-08 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2195 ER - TY - GEN A1 - Rojas, Raul T1 - Sixty Years of Computation - The Machines of Konrad Zuse N2 - 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. T3 - ZIB-Report - SC-96-09 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2203 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz T1 - Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cuttings Planes N2 - 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. T3 - ZIB-Report - SC-95-35 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2012 ER - TY - GEN A1 - Thomas, Rekha R. A1 - Weismantel, Robert T1 - Test sets and inequalities for integer programs: extended abstract N2 - 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. T3 - ZIB-Report - SC-95-36 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2021 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz A1 - Weismantel, Robert T1 - Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract N2 - 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. T3 - ZIB-Report - SC-95-37 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2031 ER - TY - GEN A1 - Löbel, Andreas A1 - Strubbe, Uwe T1 - Wagenumlaufoptimierung - Methodischer Ansatz und praktische Anwendung N2 - Im Rahmen des EDV-gestü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 über die betrieblichen Anforderungen und Nebenbedingungen an eine mathematische Optimierung und erläutern unsere Konzepte zur Realisierung eines exakten mathematischen Verfahrens. T3 - ZIB-Report - SC-95-38 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2047 ER -