TY - GEN A1 - Nowak, Ulrich T1 - A Fully Adaptive MOL-Treatment of Parabolic 1D-Problems with Extrapolation Techniques N2 - 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. T3 - ZIB-Report - SC-95-25 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1913 ER - TY - GEN A1 - Bornemann, Folkmar A. A1 - Nettesheim, Peter A1 - Schütte, Christof T1 - Quantum-Classical Molecular Dynamics as an Approximation to Full Quantum Dynamics N2 - 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ö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ödinger equation. These critical situations are exemplified in an illustrative numerical simulation: the collinear collision of an Argon atom with a harmonic quantum oscillator. T3 - ZIB-Report - SC-95-26 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1922 ER - TY - GEN A1 - Fröhlich, Jochen A1 - Schneider, Kai T1 - An adaptive Wavelet-Vaguelette Algorithm for the Solution of Nonlinear PDEs N2 - 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. T3 - ZIB-Report - SC-95-28 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1941 ER - TY - GEN A1 - Deuflhard, Peter A1 - Heroth, Jörg T1 - Dynamic Dimension Reduction in ODE Models N2 - 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. T3 - ZIB-Report - SC-95-29 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1951 ER - TY - GEN A1 - Bornemann, Folkmar A. A1 - Schütte, Christof T1 - A Mathematical Approach to Smoothed Molecular Dynamics: Correcting Potentials for Freezing Bond Angles N2 - 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. T3 - ZIB-Report - SC-95-30 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1960 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Consecutive Case N2 - 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. T3 - ZIB-Report - SC-95-31 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1976 ER - TY - GEN A1 - Reich, Sebastian T1 - Enhanced long-term simultation of Hamiltonian systems containing a strong non-convex potential N2 - 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. T3 - ZIB-Report - SC-95-32 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1984 ER - TY - GEN A1 - Brandt, Manfred T1 - Approximations for the Distribution Function of the Sum of iid Random Variables with Compact Support in R+ N2 - 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. T3 - ZIB-Report - SC-95-33 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1990 ER - TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - On the Sojourn Times for Many-Queue Head-of-the-Line Processor-Sharing Systems with Permanent Customers N2 - 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. T3 - ZIB-Report - SC-95-34 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2005 ER - TY - GEN A1 - Deuflhard, Peter A1 - Lang, Jens A1 - Nowak, Ulrich T1 - Adaptive Algorithms in Dynamical Process Simulation N2 - Dynamical simulation of industrially relevant processes strongly advises the use of algorithms, which are {\em adaptive} both in time and in space discretization. The paper presents two alternatives: (a) a fully adaptive method of lines approach, which is based on finite difference methods and essentially applicable to 1D problems; (b) a fully adaptive Rothe method, which is based on a fast multilevel finite element method and applicable to 1D up to 3D. T3 - ZIB-Report - SC-95-16 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1823 ER - TY - GEN A1 - Reich, Sebastian T1 - A Free Energy Approach to the Torsion Dynamics of Macromolecules N2 - Based on the concept of free energy, we give a Hamiltonian formulation for the torsion dynamics of macromolecules. The appropriate reaction coordinates for the free energy calculations are defined in terms of soft constraints as introduced in Brooks, B.R., Zhou, J., and Reich, S., Elastic molecular dynamics with flexible constraints, in preparation and Reich, S., Smoothed Dynamics of Highly Oscillatory Hamiltonian Systems, Physica D, to appear, 1995. We consider a few simplifications that allow one to calculate the free energy analytically and to write the corresponding equations of motion as a constrained Hamiltonian system. We also discuss a possible stochastic embedding of the reduced dynamics by means of a generalized Langevin approach. T3 - ZIB-Report - SC-95-17 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1839 ER - TY - GEN A1 - Zumbusch, Gerhard T1 - Symmetric Hierarchical Polynomials and the Adaptive h-p-Version N2 - The $h$-$p$-version of finite-elements delivers a sub-exponential convergence in the energy norm. A step towards a full adaptive implementation is taken in the context of unstructured meshes of simplices with variable order $p$ in space. Both assumptions lead to desirable properties of shape functions like symmetry, $p$-hierarchy and simple coupling of elements. In a first step it is demonstrated that for standard polynomial vector spaces on simplices not all of these features can be obtained simultaneously. However, this is possible if these spaces are slightly extended or reduced. Thus a new class of polynomial shape functions is derived, which are especially well suited for three dimensional tetrahedra. The construction is completed by directly minimizing the condition numbers of the arising preconditioned local finite element matrices. The preconditioner is based on two-step domain decomposition techniques using a multigrid solver for the global linear problem $p=1$ and direct solvers for local higher order problems. Some numerical results concerning an adaptive (feedback) version of $h$-$p$ finite elements are presented. T3 - ZIB-Report - SC-95-18 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1841 ER - TY - GEN A1 - Schütte, Christof A1 - Dinand, Manfred A1 - Zumbusch, Gerhard A1 - Brinkmann, Ralf T1 - Dynamics of Erbium-doped Waveguide Lasers: Modelling, Reliable Simulation, and Comparison with Experiments N2 - A theoretical investigation of the dynamic properties of integrated optical Er--doped waveguide lasers is presented. It includes the construction of a physical model and of numerical techniques which allow reliable simulations of the dynamical behaviour of the laser signal depending on essential parameters of the laser device and on its external, time--dependent pump radiation. Therefore, a physical theory is developed which describes the propagation of light and its interaction with the active substrate in the laser cavity. This is realized in two steps. First, a {\em fundamental model} based on Maxwell's equations and on rate equations for the transitions in the active medium is constructed. Since this turns out to prohibit reliable simulations, it is, in a second step, reformulated via averaging in time and space which suppresses the fluctuations on the fastest time scales but represents them correctly. For this {\em reduced model} reliable and efficient simulation techniques using adaptive control schemes are designed and implemented. We apply the linear--implicit Euler discretization with extrapolation in time and a multilevel quadrature scheme in space. Finally, the model is justified in comparison with experimental observations in four cases of technological relevance. T3 - ZIB-Report - SC-95-19 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1856 ER - TY - GEN A1 - Schultz, Rüdiger T1 - Discontinuous Optimization Problems in Stochastic Integer Programming N2 - Integer stochastic linear programming is considered from the viewpoint of discontinuous optimization. After reviewing solution approaches via mollifier subgradients and decomposition we outline how to base a solution method on efficient pointwise calculation of the objective employing computer algebra. T3 - ZIB-Report - SC-95-20 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1861 ER - TY - GEN A1 - Schultz, Rüdiger T1 - Strong Convexity in Stochastic Programs with Complete Recourse II: Partially Random Right-Hand Side N2 - We establish a verifiable sufficient condition for strong convexity of the expected recourse as a function of the tender variable in a two-stage stochastic program with linear recourse. Generalizing a former result where all components of the second-stage right-hand side vector were random we treat the case where only a subvector of the right-hand side is random. As prerequisite, a refined analysis of the polyhedral complex of lineality regions of the second-stage value function is carried out. The sufficient condition for strong convexity allows to widen the class of recourse models for which certain quantitative results on stability and asymptotic convergence of optimal solutions are valid. T3 - ZIB-Report - SC-95-21 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1874 ER - TY - GEN A1 - Wolf, Thomas T1 - The program CRACK for solving PDEs in General Relativity. Lecture given at the 152. WE-Heraeus-Seminar on RELATIVITY AND SCIENTIFIC CUMPUTING: Computer Algebra, Numerics, Visualization N2 - In the introduction an approach to solving differential equations is motivated in which non-linear DEs are not attacked directly but properties like infinitesimal symmetries or the existence of an equivalent variational principle are investigated. In the course of such investigations overdetermined PDE-systems are generated which are to be solved (where the term `overdetermined' just stands for `more conditions than free functions'). In section 2.\ algorithms for simplifying and solving overdetermined PDE systems are given together with examples. References for more details of the corresponding program {\tt CRACK}, written by A.\ Brand and the author, are given. In sections 3.-05.\ applications of the program {\tt CRACK} are discussed. The first application is the investigation of symmetries of space-time metrics by solving Killing equations for Killing vectors and Killing tensors and their integrability conditions. A program {\tt CLASSYM} that formulates these equations, written by G.\ Grebot, is briefly described. In section 4.\ an example of the original application of {\tt CRACK} is discussed which is the determination of symmetries of a PDE system. The problem is to find the symmetries of an unusual unified field theory of gravitational and hadronic interactions. The application of symmetries with a program {\tt APPLYSYM} is the content of section 5.\ where an ODE, resulting from an attempt to generalize Weyl's class of solutions of Einsteins field equations, is solved. The final section is devoted to future work on, first, making a general PDE-solver more flexible and effective, and secondly, on applying it to more advanced applications. This section contains so far unpublished work. An example requiring the extension of {\tt CRACK} to deal with non-polynomial non-linearities results from an investigation of interior solutions of Einstein's field equations for a spherically symmetric perfect fluid in shear-free motion by H.\ Stephani. A possible future application of {\tt CRACK} is the determination of Killing tensors of higher rank. In the last sub-section an algorithm for formulating corresponding integrability conditions has been sketched. The maximal number of Killing tensors of rank $r$ in a $n$-dimensional Riemannian space has been found to be $\frac{1}{r+1}\left( ^{n + r - 1}_{\;\;\;\;\,r} \right) \left( ^{ n+r}_{\;\;\,r} \right)$. T3 - ZIB-Report - SC-95-22 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1881 ER - TY - GEN A1 - Schultz, Rüdiger A1 - Stougie, Leen A1 - Vlerk, Maarten H. van der T1 - Solving Stochastic Programs with Complete Integer Recourse: a framework using Gröbner Bases N2 - In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the integer expected recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest possible improvements to economize on the number of function evaluations needed. T3 - ZIB-Report - SC-95-23 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1890 ER - TY - GEN A1 - Zumbusch, Gerhard T1 - Adaptive h-p approximation procedures, graded meshes and anisotropic refinement for Numerical Quadrature N2 - A set of adaptive algorithms for quadrature on multi-dimensional polyhedral domains is presented. Several kinds of refinement are discussed, covering local improvement of quadrature order and splitting the domain into sub-domains, resulting in isotropic, graded or anisotropic grids. The algorithms are pure local heuristics using no a priori knowledge or tuning parameters. This approach was motivated by results from finite element theory for optimal approximation results. Numerical experiments show the optimality of pure local greedy-like algorithms for singularity-type functions typically occurring in finite element computations. T3 - ZIB-Report - SC-95-24 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1905 ER - TY - GEN A1 - Koepf, Wolfram T1 - Algorithms for the Indefinite and Definite Summation N2 - The celebrated Zeilberger algorithm which finds holonomic recurrence equations for definite sums of hypergeometric terms $F(n,k)$ is extended to certain nonhypergeometric terms. An expression $F(n,k)$ is called hypergeometric term if both $F(n+1,k)/F(n,k)$ and $F(n,k+1)/F(n,k)$ are rational functions. Typical examples are ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are integer-linear with respect to $n$ and $k$ in their arguments. We consider the more general case of ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are rational-linear with respect to $n$ and $k$ in their arguments, and present an extended version of Zeilberger's algorithm for this case, using an extended version of Gosper's algorithm for indefinite summation. In a similar way the Wilf-Zeilberger method of rational function certification of integer-linear hypergeometric identities is extended to rational-linear hypergeometric identities. The given algorithms on definite summation apply to many cases in the literature to which neither the Zeilberger approach nor the Wilf-Zeilberger method is applicable. Examples of this type are given by theorems of Watson and Whipple, and a large list of identities (``Strange evaluations of hypergeometric series'') that were studied by Gessel and Stanton. It turns out that with our extended algorithms practically all hypergeometric identities in the literature can be verified. Finally we show how the algorithms can be used to generate new identities. REDUCE and MAPLE implementations of the given algorithms can be obtained from the author, many results of which are presented in the paper. T3 - ZIB-Report - SC-94-33 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1610 ER - TY - GEN A1 - Lang, Jens T1 - Two-Dimensional Fully Adaptive Solutions of Reaction-Diffusion Equations N2 - We present an adaptive Rothe method for two--dimensional problems combining an embedded Runge--Kutta scheme in time and a multilevel finite element discretization in space. The spatial discretization error is controlled by a posteriori error estimates based on interpolation techniques. A computational example for a thermodiffusive flame propagation model illustrates the high accuracy that is possible with the proposed method. T3 - ZIB-Report - SC-94-34 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1627 ER -