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: \def\Bbb{\mathbb} For Gorenstein quotient spaces $\Bbb{C}^d/G$, a direct generalization of the classical McKay correspondence in dimensions $d\geq 4$ would primarily demand the existence of projective, crepant desingularizations. Since this turned out to be not always possible, Reid asked about special classes of such quotient spaces which would satisfy the above property. We prove that the underlying spaces of all Gorenstein abelian quotient singularities, which are embeddable as complete intersections of hypersurfaces in an affine space, have torus-equivariant projective crepant resolutions in all dimensions. We use techniques from toric and discrete geometry.

Description: We investigate the potential and limits of interior point based cutting plane algorithms for semidefinite relaxations on basis of implementations for max-cut and quadratic 0-1 knapsack problems. Since the latter has not been described before we present the algorithm in detail and include numerical results.

Description: \def\KukaRob {{\sf KUKA IR\,761}} {\small Industrial robots have greatly enhanced the performance of automated manufacturing processes during the last decades. International competition, however, creates an increasing demand to further improve both the accuracy of off-line programming and the resulting cycle times on production lines. To meet these objectives, validated dynamic robot models are required. We describe in detail the development of a generic dynamic model, specialize it to an actual industrial robot \KukaRob, and discuss the problem of dynamic calibration. Efficient and robust trajectory optimization algorithms are then presented which, when integrated into a CAD system, are suitable for routine application in an industrial environment. Our computational results for the \KukaRob\ robot performing a real life transport maneuver show that considerable gains in productivity can be achieved by minimizing the cycle time.}

Description: Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.

Description: We present a new technique for generating surface meshes from a uniform set of discrete samples. Our method extends the well-known marching cubes algorithm used for computing polygonal isosurfaces. While in marching cubes each vertex of a cubic grid cell is binary classified as lying above or below an isosurface, in our approach an arbitrary number of vertex classes can be specified. Consequently the resulting surfaces consist of patches separating volumes of two different classes each. Similar to the marching cubes algorithm all grid cells are traversed and classified according to the number of different vertex classes involved and their arrangement. The solution for each configuration is computed based on a model that assigns probabilities to the vertices and interpolates them. We introduce an automatic method to find a triangulation which approximates the boundary surfaces - implicitly given by our model - in a topological correct way. Look-up tables guarantee a high performance of the algorithm. In medical applications our method can be used to extract surfaces from a 3D segmentation of tomographic images into multiple tissue types. The resulting surfaces are well suited for subsequent volumetric mesh generation, which is needed for simulation as well as visualization tasks. The proposed algorithm provides a robust and unique solution, avoiding ambiguities occuring in other methods. The method is of great significance in modeling and animation too, where it can be used for polygonalization of non-manifold implicit surfaces.

Description: {\small Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computes recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions. In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation. In this article we extend these results be presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible. The main technique is again to use explicit formulas for structural identities of the given polynomial systems.}

Description: \noindent In molecular dynamics applications there is a growing interest in so-called {\em mixed quantum-classical} models. These models describe most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of quantum mechanics. A particularly extensively used model, the QCMD model, consists of a {\em singularly perturbed}\/ Schrödinger equation nonlinearly coupled to a classical Newtonian equation of motion. This paper studies the singular limit of the QCMD model for finite dimensional Hilbert spaces. The main result states that this limit is given by the time-dependent Born-Oppenheimer model of quantum theory---provided the Hamiltonian under consideration has a smooth spectral decomposition. This result is strongly related to the {\em quantum adiabatic theorem}. The proof uses the method of {\em weak convergence} by directly discussing the density matrix instead of the wave functions. This technique avoids the discussion of highly oscillatory phases. On the other hand, the limit of the QCMD model is of a different nature if the spectral decomposition of the Hamiltonian happens not to be smooth. We will present a generic example for which the limit set is not a unique trajectory of a limit dynamical system but rather a {\em funnel} consisting of infinitely many trajectories.

Description: This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported.

Description: Increasing demands on industrial robot operation call for optimal motion planning based on dynamic models. The resulting mathematical problems can be handled efficiently by sparse direct boundary value problem methods. Within this framework we propose a new solution technique that is closely related to the conventional kinematic approach: it eliminates the need for numerical integration of differential equations. First optimization results on a real life transport maneuver demonstrate that the technique may save over 50\,\%\ computation time.

Description: A mixed hypergraph ${\cal H}=(X,{\cal A},{\cal E})$ consists of the vertex set $X$ and two families of subsets: the family of edges ${\cal E}$ and the family of co-edges ${\cal A}$. In a coloring every edge $E \in {\cal E}$ has at least two vertices of different colors, while every co-edge $A \in {\cal A}$ has at least two vertices of the same color. The smallest (largest) number of colors for which there exists a coloring of a mixed hypergraph $\cal H$ using all the colors is called the lower (upper) chromatic number and is denoted $\chi ({\cal H})$ $(\bar {\chi} ({\cal H}) )$. A mixed hypergraph is called uncolorable if it admits no coloring. \par We show that there exist uncolorable mixed hypergraphs ${\cal H}=$ $(X, {\cal A}, {\cal E})$ with arbitrary difference between the upper chromatic number $\bar{\chi } ({\cal H}_{\cal A}) $ of ${\cal H}_{\cal A}=(X,{\cal A})$ and the lower chromatic number ${\chi }({\cal H}_{\cal E})$ of ${\cal H}_{\cal E}=(X,{\cal E}).$ Moreover, for any $k=\bar \chi ({\cal H}_{\cal A})- \chi ({\cal H}_{\cal E})$, the minimum number $v(k)$ of vertices of an inclusionwise minimal uncolorable mixed hypergraph is exactly $k+4.$ \par We introduce the measure of uncolorability which is called the vertex uncolorability number and propose a greedy algorithm that finds an estimate on it, and is a mixed hypergraph coloring heuristic at the same time. \par We show that the colorability problem can be expressed as an integer linear programming problem. \par Concerning particular cases, we describe those complete $(l,m)$-uniform mixed hypergraphs which are uncolorable, and observe that for given $(l,m)$ almost all complete $(l,m)$-uniform mixed hypergraphs are uncolorable, whereas generally almost all complete mixed hypergraphs are colorable.

Description: We present a self--adaptive finite element method to solve combustion problems in 1D, 2D, and 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. A posteriori error estimates are obtained by constructing locally higher order solutions involving all variables of the problem. Adaptive strategies such as step size control, spatial refinement and coarsening allow us to get economically an accurate solution. Various examples are presented to demonstrate practical applications of the proposed method.

Description: Let $G$ be a finite subgroup of SL$\left( r,% {\mathbb{C}}\right) $. In dimensions $r=2$ and $r=3$, McKay correspondence provides a natural bijection between the set of irreducible representations of $G$ and a cohomology-ring basis of the overlying space of a projective, crepant desingularization of ${\mathbb{C}}^r/G$. For $r=2$ this desingularization is unique and is known to be determined by the Hilbert scheme of the $G$% -orbits. Similar statements (including a method of distinguishing just {\it{one}} among all possible smooth minimal models of ${\mathbb{C}}^3/G$), are very probably true for all $G$'s $\subset $ SL$\left( 3,{\mathbb{C}}\right) $ too, and recent Hilbert-scheme-techniques due to Ito, Nakamura and Reid, are expected to lead to a new fascinating uniform theory. For dimensions $r\geq 4 $, however, to apply analogous techniques one needs extra modifications. In addition, minimal models of ${\mathbb{C}}^r/G$ are smooth only under special circumstances. ${\mathbb{C}}^4/\left( \hbox{\rm involution}\right) $, for instance, cannot have any smooth minimal model. On the other hand, all abelian quotient spaces which are c.i.'s can always be fully resolved by torus-equivariant, crepant, projective morphisms. Hence, from the very beginning, the question whether a given Gorenstein quotient space ${\mathbb{C}}% ^r/G$, $r\geq 4$, admits special desingularizations of this kind, seems to be absolutely crucial.\noindent In the present paper, after a brief introduction to the existence-problem of such desingularizations (for abelian $G$'s) from the point of view of toric geometry, we prove that the Gorenstein cyclic quotient singularities of type \[ \frac 1l\,\left( 1,\ldots ,1,l-\left( r-1\right) \right) \] with $l\geq r\geq 2$, have a \textit{unique }torus-equivariant projective, crepant, partial resolution, which is full'' iff either $l\equiv 0$ mod $% \left( r-1\right) $ or $l\equiv 1$ mod $\left( r-1\right) $. As it turns out, if one of these two conditions is fulfilled, then the exceptional locus of the full desingularization consists of $\lfloor\frac{l}{r-1} \rfloor $ prime divisors, $\lfloor\frac{l}{r-1} \rfloor -1$ of which are isomorphic to the total spaces of ${\mathbb{P}}_{{\mathbb{C}}}^1$-bundles over ${\mathbb{P}}_{{\mathbb{C}}% }^{r-2}$. Moreover, it is shown that intersection numbers are computable explicitly and that the resolution morphism can be viewed as a composite of successive (normalized) blow-ups. Obviously, the monoparametrized singularity-series of the above type contains (as its first member'') the well-known Gorenstein singularity defined by the origin of the affine cone which lies over the $r$-tuple Veronese embedding of ${\mathbb{P}}_{\mathbb{C}}^{r-1}$.

Description: We describe an extension of the line integral convolution method (LIC) for imaging of vector fields on arbitrary surfaces in 3D space. Previous approaches were limited to curvilinear surfaces, i.e.~surfaces which can be parametrized globally using 2D-coordinates. By contrast our method also handles the case of general, possibly multiply connected surfaces. The method works by tesselating a given surface with triangles. For each triangle local euclidean coordinates are defined and a local LIC texture is computed. No scaling or distortion is involved when mapping the texture onto the surface. The characteristic length of the texture remains constant. In order to exploit the texture hardware of modern graphics computers we have developed a tiling strategy for arranging a large number of triangular texture pieces within a single rectangular texture image. In this way texture memory is utilized optimally and even large textured surfaces can be explored interactively.

Description: A new technique for interactive vector field visualization using large numbers of properly illuminated field lines is presented. Taking into account ambient, diffuse, and specular reflection terms as well as transparency and depth cueing, we employ a realistic shading model which significantly increases quality and realism of the resulting images. While many graphics workstations offer hardware support for illuminating surface primitives, usually no means for an accurate shading of line primitives are provided. However, we show that proper illumination of lines can be implemented by exploiting the texture mapping capabilities of modern graphics hardware. In this way high rendering performance with interactive frame rates can be achieved. We apply the technique to render large numbers of integral curves of a vector field. The impression of the resulting images can be further improved by a number of visual enhancements, like transparency and depth-cueing. We also describe methods for controlling the distribution of field lines in space. These methods enable us to use illuminated field lines for interactive exploration of vector fields.

Description: The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.

Description: In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the %LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.

Description: In this paper we present a self--adaptive finite element method to solve flame propagation problems in 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. The proposed method is applied to an unsteady thermo--diffusive combustion model to demonstrate its potential for the solution of complicated problems.

Description: The paper is concerned with the analysis of an $s$ server queueing system in which the calls become impatient and leave the system if their waiting time exceeds their own patience. The individual patience times are assumed to be i.i.d.\ and arbitrary distributed. The arrival and service rate may depend on the number of calls in the system and in service, respectively. For this system, denoted by $M(n)/M(m)/s+GI$, where $m=\min(n,s)$ is the number of busy servers in the system, we derive a system of integral equations for the vector of the residual patience times of the waiting calls and their original maximal patience times. By solving these equations explicitly we get the stability condition and, for the steady state of the system, the occupancy distribution and various waiting time distributions. As an application of the \mbox{$M(n)/M(m)/s+GI$} system we give a performance analysis of an Automatic Call Distributor system (ACD system) of finite capacity with outbound calls and impatient inbound calls, especially in case of patience times being the minimum of constant and exponentially distributed times.

Description: During the last years the interest in the numerical simulation of reacting flows has grown considerably and numerical methods are available, which allow to couple chemical kinetics with flow and molecular transport. The use of detailed physical and chemical models, involving several hundred species, is restricted to very simple flow configurations like one-dimensional systems or two-dimensional systems with very simple geometries, and models are required, which simplify chemistry without sacrificing accuracy. One method to simplify the chemical kinetics is based on Intrinsic Low-Dimensional Manifolds (ILDM). They present attractors for the chemical kinetics, i.e. fast chemical processes relax towards them, and slow chemical processes represent movements within the manifolds. Thus the identification of the ILDMs allows a decoupling of the fast time scales. The concept has been verified by many different reacting flow calculations. However, one remaining problem of the method is the efficient calculation of the low-dimensional manifolds. This problem is addressed in this paper. We present an efficient, robust method, which allows to calculate intrinsic low-dimensional manifolds of chemical reaction systems. It is based on a multi-dimensional continuation process. Examples are shown for a typical combustion system. The method is not restricted to this class, but can be applied to other chemical systems, too.

Description: Given a communication demand between each pair of nodes of a network we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. We treat, in addition, several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real world data.

Description: We present a mathematical formulation of a \emph{frequency assignment problem} encountered in cellular phone networks: frequencies have to be assigned to stationary transceivers (carriers) such that as little interference as possible is induced while obeying several technical and legal restrictions. The optimization problem is NP-hard, and no good approximation can be guaranteed---unless P = NP. We sketch some starting and improvement heuristics, and report on their successful application for solving the frequency assignment problem under consideration. Computational results on real-world instances with up to 2877 carriers and 50 frequencies are presented.

Description: This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.

Description: We survey the literature on those variants of the {\em chromatic number\/} problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the {\em list colorings\/} and the {\em precoloring extensions\/} are considered. \par In one of the most general formulations, a graph $G=(V,E)$, sets $L(v)$ of admissible colors, and natural numbers $c_v$ for the vertices $v\in V$ are given, and the question is whether there can be chosen a subset $C(v)\subseteq L(v)$ of cardinality $c_v$ for each vertex in such a way that the sets $C(v),C(v')$ are disjoint for each pair $v,v'$ of adjacent vertices. The particular case of constant $|L(v)|$ with $c_v=1$ for all $v\in V$ leads to the concept of {\em choice number}, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. \par To illustrate typical techniques, some of the proofs are sketched.

Description: A graph $G$ is called preperfect if each induced subgraph $G' \subseteq G$ of order at least 2 has two vertices $x,y$ such that either all maximum cliques of $G'$ containing $x$ contain $y$, or all maximum indepentent sets of $G'$ containing $y$ contain $x$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph $G$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if $G$ is bipartite, 3-edge-connected, regular of degree $d$ for some $d \ge 3$, and contains no 3-edge-connected $d'$-regular subgraph for any $3 \le d' \le d$. \end{itemize}

Description: A (vertex) $k$-ranking of a graph $G=(V,E)$ is a mapping $ p:V\to \{1,\dots,k\}$ such that each path with endvertices of the same color $i$ contains an internal vertex of color $\ge i+1$. In the on-line coloring algorithms, the vertices $v_1,\dots,v_n$ arrive one by one in an unrestricted order, and only the edges inside the set $\{v_1,\dots,v_i\}$ are known when the color of $v_i$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a $(3\log_2 n)$-ranking for the path with $n \geq 2$ vertices, independently of the order in which the vertices are received.

Description: In our previous work [Preprint SC 97-48] we have studied natural mechanical systems on Riemannian manifolds with a strong constraining potential. These systems establish fast nonlinear oscillations around some equilibrium manifold. Important in applications, the problem of elimination of the fast degrees of freedom, or {\em homogenization in time}, leads to determine the singular limit of infinite strength of the constraining potential. In the present paper we extend this study to systems which are subject to external forces that are non-potential, depending in a mixed way on positions {\em and}\/ velocities. We will argue that the method of weak convergence used in [1997] covers such forces if and only if they result from viscous friction and gyroscopic terms. All the results of [1997] directly extend if there is no friction transversal to the equilibrium manifold; elsewise we show that instructive modifications apply.

Description: In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time.

Description: Scientific visualization is a rapidly growing research field with a need for information dissemination. This report describes the Electronic Visualization Library (EVlib), a digital library for scientific visualization. Main design goals of EVlib were an attractive user interface providing various kind of access mechanisms as well as an open interface to other already established information systems. EVlib stores fulltext versions of documents where they are available. We also provide access to BibTeX entries for every stored document. All available BibTeX entries are combined in BibTeX bibliographies which are registered with the ``Collection of Computer Science Bibliographies'' at University of Karlsruhe. Additionally, we have defined a mapping from BibTeX attributes to the Dublin Core attribute set. This mapping is used to provide a gatherer interface for the Harvest information system. This way, existing Harvest installations can immediately use EVlib as an information resource.

Description: An algorithm is given for bringing the equations of monomial first integrals of arbitrary degree of the geodesic motion in a Riemannian space $V_n$ into the form $(F_A)_{;k} = \sum_B \Gamma_{kAB} F_B$. The $F_A$ are the components of a Killing tensor $K_{i_1\ldots i_r}$ of arbitrary rank $r$ and its symmetrized covariant derivatives. Explicit formulas are given for rank 1,2 and 3. %The maximal number of Killing tensors %(reducible + non-reducible) is found to be %$\frac{1}{r+1}\left( ^{n + r - 1}_{\;\;\;\;\,r} \right) % \left( ^{ n+r}_{\;\;\,r} \right)$. Killing tensor equations in structural form allow the formulation of algebraic integrability conditions and are supposed to be well suited for integration as it is demonstrated in the case of flat space. An alternative proof of the reducibility of these Killing tensors is given which shows the correspondence to structural equations for rank 2 Killing tensors as formulated by Hauser & Malhiot. They used tensors with different symmetry properties.

Description: In molecular dynamics applications there is a growing interest in including quantum effects for simulations of larger molecules. This paper is concerned with {\em mixed quantum-classical} models which are currently discussed: the so-called QCMD model with variants and the time-dependent Born-Oppenheimer approximation. All these models are known to approximate the full quantum dynamical evolution---under different assumptions, however. We review the meaning of these assumptions and the scope of the approximation. In particular, we characterize those typical problematic situations where a mixed model might largely deviate from the full quantum evolution. One such situation of specific interest, a non-adiabatic excitation at certain energy level crossings, can promisingly be dealt with by a modification of the QCMD model that we suggest.

Description: This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.

Description: In this paper, we present a Dantzig-Wolfe decomposition for the $NP$-hard multiple-depot vehicle scheduling problem in public mass transit. It turned out that such a decomposition approach is an unsuitable method to solve such kind of multicommodity flow problems. The major obstacle to solve such problems is that the continuous master problem relaxations become too hard to be solved efficiently. Especially for problems with more than one thousand timetabled trips, the LU factorization in solving a restricted master problem takes far too much time. We will describe our computational experiments in detail and discuss the reasons why the decomposition method fails in this case. Our computational investigations are based on real-world problems from the city of Hamburg with up to 2,283 timetabled trips. Our decomposition implementation is compared with a delayed column generation to solve the linear programming (LP) relaxation directly. This LP method can solve the LP relaxations of the integer linear programming formulation exactly for truly large-scale real-world problems of the cities of Berlin and Hamburg.

Description: In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.

Description: This paper presents an integer linear programming approach with delayed column generation for the {\em NP} Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail all basic ingredients of our approach that are indispensable to solve truly large-scale real-world instances to optimality, and we report on computational investigations that are based on real-world instances from the city of Berlin, the city of Hamburg, and the region around Hamburg. These real-world instances have up to 25 thousand timetabled trips and 70 million dead-head trips. Computational tests using the data of the Hamburger Hochbahn AG indicate savings of several vehicles and a cost reduction of about 10\% compared with the solution provided by HOT II, the vehicle scheduling tool of the HanseCom GmbH, Hamburg. Parts of our algorithms are already integrated in the BERTA system of the Berliner Verkehrsbetriebe (BVG) and will soon be integrated in the MICROBUS system of the Gesellschaft für Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin.

Description: Based on an approach of Affentranger&Schneider we give an asymptotic formula for the expected number of $k$-faces of the orthogonal projection of a regular $n$-crosspolytope onto a randomly chosen isotopic subspace of fixed dimension, as $n$ tends to infinity. In particular, we present a precise asymptotic formula for the (spherical) volume of spherical regular simplices, which generalizes Daniel's formula.

Description: Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice.

Description: {\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before.

Description: \noindent The speaker and his co-workers in Scientific Computing and Visualization have established a close cooperation with medical doctors at the Rudolf--Virchow--Klinikum of the Humboldt University in Berlin on the topic of regional hyperthermia. In order to permit a patient--specific treatment planning, a special software system ({\sf\small HyperPlan}) has been developed. \noindent A mathematical model of the clinical system ({\it radio frequency applicator with 8 antennas, water bolus, individual patient body}) involves Maxwell's equations in inhomogeneous media and a so--called bio--heat transfer PDE describing the temperature distribution in the human body. The electromagnetic field and the thermal phenomena need to be computed at a speed suitable for the clinical environment. An individual geometric patient model is generated as a quite complicated tetrahedral ``coarse'' grid (several thousands of nodes). Both Maxwell's equations and the bio--heat transfer equation are solved on that 3D--grid by means of {\em adaptive} multilevel finite element methods, which automatically refine the grid where necessary in view of the required accuracy. Finally optimal antenna parameters for the applicator are determined . \noindent All steps of the planning process are supported by powerful visualization methods. Medical images, contours, grids, simulated electromagnetic fields and temperature distributions can be displayed in combination. A number of new algorithms and techniques had to be developed and implemented. Special emphasis has been put on advanced 3D interaction methods and user interface issues.

Description: This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.

Description: A central drawback of interior point methods for semidefinite programs is their lack of ability to exploit problem structure in cost and coefficient matrices. This restricts applicability to problems of small dimension. Typically semidefinite relaxations arising in combinatorial applications have sparse and well structured cost and coefficient matrices of huge order. We present a method that allows to compute acceptable approximations to the optimal solution of large problems within reasonable time. Semidefinite programming problems with constant trace on the primal feasible set are equivalent to eigenvalue optimization problems. These are convex nonsmooth programming problems and can be solved by bundle methods. We propose to replace the traditional polyhedral cutting plane model constructed by means of subgradient information by a semidefinite model that is tailored for eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficacy of the approach on combinatorial examples.

Description: This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view.

Description: We study the Einstein field equations for spacetimes admitting a maximal two-dimensional abelian group of isometries acting orthogonally transitively on spacelike surfaces and, in addition, with at least one conformal Killing vector. The three-dimensional conformal group is restricted to the case when the two-dimensional abelian isometry subalgebra is an ideal and it is also assumed to act on non-null hypersurfaces (both, spacelike and timelike cases are studied). We consider both, diagonal and non-diagonal metrics and find all the perfect-fluid solutions under these assumptions (except those already known). We find four families of solutions, each one containing arbitrary parameters for which no differential equations remain to be integrated. We write the line-elements in a simplified form and perform a detailed study for each of these solutions, giving the kinematical quantities of the fluid velocity vector, the energy-density and pressure, values of the parameters for which the energy conditions are fulfilled everywhere, the Petrov type, the singularities in the spacetimes and the Friedmann-Lema\^{\i}tre-Robertson-Walker metrics contained in each family.

Description: Konrad Zuse ist unserem Land bekannt als der Computerpionier, der den ersten funktionstüchtigen Rechner in der Geschichte der Menschheit realisierte. Weniger bekannt ist aber immer noch die Tatsache, daß er mit seinem Plankalkül auch die erste höhere Programmiersprache der Welt entwickelte. Zuse hatte bereits 1945 nicht nur klare Vorstellungen über die Konzepte von höheren Programmiersprachen, sondern auch über die Programmierung von Anwendungen der künstlichen Intelligenz wie der relationalen Datenspeicherung oder dem Schachspiel. Dies macht ihn auch zum ersten Informatiker der Welt und darüber hinaus zum Erfinder der künstlichen Intelligenz.

Description: The focus of this paper is on the efficient solution of boundary value problems involving the double-- curl operator. Those arise in the computation of electromagnetic fields in various settings, for instance when solving the electric or magnetic wave equation with implicit timestepping, when tackling time--harmonic problems or in the context of eddy--current computations. Their discretization is based on on N\'ed\'elec's {\bf H(curl}; $\Omega$)--conforming edge elements on unstructured grids. In order to capture local effects and to guarantee a prescribed accuracy of the approximate solution adaptive refinement of the grid controlled by a posteriori error estimators is employed. The hierarchy of meshes created through adaptive refinement forms the foundation for the fast iterative solution of the resulting linear systems by a multigrid method. The guiding principle underlying the design of both the error estimators and the multigrid method is the separate treatment of the kernel of the curl--operator and its orthogonal complement. Only on the latter we have proper ellipticity of the problem. Yet, exploiting the existence of computationally available discrete potentials for edge element spaces, we can switch to an elliptic problem in potential space to deal with nullspace of curl. Thus both cases become amenable to strategies of error estimation and multigrid solution developed for second order elliptic problems. The efficacy of the approach is confirmed by numerical experiments which cover several model problems and an application to waveguide simulation.

Description: A hybrid Monte Carlo method with adaptive temperature choice is presented, which exactly generates the distribution of a mixed-canonical ensemble composed of two canonical ensembles at low and high temperature. The analysis of resulting Markov chains with the reweighting technique shows an efficient sampling of the canonical distribution at low temperature, whereas the high temperature component facilitates conformational transitions, which allows shorter simulation times. \\The algorithm was tested by comparing analytical and numerical results for the small n-butane molecule before simulations were performed for a triribonucleotide. Sampling the complex multi-minima energy landscape of these small RNA segments, we observed enforced crossing of energy barriers.

Description: We study the parallelization of linearly--implicit extrapolation methods for the solution of large scale systems of differential algebraic equations arising in a method of lines (MOL ) treatment of partial differential equations. In our approach we combine a slightly overlapping domain decomposi tion together with a polynomial block Neumann preconditioner. Through the explicit computation of the matrix products of the pre conditioner and the system matrix a significant gain in overall efficiency is achieved for medium--sized problems. The parallel algorithm exhibits a good scalability up to 32 proces sors on a Cray T3E. Preliminary results for computations on a workstation cluster are reported.

Description: The (implicit) midpoint scheme, like higher order Gauss-collocation schemes, is algebraically stable and symplectic, and it preserves quadratic integral invariants. It may appear particularly suitable for the numerical solution of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or structural mechanics, because there is no stability restriction when it is applied to a simple harmonic oscillator. Although it is well-known that the midpoint scheme may also exhibit instabilities in various stiff situations, one might still hope for good results when resonance-type instabilities are avoided. In this paper we investigate the suitability of the midpoint scheme for highly oscillatory, frictionless mechanical systems, where the step-size $k$ is much larger than the system's small parameter $\varepsilon$, in case that the solution remains bounded as $\varepsilon \rightarrow 0$. We show that in general one must require that $k^2/\varepsilon$ be small enough, or else, even the errors in slowly varying quantities like the energy may grow undesirably (especially when fast and slow modes are tightly coupled) or, worse, the computation may yield misleading information. In some cases this may already happen when $k = O(\varepsilon )$. The same holds for higher order collocation at Gaussian points. The encountered restrictions on $k$ are still better than the corresponding ones for explicit schemes.

Description: It was revealed that the QCMD model is of canonical Hamiltonian form with symplectic structure, which implies the conservation of energy. An efficient and reliable integrator for transfering these properties to the discrete solution is the symplectic and explicit {\sc Pickaback} algorithm. The only drawback of this kind of integrator is the small stepsize in time induced by the splitting techniques used to discretize the quantum evolution operator. Recent investigations concerning Krylov iteration techniques result in alternative approaches which overcome this difficulty for a wide range of problems. By using iterative methods in the evaluation of the quantum time propagator, these techniques allow for the stepsize to adapt to the coupling between the classical and the quantum mechanical subsystem. This yields a drastic reduction of the numerical effort. The pros and cons of both approaches as well as the suitable applications are discussed in the last part.

Description: We study the parallelization of linearly--implicit extrapolation codes for the solution of large scale PDE systems and differential algebraic equations on distributed memory machines. The main advantage of these algorithms is that they enable adapativity both in time and space. Additive Krylov--Schwarz methods yield high parallel perfomance for such extrapolation methods. Our approach combines a slightly overlapping domain decomposition together with a polynomial block Neumann preconditioner and a reduced system technique. Furthermore we get important advantages through the explicit computation of the matrix--products of the preconditioner and the matrix of the linear system. The parallel algorithms exhibit scalability up to 64 processors already for medium--sized test problems. We show that the codes are really efficient in large application systems for chemical engineering problems.

Description: We present a self-adaptive finite element method to solve nonlinear evolution problems in 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. The proposed method is applied to hyperthermia treatments to demonstrate its potential for the solving of complicated problems.

Description: An edge $e$ of a perfect graph $G$ is called critical if $G-e$ is imperfect. For certain graphs $G-e$ of this type, we determine all minimally imperfect subgraphs. We use this knowledge to describe inequalities inducing facets of the stable set polytope associated with $G-e$.\\

Description: We consider the fast solution of large, piecewise smooth minimization problems as typically arising from the finite element discretization of porous media flow. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with {\em constrained} Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give logarithmic upper bounds for the asymptotic convergence rates.

Description: In this article we consider a general model for phosphorus diffusion in silicon under extrinsic doping conditions. At such high concentrations we have to include the charged species and the internal electric field of the crystal, both of which can have profound effects on diffusion. In principle, this leads to a very large number of drift--diffusion--reaction equations: one for each charge state of every species, plus one Poisson equation to describe the internal electric field (in terms of the electron/hole concentration). The number of equations can be reduced substantially by making additional assumptions on the distribution of charge states and local equilibrium assumptions concerning the reaction terms. The resulting model turns out to be very interesting for numerical investigation. We solve the problem numerically in two space dimensions with the adaptive finite element program KARDOS and describe the numerical method used here to treat the resulting drift--diffusion--reaction problem.

Description: We present a particular method for the explicit elimination of rapidly oscillating micro-scales in certain singularly perturbed conservative mechanical systems. Non-linear effects call for a non-trivial averaging procedure that we call {\em homogenization in time.} This method is based on energy principles and weak convergence techniques. Since non-linear functionals are in general {\em not} weakly sequentially continuous, we have to study {\em simultaneously} the weak limits of all those non-linear quantities of the rapidly oscillating components which are of importance for the underlying problem. Using the physically motivated concepts of {\em virial theorems}, {\em adiabatic invariants}, and {\em resonances}, we will be able to establish sufficiently many relations between all these weak limits, allowing to calculate them explicitly. Our approach will be {\em paradigmatical} rather than aiming at the largest possible generality. This way, we can show most clearly how concepts and notions from the physical background of the underlying mathematical problem enter and help to determine relations between weak limit quantities. In detail we will discuss natural mechanical systems with a strong constraining potential on Riemannian manifolds, the questions of realization of holonomic constraints, and singular limits of mixed quantum-classical coupling models. This latter class of problems also leads to a new proof for the adiabatic theorem of quantum mechanics. The strength of our methodology will be illustrated by applications to problems from plasma physics, molecular dynamics and quantum chemistry.

Description: In molecular dynamics the highly oscillatory vibrations in the chemical bonds are often replaced by holonomic constraints that freeze the bond length/angle to its equilibrium value. In some cases this approach can be justified if the force constants of the bond vibrations are sufficiently large. However, for moderate values of the force constant, the constrained system might lead to a dynamical behavior that is too ``rigid'' compared to the flexible model. To compensate for this effect, the concept of soft constraints was introduced [Reich 1997, Reich 1995, Reich 1996]. However, its implementation is rather expensive. In this paper, we suggest an alternative approach that modifies the force field instead of the constraint functions. This leads to a more efficient method that avoids the resonance induced instabilities of multiple-time-stepping [Bishop 1996] and the above described effect of standard constrained dynamics.

Description: The numerical integration of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or Hamiltonian partial differential equations, is a challenging task. Various methods have been suggested to overcome the step-size restrictions of explicit methods such as the Verlet method. Among these are multiple-time-stepping, constrained dynamics, and implicit methods. In this paper, we investigate the suitability of time-reversible, semi-implicit methods. Here semi-implicit means that only the highly oscillatory part is integrated by an implicit method such as the midpoint method or an energy-conserving variant of it. The hope is that such methods will allow one to use a step-size $k$ which is much larger than the period $\varepsilon$ of the fast oscillations. However, our results are discouraging. Even in the absence of resonance-type instabilities, we show that in general one must require that $k^2/\varepsilon$ be small enough. Otherwise the method might become unstable and/or it might lead to a wrong approximation of the slowly varying solution components. The latter situation might, in some cases, even require that $k/\varepsilon$ be small in order to avoid this danger. While certain (semi-implicit) energy conserving methods prove to be robust for some model problems, they may also yield deceptively-looking, wrong solutions for other simple model problems, in circumstances where the corresponding constrained dynamics formulation may not be easily derived and used.

Description: In this paper the integrability conditions for Killing pairs in flat spaces are investigated and it is shown that only trivial Killing pairs exist.