Library

Description: In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The {\em quantum-classical Liouville equation} (QCL) describes most atoms of the molecular system under consideration by means of classical phase space density but an important, small portion of the system by means of quantum mechanics. The QCL is derived from the full quantum dynamical (QD) description by applying the Wigner transform to the classical part'' of the system only. We discuss the conditions under which the QCL model approximates the full QD evolution of the system. First, analysis of the asymptotic properties of the Wigner transform shows that solving the QCL yields a first order approximation of full quantum dynamics. Second, we discuss the adiabatic limit of the QCL. This discussion shows that the QCL solutions may be interpretated as classical phase space densities, at least near the adiabatic limit. Third, it is demonstrated that the QCL yields good approximations of {\em non-adiabatic quantum effects,} especially near so-called {\em avoided crossings} where most quantum-classical models fail.

Description: Mean-variance portfolio analysis provided the first quantitative treatment of the tradeoff between profit and risk. We investigate in detail the interplay between objective and constraints in a number of single-period variants, including semi-variance models. Particular emphasis is laid on avoiding the penalization of overperformance. The results are then used as building blocks in the development and theoretical analysis of multi-period models based on scenario trees. A key property is the possibility to remove surplus money in future decisions, yielding approximate downside risk minimization.

Description: The paper compares computational aspects of four approaches to compute conservation laws of single differential equations or systems of them, ODEs and PDEs. The only restriction, required by two of the four corresponding computer algebra programs, is that each DE has to be solvable for a leading derivative. Extra constraints may be given. Examples of new conservation laws include non-polynomial expressions, an explicit variable dependence and conservation laws involving arbitrary functions. Examples involve the following equations: Ito, Liouville, Burgers, Kadomtsev-Petviashvili, Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney.

Description: Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of $T$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted.

Description: In KOBV we offer the user an efficient tool for searching regional and worldwide accessible library catalogues (KOBV search engine). Search is performed by a distributed Z39.50 retrieval and an index based quicksearch. Due to the number of catalogues, result sets may contain a significant amount of duplicate records. Therefore we integrate a de-duplication procedure into KOBV search engine. It is part of the distributed search and the KOBV quicksearch as well. Main goals are the presentation of uniform retrieval results, the preservation of retrieval quality and cutting off redundant information. At least we keep an eye on efficiency. De-duplication is fully parametrizable, so that settings can be changed easily on line.

Description: A cascadic multigrid (CMG) method for elliptic problems with strong material jumps is proposed and analyzed. Non--matching grids at interfaces between subdomains are allowed and treated by mortar elements. The arising saddle point problems are solved by a subspace confined conjugate gradient method as smoother for the CMG. Details of algorithmic realization including adaptivity are elaborated. Numerical results illustrate the efficiency of this CMG algorithm.

Description: In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.

Description: We present an algebraic multigrid preconditioner which uses only the graphs of system matrices. Some elementary coarsening rules are stated, from which an advancing front algorithm for the selection of coarse grid nodes is derived. This technique can be applied to linear Lagrange-type finite element discretizations; for higher-order elements an extension of the multigrid algorithm is provided. Both two- and three-dimensional second order elliptic problems can be handled. Numerical experiments show that the resulting convergence acceleration is comparable to classical geometric multigrid.

Description: Flavone and the flavylium ion have been studied at Hartree-Fock, M{\o}ller-Plesset and B3LYP hybrid density functional level to determine the structures and barriers to internal rotation. Both molecules have a high perpendicular barrier about the single bond connecting the phenyl ring with the benzopyrone and benzopyrylium ring, respectively. In contrast to biphenyl both molecules have low coplanar barriers. B3LYP overestimates the perpendicular barrier heights compared to other methods. The dependence of the population and orbital energies on the torsion has been investigated and the structures of both flavonoids have been estimated by means of a reaction field model.

Description: The function of many important biomolecules is related to their dynamic properties and their ability to switch between different {\em conformations}, which are understood as {\em almost invariant} or {\em metastable} subsets of the positional state space of the system. Recently, the present authors and their coworkers presented a novel algorithmic scheme for the direct numerical determination of such metastable subsets and the transition probability between them. Although being different in most aspects, this method exploits the same basic idea as {\sc Dellnitz} and {\sc Junge} in their approach to almost invariance in discrete dynamical systems: the almost invariant sets are computed via certain eigenvectors of the Markov operators associated with the dynamical behavior. In the present article we analyze the application of this approach to (high--friction) Langevin models describing the dynamical behavior of molecular systems coupled to a heat bath. We will see that this can be related to theoretical results for (symmetric) semigroups of Markov operators going back to {\sc Davies}. We concentrate on a comparison of our approach in respect to random perturbations of dynamical systems.

Description: An introductory chapter on Groebner bases is given which also includes new results on the detection of Groebner bases for sparse polynomial systems. Algorithms for the computation of invariants and equivariants for finite groups, compact Lie groups and algebraic groups are presented and efficient implementation and time comparision are discussed. This chapter also inlcudes improvements of the computation of Noether normalisation and Stanley decomposition. These results are applied in symmetric bifurcation theory and equivariant dynamics. As preparation of the investigation of the orbit space reduction three methods are compared for solving symmetric polynomial systems exactly. The method of orbit space reduction is improved by using the Cohen-Macaulayness of the invariant ring and nested Noether normalization. Finally this is applied for a case of mode interaction in the Taylor-Couette problem.

Description: A class of sparse polynomial systems is investigated which is defined by a weighted directed graph and a weighted bipartite graph. They arise in the model of mass action kinetics for chemical reaction systems. In this application the number of real positive solutions within a certain affine subspace is of particular interest. We show that the simplest cases are equivalent to binomial systems while in general the solution structure is highly determined by the properties of the two graphs. First we recall results by Feinberg and give rigorous proofs. Secondly, we explain how the graphs determine the Newton polytopes of the system of sparse polynomials and thus determine the solution structure. The results on positive solutions from real algebraic geometry are applied to this particular situation. Examples illustrate the theoretical results.

Description: We study the improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering. As an indicator for decorrelation we use the topological charge.

Description: We describe a novel method for continuously transforming two triangulated models of arbitrary topology into each other. Equal global topology for both objects is assumed, extensions for genus changes during metamorphosis are provided. The proposed method addresses the major challenge in 3D metamorphosis, namely specifying the morphing process intuitively, with minimal user interaction and sufficient detail. Corresponding regions and point features are interactively identified. These regions are parametrized automatically and consistently, providing a basis for smooth interpolation. Utilizing suitable 3D interaction techniques a simple and intuitive control over the whole morphing process is offered.

Description: Our focus is on Maxwell's equations in the low frequency range; two specific applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the finite element approximation we choose N\'{e}d\'{e}lec's $H(curl)$-conforming edge elements of the lowest order. For the solution of the arising linear equation systems we devise an algebraic multigrid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally, we have to cope with the kernel of the $curl$-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efficacy of the proposed algorithms.

Description: Large scale simulations running in metacomputing environments face the problem of efficient file I/O. For efficiency it is desirable to write data locally, distributed across the computing environment, and then to minimize data transfer, i.e.\ reduce remote file access. Both aspects require I/O approaches which differ from existing paradigms. For the data output of distributed simulations, one wants to use fast local parallel I/O for all participating nodes, producing a single distributed logical file, while keeping changes to the simulation code as small as possible. For reading the data file as in postprocessing and file based visualization, one wants to have efficient partial access to remote and distributed files, using a global naming scheme and efficient data caching, and again keeping the changes to the postprocessing code small. However, all available software solutions require the entire data to be staged locally (involving possible data recombination and conversion), or suffer from the performance problems of remote or distributed file systems. In this paper we show how to interface the HDF5 I/O library via its flexible Virtual File Driver layer to the Globus Data Grid. We show, that combining these two toolkits in a suitable way provides us with a new I/O framework, which allows efficient, secure, distributed and parallel file I/O in a metacomputing environment.

Description: Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node $i$ to node $j$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for $m\ge 3$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for $m\ge 2$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for $m\ge 2$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.

Description: Due to its many applications in control theory, robust optimization, combinatorial optimization and eigenvalue optimization, semidefinite programming had been in wide spread use even before the development of efficient algorithms brought it into the realm of tractability. Today it is one of the basic modeling and optimization tools along with linear and quadratic programming. Our survey is an introduction to semidefinite programming, its duality and complexity theory, its applications and algorithms.

Description: Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d 〈 d' 〈 n$.

Description: In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.

Description: It is well known that the following class of systems of evolution equations \begin{eqnarray} \label{nsgen} \cases{ u_{t}=u_{xx}+F(u,v,u_x,v_x),\cr v_{t}=-v_{xx}+G(u,v,u_x,v_x),\cr} \end{eqnarray} is very rich in integrable cases. The complete classification problem is very difficult. Here we consider only the most interesting (from our opinion) subclass of systems (1). Namely, we consider equations linear in all derivatives of the form \begin{eqnarray} \label{kvazgen} \cases{ u_t = u_{xx} + A_{1}(u,v) u_x + A_{2}(u,v) v_x + A_{0}(u,v)\cr v_t = - v_{xx} + B_{1}(u,v) v_x + B_{2}(u,v) u_x + B_{0}(u,v). \cr} \end{eqnarray} without any restrictions on the functions $A_{i}(u,v), B_{i}(u,v)$.

Description: In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.

Description: In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5.

Description: A new seasonal energy storage for thermal solar systems has been developed on the basis of an adsorption-desorption process. Design and optimization of this storage will be supported by numerical simulations of heat and mass transfer with KARDOS. This paper focuses on the unsteady heat transfer during the major operating step of energetic discharge of the storage, which is characterized by conductive heat transfer in the fixed bed and a strong heat source caused by the adsorption enthalpy. Results are interpreted concerning the influence of variations in the parameter set. The method of implementation of the differential equation will be shown as well as the post-processing and gridwriting programs.

Description: In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.

Description: The function of many important biomolecules comes from their dynamic properties and their ability to switch between different {\em conformations}. In a conformation, the large scale geometric structure of the molecule is understood to be conserved, whereas on smaller scales the system may well rotate, oscillate or fluctuate. In a recent article [J. Comp. Phys., 151,1 (1999)], the present author and coworkers demonstrated that (a) conformations can be understood as almost invariant sets of some Markov chain being defined via the Hamiltonian system governing the molecular dynamics and that (b) these sets can efficiently be computed via eigenvectors of the corresponding Markov operator. The persent manuscript reviews the mathematical modelling steps behind the novel concept, includes a rigorous analytical justification of this approach and especially of the numerical details of the algorithm, and illustrates its performance when applied to realistic molecular systems.

Description: This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.

Description: This monograph has been written to illustrate the interlocking of theory, algorithm, and application in developing solution techniques for complex PDE systems. A deep theoretical understanding is necessary to produce a powerful idea leading to a successful algorithm. Efficient and robust implementation is the key to make the algorithm perform satisfactorily. The extra insight obtained by solving real--life problems brings out the structure of the method more clearly and suggests often ways to improve the numerical algorithm. It is my intention to impart the beauty and complexity found in both the theoretical investigation of the adaptive algorithm proposed here, i.e., the coupling of Rosenbrock methods in time and multilevel finite elements in space, and its realization. I hope that this method will find many more interesting applications.

Description: Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions.

Description: The method of symmetry adapted wavepackets (SAWP) to solve the time-dependent Schrödinger equation for a highly symmetric potential energy surface is introduced. The angular dependence of a quantum-mechanical wavepackets is expanded in spherical harmonics where the number of close-coupled equations for the corresponding radial functions can be efficiently reduced by symmetry adaption of the rotational basis using the SWAP approach. Various techniques to generate symmetry adapted spherical harmonics (SASHs) for the point groups of highest symmetry (octahedral, icosahedral) are discussed. The standard projection operator technique involves the use of Wigner rotation matrices. Two methods to circumvent numerical instabilities occuring for large azimuthal quantum numbers are suggested. The first is based on a numerical scheme which employs Gaussian integrations yielding exact and stable results. The second is a recursive algorithm to generate higher order SASHs accurately and efficiently from lower order ones. The paper gives a complete set of ``seed functions'' generated by projection techniques which can be used obtain SASHs for all irreducible representations of the octahedral and icosahedral point groups recursively.

Description: The article surveys the development of novel mathematical concepts and algorithmic approaches based thereon in view of their possible applicability to biomolecular design. Both a first deterministic approach, based on the Frobenius-Perron operator corresponding to the flow of the Hamiltonian dynamics, and later stochastic approaches, based on a spatial Markov operator or on Langevin dynamics, can be subsumed under the unified mathematical roof of the transfer operator approach to effective dynamics of molecular systems. The key idea of constructing specific transfer operators especially taylored for the purpose of conformational dynamics appears as the red line throughout the paper. Different steps of the algorithm are exemplified by a trinucleotide molecular system as a small representative of possible RNA drug molecules.

Description: In this paper we discuss several ways to visualize stationary and non-stationary quantum mechanical systems. We demonstrate an approach for the quantitative interpretation of probability density isovalues which yields a reasonable correlation between isosurfaces for different timesteps. As an intuitive quantity for visualizing the momentum of a quantum system we propose the probability flow density which can be treated by vector field visualization techniques. Finally, we discuss the visualization of non-stationary systems by a sequence of single timestep images.

Description: One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included.

Description: The photoassociation process shows strong dependence on the temporal duration of the electromagnetic field pulses and their frequencies. This dependence is investigated using quantum mechanical simulations that include all ranges of impact parameters and contributions from bound-to-bound transitions. The photoassociation yield of mercury atoms to produce excimer dimers is enhanced for short (ps) and for ultrashort (fs) pulse durations. Ultrashort laser pulses effectively overlap the entire range of free-to-bound transition, therefore achieving a maximum probability. Short pulses show a maximum in the photoassociation yield when their carrier frequency overlaps a particular free-to-bound spectroscopic resonance. Implications of these calculations on efforts to control bimolecular reactions are discussed.

Description: For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis.

Description: This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.

Description: The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied. As an indicator for decorrelation the topological charge is used.

Description: This series of lectures has been given to a class of mathematics postdocs at a European summer school on Computational Mathematics Driven by Industrial Applications in Martina Franca, Italy (organized by CIME). It deals with a variety of challenging real life problems selected from clinical cancer therapy, communication technology, polymer production, and pharmaceutical drug design. All of these problems from rather diverse application areas share two common features: (a) they have been modelled by various differential equations -- elliptic, parabolic, or Schrödinger--type partial differential equations, countable ordinary diffential equations, or Hamiltonian systems, (b) their numerical solution has turned out to be real challenge to computational mathematics.

Description: Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. Encouraging preliminary computational results are reported.

Description: The C++ standard template library has many useful containers for data. The standard library includes two adpators, queue, and stack. The authors have extended this model along the lines of relational database semantics. Sometimes the analogy is striking, and we will point it out occasionally. An adaptor allows the standard algorithms to be used on a subset or modification of the data without having to copy the data elements into a new container. The authors provide many useful adaptors which can be used together to produce interesting views of data in a container.

Description: This report describes the development of an experimental service for picture-based document retrieval for the Electronic Visualization Library (EVlib). The EVlib is a digital library for scientific visualization, established at the Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB). The picture-based retrieval service allows users to look for documents by describing the pictures they contain. This query method was developed based on the assumption that (1) pictures often represent relevant parts of the contents of a document, and (2) pictures are often remembered well. A picture-based approach provides a new quality of accessing and exploring scientific literature. Motivation, concepts and realization of our service are outlined. Results of a user test are presented, too. The results indicate that this service can be used for searching and browsing the document collection in principle. On the other hand, problems were detected which can give fruitful hints for future work concerning document and image retrieval.

Description: In this paper, we generalize the nonlocal discrete transparent boundary condition introduced by Schmidt and Deuflhard {[}Comp. Math. Appl. 29 (1995) 53-76{]} and Schmidt and Yevick {[}J. Comput. Phys. 134 (1997) 96-107{]} to propagation methods based on arbitrary Pad\'e approximations to the two-dimensional one-way Helmholtz equation. Our approach leads to a recursive formula for the coefficients appearing in the nonlocal condition which then yields an unconditionally stable propagation method.

Description: We present nonlocal discrete transparent boundary conditions for a fourth-order wide-angle approximation of the two-dimensional Helmholtz equation. The boundary conditions are exact in the sense that they supply the same discrete solution on a bounded interior domain as would be obtained by considering the problem on the entire unbounded domain with zero boundary conditions at infinity. The proposed algorithm results in an unconditionally stable propagation method. Numerical examples from optics illustrate the efficiency of our approach.

Description: The paper discusses the approximation of scattered data on the sphere which is one of the major tasks in geomathematics. Starting from the discretization of singular integrals on the sphere the authors devise a simple approximation method that employs locally supported spherical polynomials and does not require equidistributed grids. It is the basis for a hierarchical approximation algorithm using differently scaled basis functions, adaptivity and error control. The method is applied to two examples one of which is a digital terrain model of Australia.

Description: In this article we present new results for families of orthogonal polynomials and special functions, that are determined by algorithmical approaches. In the first section, we present new results, especially for discrete families of orthogonal polynomials, obtained by an application of the celebrated Zeilberger algorithm. Next, we present algorithms for holonomic families $f(n,x)$ of special functions which possess a derivative rule. We call those families {\sl admissible}. A family $f(n,x)$ is holonomic if it satisfies a holonomic recurrence equation with respect to $n$, and a holonomic differential equation with respect to $x$, i.\ e. linear homogeneous equations with polynomial coefficients. The rather rigid property of admissibility has many interesting consequences, that can be used to generate and verify identities for these functions by linear algebra techniques. On the other hand, many families of special functions, in particular families of orthogonal polynomials, are admissible. We moreover present a method that generates the derivative rule from the holonomic representation of a holonomic family. % whenever one exists. As examples, we find new identities for the Jacobi polynomials and for the Whittaker functions, and for families of discrete orthogonal polynomials by the given approach. Finally, we present representations for the parameter derivatives of the Gegenbauer and the generalized Laguerre polynomials.

Description: In this paper the programs {\tt APPLYSYM}, {\tt QUASILINPDE} and {\tt DETRAFO} are described which aim at the utilization of infinitesimal symmetries of differential equations. The purpose of {\tt QUASILINPDE} is the general solution of quasilinear PDEs. This procedure is used by {\tt APPLYSYM} for the application of point symmetries for either \begin{itemize} \item calculating similarity variables to perform a point transformation which lowers the order of an ODE or effectively reduces the number of explicitly occuring independent variables in a PDE(-system) or for \item generalizing given special solutions of ODEs/PDEs with new constant parameters. \end{itemize} The program {\tt DETRAFO} performs arbitrary point- and contact transformations of ODEs/PDEs and is applied if similarity and symmetry variables have been found. The program {\tt APPLYSYM} is used in connection with the program {\tt LIEPDE} for formulating and solving the conditions for point- and contact symmetries which is described in LIEPDE(1992). The actual problem solving is done in all these programs through a call to the package {\tt CRACK} for solving overdetermined PDE-systems.

Description: Spiral-like patterns are an often observed phenomenon in chemical experiments such as the Belousov-Zhabotinskii reaction. The talk is concerned with a new PDE model whose solutions have the form of rotating spirals. In contrast to previous approaches it is based on a {\em scalar\/} reaction diffusion equation defined on a disk. A particular choice of boundary conditions leads to a non-selfadjoint operator which permits non-trivial dynamics. We study this equation using a combination of equivariant bifurcation theory and numerical simulations. The latter involves the direct simulation of the time dependent system as well as the computation of rotating waves and their stability.

Description: In this paper we develop a method for the simulation of wave propagation on artificially bounded domains. The acoustic wave equation is solved at all points away from the boundaries by a pseudospectral Chebychev method. Absorption at the boundaries is obtained by applying one-way wave equations at the boundaries, without the use of damping layers. The theoretical reflection coefficient for the method is compared to theoretical estimates of reflection coefficients for a Fourier model of the problem. These estimates are confirmed by numerical results. Modification of the method by a transformation of the grid to allow for better resolution at the center of the grid reduces the maximum eigenvalues of the differential operator. Consequently, for stability the maximum timestep is $O(1/N)$ as compared to $O(1/N^2)$ for the standard Chebychev method. Therefore, the Chebychev method can be implemented with efficiency comparable to that of the Fourier method. Moreover, numerical results presented demonstrate the superior performance of the new method.

Description: {\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set ${\cal F}\subseteq\{0,1\}^n$ the following problems are strongly polynomial time equivalent: given a feasible point $x\in\cal F$ and a linear objective function $c\in\Z^n$, \begin{itemize} \item find a feasible point $x^*\in\cal F$ that maximizes $cx$ (Optimization), \item find a feasible point $\xnew\in\cal F$ with $c\xnew〉cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew〉cx$ such that $\xnew-x$ is ``irreducible''\\(Irreducible Augmentation). \end{itemize} This generalizes results and techniques that are well known for $0/1$--integer programming problems that arise from various classes of combinatorial optimization problems.}

Description: In the recent years symmetric chaos has been studied intensively. One knows which symmetries are admissible as the symmetry of an attractor and which transitions are possible. The numeric has been developed using equivariant functions for detection of symmetry and augmented systems for determination of transition points. In this paper we look at this from a sophisticated group theoretic point of view and from the view of scientific computing, i.e. efficient evaluation of detectives is an important point. The constructed detectives are based on Young's seminormal form for $S_n$. An application completes the paper.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: This paper makes use of statistical mechanics in order to construct effective potentials for Molecular Dynamics for systems with nonstationary thermal embedding. The usual approach requires the computation of a statistical ensemble of trajectories. In the context of the new model the evaluation of only one single trajectory is sufficient for the determination of all interesting quantities, which leads to an enormous reduction of computational effort. This single trajectory is the solution to a corrected Hamiltonian system with a new potential $\tilde{V}$. It turns out that $\tilde{V}$ can be defined as spatial average of the original potential $V$. Therefore, the Hamiltonian dynamics defined by $\tilde{V}$ is smoother than that effected by $V$, i.e. a numerical integration of its evolution in time allows larger stepsizes. Thus, the presented approach introduces a Molecular Dynamics with smoothed trajectories originating from spatial averaging. This is deeply connected to time--averaging in Molecular Dynamics. These two types of {\em smoothed Molecular Dynamics} share advantages (gain in efficiency, reduction of error amplification, increased stability) and problems (necessity of closing relations and adaptive control schemes) which will be explained in detail.

Description: 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.

Description: 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.

Description: 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.

Description: The first part of the report contains a lecture presented at ``Scientific Computing in der Theoretischen Physik'', a workshop organized by the DMV-Fachgruppe Scientific Computing in cooperation with the GAMM-Fachauschuß Scientific Computing at Freie Universit{ä}t Berlin in March 1994. To complete this lecture, a slightly modified version of TR 93-12 is appended.

Description: International Workshop with support of the Deutsche Forschungsgemeinschaft (DFG) and Max-Planck-Gesellschaft (MPG) Berlin (Dahlem), Germany, May 30 - June 2, 1995

Description: In this report, we present a collection of new REDUCE packages that recently have been developed. These are the packages {\tt FPS}, {\tt ZTRANS}, {\tt RESIDUE} and {\tt TRIGSIMP} on the following topics: \begin{itemize} \item[] FPS Calculation of differential equations and formal power series representations, in particular for orthogonal polynomials and special functions of the hypergeometric type. \item[] ZTRANS Calculation of the Z-Transformation and its inverse. % to be used for the solution of linear recurrence equations. \item[] RESIDUE Calculation of residues of meromorphic functions. \item[] TRIGSIMP Simplification of expressions involving trigonometric and hyperbolic functions. \end{itemize} % These packages can be obtained via anonymous {\tt ftp} from % {\tt } in the directories {\tt ..}, ) For each of these packages, a description in form of a \LaTeX\ file is distributed together with the package. These documentations are collected here. In a final chapter, we show how to solve some difficult problems with these packages, and how they usefully can be combined.

Description: KASKADE 3.0 was developed for the solution of partial differential equations in one, two, or three space dimensions. Its object-oriented implementation concept is based on the programming language C++$\,$.~Adaptive finite element techniques are employed to provide solution procedures of optimal computational complexity. This implies a posteriori error estimation, local mesh refinement and multilevel preconditioning. The program was designed both as a platform for further developments of adaptive multilevel codes and as a tool to tackle practical problems. Up to now we have implemented scalar problem types like stationary or transient heat conduction. The latter one is solved with the Rothe method, enabling adaptivity both in space and time. Some nonlinear phenomena like obstacle problems or two-phase Stefan problems are incorporated as well. Extensions to vector-valued functions and complex arithmetic are provided. %Such free boundary problems ... We have implemented several iterative solvers for both symmetric and unsymmetric systems together with multiplicative and additive multilevel preconditioners. Systems arising from the nonlinear problems can be solved with lately developed monotone multigrid methods. %An object-oriented concept was chosen for KASKADE~3.0, based on the programming %language C++$\,$. This should provide the desired extensibilty and clearly %reflect the structure of the code. %A direct sparse matrix solver (Harwell MA28) is included.

Description: KASKADE 3.x was developed for the solution of partial differential equations in one, two, or three space dimensions. Its object-oriented implementation concept is based on the programming language C++$\,$.~Adaptive finite element techniques are employed to provide solution procedures of optimal computational complexity. This implies a posteriori error estimation, local mesh refinement and multilevel preconditioning. The program was designed both as a platform for further developments of adaptive multilevel codes and as a tool to tackle practical problems. Up to now we have implemented scalar problem types like stationary or transient heat conduction. The latter one is solved with the Rothe method, enabling adaptivity both in space and time. Some nonlinear phenomena like obstacle problems or two-phase Stefan problems are incorporated as well. Extensions to vector-valued functions and complex arithmetic are provided. This report helps to work with KASKADE Especially we \begin{itemize} \setlength{\parskip}{0ex} \item [{\bf --}] study a set of examples, \item [{\bf --}] explain how to define a user's problem and \item [{\bf --}] introduce a graphical user interface. \end{itemize} We are extending this guide continuously. The latest version is available by network.

Description: Line Integral Convolution (LIC) is a powerful technique for generating striking images and animations from vector data. Introduced in 1993, the method has rapidly found many application areas, ranging from computer arts to scientific visualization. Based upon locally filtering an input texture along a curved stream line segment in a vector field, it is able to depict directional information at high spatial resolutions. We present a new method for computing LIC images, which minimizes the total number of stream lines to be computed and thereby reduces computational costs by an order of magnitude compared to the original algorithm. Our methods utilizes fast, error-controlled numerical integrators. Decoupling the characteristic lengths in vector field grid, input texture and output image, it allows to compute filtered images at arbitrary resolution. This feature is of great significance in computer animation as well as in scientific visualization, where it can be used to explore vector data by smoothly enlarging structure of details. We also present methods for improved texture animation, employing constant filter kernels only. To obtain an optimal motion effect, spatial decay of correlation between intensities of distant pixels in the output image has to be controlled. This is achieved by blending different phase shifted box filter animations and by adaptively rescaling the contrast of the output frames.

Description: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}.

Description: The aim of this paper is to demonstrate a specific application of Computer Algebra to bifurcation theory with symmetry. The classification of different bifurcation phenomena in case of several parameters is automated, based on a classification of Gröbner bases of possible tangent spaces. The computations are performed in new coordinates of fundamental invariants and fundamental equivariants, with the induced weighted ordering. In order to justify the approach the theory of intrinsic modules is applied. Results for the groups $D_3, Z_2,$ and $ Z_2\times Z_2$ demonstrate that the algorithm works independent of the group and that new results are obtained.

Description: 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.

Description: {\begin{footnotesize} This thesis is concerned with structural properties and the stability behaviour of two-stage stochastic programs. Chapter~1 gives an introduction into stochastic programming and a summary of the main results of the thesis. In Chapter~2 we present easily verifiable sufficient conditions for the strong convexity of the expected-recourse function in a stochastic program with linear complete recourse. Different levels of randomness in the data are considered. We start with models where only the right-hand side of the constraints is random and extend these results to the situation where also the technology matrix contains random entries. The statements on strong convexity imply new stability estimates for sets of optimal solutions when perturbing the underlying probability measure. We work out Hölder estimates (in terms of the $\mbox{L}_1$-Wasserstein distance) for optimal solution sets to linear recourse models with random technology matrix. In Chapter~3 ({\it joint work with Werner Römisch, Berlin}) we are aiming at the Lipschitz stability of optimal solution sets to linear recourse models with random right-hand side. To this end , we first adapt the distance notion for the underlying probability measures to the structure of the model and derive a Lipschitz estimate for optimal solutions based on that distance. Here, the strong convexity established in Chapter~2 turns out as an essential assumption. For applications, however, a Lipschitz estimate with respect to a more accesssible probability distance is desirable. Structural properties of the expected-recourse function finally permit such an estimate in terms of the Kolmogorov-Smirnov distance of linear transforms of the underlying measures. The general analysis is specified to estimation via empirical measures. We obtain a law of iterated logarithm, a large deviation estimate and an estimate for the asymptotic distribution of optimal solution sets. Chapters~4 and~5 deal with two-stage linear stochastic programs where integrality constraints occur in the second stage. In Chapter~4 we study basic continuity properties of the expected-recourse function for models with random right-hand side and random technology matrix. The joint continuity with respect to the decision variable and the underlying probability measure leads to qualitative statements on the stability of local optimal values and local optimal solutions. In Chapter~5 we demonstrate that a variational distance of probability measures based on a suitable Vapnik-\v{C}ervonenkis class of Borel sets leads to convergence rates of the Hölder type for the expected recourse as a function of the underlying probability measure. The rates carry over to the convergence of local optimal values. As an application we again consider estimation via empirical measures. Beside qualitative asymptotic results for optimal values and optimal solutions we obtain a law of iterated logarithm for optimal values. \end{footnotesize}}

Description: 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.

Description: 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.

Description: 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.

Description: 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)$.

Description: 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.

Description: The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the $8$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.

Description: 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.

Description: 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.

Description: 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.

Description: Each invariant set of a given dynamical system is part of the global attractor. Therefore the global attractor contains all the potentially interesting dynamics, and, in particular, it contains every (global) unstable manifold. For this reason it is of interest to have an algorithm which allows to approximate the global attractor numerically. In this article we develop such an algorithm using a subdivision technique. We prove convergence of this method in a very general setting, and, moreover, we describe the qualitative convergence behavior in the presence of a hyperbolic structure. The algorithm can successfully be applied to dynamical systems of moderate dimension, and we illustrate this fact by several numerical examples.

Description: In this article algorithmic methods are presented that have essentially been introduced into computer algebra within the last decade. The main ideas are due to Stanley[1980] and Zeilberger[1990]. Some of them had already been discovered in the last century (see e.\ g.\ Beke[1894]), but because of the complexity of the underlying algorithms have fallen into oblivion. The combination of these ideas leads to a solution of the identification problem for a large class of transcendental functions. We present implementations of these algorithms in computer algebra systems.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: "The system is broken'' is how Keith Dennis, professor at Cornell University and the new editor-in-chief of the Mathematical Reviews characterizes the traditional ways and means of publication in mathematics. What are the reasons? The main reasons are the extreme growth in the mathematical literature, the long delays between preparation and publication of an article, the high number of rejected papers due to page limitations (not lack of quality) as well as drastic price increases for journals and books with library budgets being reduced at the same time.

Description: The reference wave vector of the paraxial Helmholtz equation is determined using various strategies which result all in similar expressions. The effort for its evaluation is so small that the reference wave vector can be adapted for each propagation step of an arbitrary BPM-algorithm.

Description: This report collects a number of proposals to determine the lowest eigensolutions of the scalar Helmholtz equation. The basic routine of all discussed algorithms is the standard Rayleigh quotient minimization process. The minimization is performed in a direct multilevel manner, and a subspace iteration is used to determine simultaneously a couple of eigensolutions. As smoother the nonlinear Gauß-Seidel, the nonlinear conjugate gradient method and a preconditioned version of this method are compared with respect to their efficiency. The numerical examples are based on realistic 1D and 2D models of integrated optics components.