Library

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.

Description: This article considers the design and implementation of variable-timestep methods for simulating holonomically constrained mechanical systems. Symplectic variable stepsizes are briefly discussed, we then consider time-reparameterization techniques employing a time-reversible (symmetric) integration method to solve the equations of motion. We give several numerical examples, including a simulation of an elastic (inextensible, unshearable) rod undergoing large deformations and collisions with the sides of a bounding box. Numerical experiments indicate that adaptive stepping can significantly smooth the numerical energy and improve the overall efficiency of the simulation.

Description: Symplectic methods, like the Verlet method, are a standard tool for the long term integration of Hamiltonian systems as they arise, for example, in molecular dynamics. One of the reasons for the popularity of symplectic methods is the conservation of energy over very long periods of time up to small fluctuations that scale with the order of the method. In this paper, we discuss a qualitative feature of Hamiltonian systems with separated time scales that is also preserved under symplectic discretization. Specifically, highly oscillatory degrees of freedom often lead to almost preserved quantities (adiabatic invariants). Using recent results from backward error analysis and normal form theory, we show that a symplectic method, like the Verlet method, preserves those adiabatic invariants. We also discuss step-size restrictions necessary to maintain adiabatic invariants in practical computations.

Description: A ranking of a graph is a coloring of the vertex set with positive integers such that on every path connecting two vertices of the same color, there is a vertex of larger color. We consider the directed variant of this problem, where the above condition is imposed only on those paths in which all edges are oriented in the same direction. We show that the ranking number of a directed tree is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time. Unlike the undirected case, however, deciding if the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard.

Description: We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.

Description: A combination of the cascadic conjugate gradient (CCG) method for homogeneous problems with a non-overlapping domain decomposition (DD) method is studied. Mortar finite elements on interfaces are applied to permit non-matching grids in neighboring subdomains. For material jump problems, the method is designed as an alternative to the cascadic methods.

Description: The overall Hamiltonian structure of the Quantum-Classical Molecular Dynamics model makes - analogously to classical molecular dynamics - symplectic integration schemes the methods of choice for long-term simulations. This has already been demonstrated by the symplectic PICKABACK method. However, this method requires a relatively small step-size due to the high-frequency quantum modes. Therefore, following related ideas from classical molecular dynamics, we investigate symplectic multiple-time-stepping methods and indicate various possibilities to overcome the step-size limitation of PICKABACK.

Description: This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.

Description: The paper deals with the solution of the eigenvalue problem of the complex Helmholtz equation. We concentrate on multigrid methods for solving the algebraic eigenproblems arising from discretization with finite elements by using adaptive generated meshes. An illustrative numerical example, the simulation of a waveguide structure from integrated optics, is included.

Description: We describe an optimization process specially designed for regional hyperthermia of deap seated tumors in order to achieve desired steady--state temperature distributions. A nonlinear three--dimensional heat--transfer model based on temperature--dependent blood perfusion is applied to predict the temperature. Optimal heating is obtained by minimizing an integral object function which measures the distance between desired and model predicted temperatures. Sequential minima are calculated from successively improved constant--rate perfusion models employing a damped Newton method in an inner iteration. Numerical results for a Sigma 60 applicator are presented. This work has been supported by Deutsche Forschungsgemeinschaft (DFG) within the Sonderforschungsbereich 273 \glqq Hyperthermie: Methodik und Klinik \grqq .

Description: The paper analyzes a recently proposed iterative error minimizing method for the solution of linear systems. Sufficient and necessary conditions for convergence are studied, which show that the method essentially requires normal matrices. An efficient implementation similar to GMRES has been worked out in detail. Numerical tests on general non--normal matrices, of course, indicate that this approach is not competitive with GMRES. Summarizing, if error minimizing is important, one should rather choose CGNE. A computational niche for GMERR might be problems, where normal but non--symmetric matrices occur, like dissipative quantum mechanics.

Description: Benchmarking of ODE methods has a long tradition. Several sets of test problems have been developed and new problems are still collected. So, a whole variety of problems can be used to check the efficiency of a method under investigation. In general, efficiency is measured by the amount of work whi ch is necessary to get a reliable solution for a prescribed accura cy. In order to quantify the term ``amount of work'' usually not only the computing time is measured but also the number of calls of functional units. To quantify the term ``quality of a numerical solution'' usually the $l_2$--norm of the true error at the final point of the integration interval is used. In our contribution we first discuss some general aspects of benchmarking. Then we present a new test frame which allows to solve typical benchmark problems with some of the state of the art integrators within a unified framework. Finally we show some results of our benchmark tests. Part of the test frame can be used interactively in the World Wide Web.

Description: The report contains the program and the collected abstracts of the 2nd International Symposium ``Algorithms for Macromolecular Modelling''.

Description: Reduced chemical systems are used in the numerical simulation of combustion processes. An automatic approach to generate a reduced model is the so-called intrinsic-low-dimensional manifold (ILDM) by {\sc Maas and Pope}. Thereby, the system state is tabulated as a function of some parameters. The paper analyses the storage requirements for usual interpolation schemes and for sparse grids. It also estimates the response time and gives a short description of an implementation.

Description: This package is an implementation of the $q$-analogues of Gosper's and Zeilberger's algorithm for indefinite, and definite summation of $q$-hypergeometric terms, respectively. An expression $a_k$ is called a {\sl $q$-hypergeometric term}, if $a_{k}/a_{k-1}$ is a rational function with respect to $q^k$. Most $q$-terms are based on the {\sl $q$-shifted factorial} or {\sl qpochhammer}. Other typical $q$-hypergeometric terms are ratios of products of powers, $q$-factorials, $q$-binomial coefficients, and $q$-shifted factorials that are integer-linear in their arguments.

Description: Die Arbeitstagung \glqq Scientific Computing in der Medizin\grqq , kurz SCMED \grq 97, findet vom 22. - 23. September 1997 im neu errichteten Gebäude des Konrad-Zuse-Zentrums auf dem Dahlemer naturwissenschaftlichen Campus der Freien Universtät Berlin statt.

Description: This report contains paper abstracts of the workshop "Visualization and Mathematics" held in Berlin-Dahlem in September 1997. The meeting serves as a forum for an international community of researchers and practitioners on the application of visualization techniques in mathematics and on mathematical concepts in visualization. It is the second symposium in a series of workshops bringing together mathematicians and experts from scientific visualization. The themes of the workshop include: \begin{itemize} \item - applications in differential geometry and partial differential equations \item - algorithmic aspects of adaptive and hierarchical techniques in space and time \item - time control of animated objects and corresponding algorithms \item - algorithmic representation of objects for display, storage and exchange \item - new visualization techniques for mathematical structures \item - integration of visualization with symbolic and numerical computation. \end{itemize}

Description: The present paper gives a brief description of the Math-Net project which is carried out by nine mathematical institutions in Germany, supported by Deutsches Forschungsnetz (DFN) and Deutsche Telekom. The project aims at setting up the technical and organizational infrastructure for efficient, inexpensive and user-driven information services for mathematics. With the aid of active (structured retrieval mechanisms) and passive (profile services) components, electronic mathematical information in Germany will be made available to the scientist at his workplace. The emphasis is put on information about publications, software and data collections, teaching and research activities, but also on organizational and bibliographical information. Decentral organization structures, distributed search systems as well as the use of meta-information (metadata) in accordance with the Dublin Core (hopefully) guarantee a longterm, high-quality repository of data. The well-known mathematical software and data collection netlib\/ will be used as an example to illustrate how such a collection can be adapted to Math-Net. An integration of netlib into HyperWave offers additional perspectives and functionalities.

Description: We present a general technique for constructing nonlocal transparent boundary conditions for time-discretized one-dimensional Schrödinger type equations. The main tool of construction is the discrete counterpart to Mikusi\'nski's continuous algebraic operator approach. Existing techniques are simplified and generalized. Both adaptive time-steps and time-dependent exterior potentials are taken into account.

Description: We present a family of nonlocal transparent boundary conditions for the 2D Helmholtz equation. The whole domain, on which the Helmholtz equation is defined, is decomposed into an interior and an exterior domain. The corresponding interior Helmholtz problem is formulated as a variational problem in standard manner, representing a boundary value problem, whereas the exterior problem is posed as an initial value problem in the radial variable. This problem is then solved approximately by means of the Laplace transformation. The derived boundary conditions are asymptotically correct, model inhomogeneous exterior domains and are simple to implement.

Description: The paper is motivated by the need for a fast robust adaptive multigrid method to solve complex Helmholtz eigenvalue problems arising from the design of optical chips. A nonlinear multigrid method is developed, which can be regarded as an extension of a previous adaptive Rayleigh quotient minimization method for selfadjoint Helmholtz eigenproblems. Since the complex Helmholtz operator is just a compact nonselfadjoint perturbation of a selfadjoint operator, linear algebra techniques like Schur decomposition can be extended from the finite dimensional case. The efficiency of the derived adaptive nonlinear multigrid method is illustrated by computations for a technologically relevant integrated optics component containing Multi Quantum Well Layers.

Description: This paper provides the {\em first} detailed description of the architecture of the computing machines Z1 and Z3 designed by Konrad Zuse in Berlin between 1936 to 1941. The necessary information was obtained from a careful evaluation of the patent application filed by Zuse in 1941. Additional insight was gained from a software simulation of the machine's logic. The Z1 was built using purely mechanical components, the Z3 using electromechanical relays. However, both machines shared a common logical structure and the programming model was exactly the same. We argue that both the Z1 and the Z3 possessed features akin to those of modern computers: memory and processor were separate units, the processor could handle floating-point numbers and compute the four basic arithmetical operations as well as the square root of a number. The program was stored on punched tape and was read sequentially. In the last section of this paper we bring the architecture of the Z1 and Z3 into historical perspective by offering a comparison with computing machines built in other countries.

Description: We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Sun S20-502, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.

Description: We present an algorithm for solving stochastic integer programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-integer variables in each time stage. %We outline a branch-and-bound algorithm for obtaining primal feasible and %possibly optimal solutions. Numerical experience is presented for some two-stage test problems.

Description: The paper presents the concept of a new type of algorithm for the numerical computation of what the authors call the {\em essential dynamics\/} of molecular systems. Mathematically speaking, such systems are described by Hamiltonian differential equations. In the bulk of applications, individual trajectories are of no specific interest. Rather, time averages of physical observables or relaxation times of conformational changes need to be actually computed. In the language of dynamical systems, such information is contained in the natural invariant measure (infinite relaxation time) or in almost invariant sets ("large" finite relaxation times). The paper suggests the direct computation of these objects via eigenmodes of the associated Frobenius-Perron operator by means of a multilevel subdivision algorithm. The advocated approach is different to both Monte-Carlo techniques on the one hand and long term trajectory simulation on the other hand: in our setup long term trajectories are replaced by short term sub-trajectories, Monte-Carlo techniques are just structurally connected via the underlying Frobenius-Perron theory. Numerical experiments with a first version of our suggested algorithm are included to illustrate certain distinguishing properties. A more advanced version of the algorithm will be presented in a second part of this paper.

Description: The aim of this work is to study the accuracy and stability of the Chebyshev--approximation method as a time--discretization for wavepacket dynamics. For this frequently used discretization we introduce estimates of the approximation and round--off error. These estimates mathematically confirm the stability of the Chebyshev--approximation with respect to round--off errors, especially for very large stepsizes. But the results also disclose threads to the stability due to large spatial dimensions. All theoretical statements are illustrated by numerical simulations of an analytically solvable example, the harmonic quantum oszillator.

Description: We present an integrated time--space adaptive finite element method for solving systems of twodimensional nonlinear parabolic systems in complex geometry. The partial differential system is first discretized in time using a singly linearly implicit Runge--Kutta method of order three. Local time errors for the step size control are defined by an embedding strategy. These errors are used to propose a new time step by a PI controller algorithm. A multilevel finite element method with piecewise linear functions on unstructured triangular meshes is subsequently applied for the discretization in space. The local error estimate of the finite element solution steering the adaptive mesh refinement is obtained solving local problems with quadratic trial functions located essentially at the edges of the triangulation. This two--fold adaptivity successfully ensures an a priori prescribed tolerance of the solution. The devised method is applied to laminar gaseous combustion and to solid--solid alloying reactions. We demonstrate that for such demanding applications the employed error estimation and adaption strategies generate an efficient and versatile algorithm.

Description: \iffalse Recently, Todorov and Wilf independently realized that de Branges' original proof of the Bieberbach and Milin conjectures and the proof that was later given by Weinstein deal with the same special function system that de Branges had introduced in his work. In this article, we present an elementary proof of this statement based on the defining differential equations system rather than the closed representation of de Branges' function system. Our proof does neither use special functions (like Wilf's) nor the residue theorem (like Todorov's) nor the closed representation (like both), but is purely algebraic. On the other hand, by a similar algebraic treatment, the closed representation of de Branges' function system is derived. Our whole contribution can be looked at as the study of properties of the Koebe function. Therefore, in a very elementary manner it is shown that the known proofs of the Bieberbach and Milin conjectures can be understood as a consequence of the Löwner differential equation, plus properties of the Koebe function. \fi In his 1984 proof of the Bieberbach and Milin conjectures de Branges used a positivity result of special functions which follows from an identity about Jacobi polynomial sums that was found by Askey and Gasper in 1973, published in 1976. In 1991 Weinstein presented another proof of the Bieberbach and Milin conjectures, also using a special function system which (by Todorov and Wilf) was realized to be the same as de Branges'. In this article, we show how a variant of the Askey-Gasper identity can be deduced by a straightforward examination of Weinstein's functions which intimately are related with a Löwner chain of the Koebe function, and therefore with univalent functions.

Description: This paper presents a large-scale real-world application of the minimum-cost flow problem, describes some details of a new implementation of the network simplex algorithm, and reports on computational comparisions. The real-world test sets include minimum-cost flow problems that are based on single-depot vehicle scheduling problems and on a Lagrangean relaxation of multiple-depot vehicle scheduling problems. Some of the problems are extremely large with up to 42,000 nodes and 20,000,000 arcs. The standard test problems are generated with NETGEN and include parts of the DIMACS standard problems. Our network simplex code is compared with \mbox{RELAX-IV}, Cost Scaling 2 version 3.4, and CPLEX's network solver NETOPT.

Description: Integrals of optimal values of random optimization problems depending on a finite dimensional parameter are approximated by using empirical distributions instead of the original measure. Under fairly broad conditions, it is proved that uniform convergence of empirical approximations of the right hand sides of the constraints implies uniform convergence of the optimal values in the linear and convex case.

Description: The adaptive Rothe method approaches a time-dependent PDE as an ODE in function space. This ODE is solved {\em virtually} using an adaptive state-of-the-art integrator. The {\em actual} realization of each time-step requires the numerical solution of an elliptic boundary value problem, thus {\em perturbing} the virtual function space method. The admissible size of that perturbation can be computed {\em a priori} and is prescribed as a tolerance to an adaptive multilevel finite element code, which provides each time-step with an individually adapted spatial mesh. In this way, the method avoids the well-known difficulties of the method of lines in higher space dimensions. During the last few years the adaptive Rothe method has been applied successfully to various problems with infinite speed of propagation of information. The present study concerns the adaptive Rothe method for hyperbolic equations in the model situation of the wave equation. All steps of the construction are given in detail and a numerical example (diffraction at a corner) is provided for the 2D wave equation. This example clearly indicates that the adaptive Rothe method is appropriate for problems which can generally benefit from mesh adaptation. This should be even more pronounced in the 3D case because of the strong Huygens' principle.

Description: A numerical method for the treatment of moving discontinuities in the model equations of chemical engineering systems is presented. The derived model describing the effects of condensation and evaporation in a regenerative air to air heat exchanger yields an illustrative example for these so called moving boundary problems. The presented adaptive moving grid method is based on the algorithm {\sc Pdex} for parabolic partial differential equations. It is shown that the method is suited for problems where the arising discontinuities cause low rates of convergence if the equations are solved with a static grid.

Description: Nahezu flächendeckend sind die mathematischen Fachbereiche der BRD zum Jahresende '95 im WWW vertreten. Durch die relative hohe Zahl von Servern entstehen Schwierigkeiten bei der Sichtung der angebotenen Information. Wir besprechen "Harvest" als brauchbares und gebrauchsfähiges Hilfsmittel zur Dokumentation.

Description: In this thesis we describe a practical problem that we encountered in the on--line optimization of a complex Flexible Manufacturing System. In the considered system a stacker crane has to fulfill all transportation tasks (jobs) in a single aisled automatic storage system. The jobs have to be sequenced in such a way, that the time needed for the unloaded moves is minimized. The modelling of this question leads to the so--called on--line Hamiltonian path problem. We computationally compare several on--line heuristics and derive lower bounds on the value obtained by an optimal on--line strategy by analyzing two off--line Combinatorial Optimization problems: the asymmetric Hamiltonian path problem with precedence constraints, also called sequential ordering problem (SOP), and the asymmetric Hamiltonian path problem with time windows (AHPPTW). We study the SOP and AHPPTW from a polyhedral point of view and derive several new classes of valid inequalities. Based on the polyhedral investigations we develop branch&cut algorithms for both problems and can achieve encouraging results on solving problem instances from real--world examples of the practical application.

Description: The Internet and the new electronic means of information and communication are transforming scientific communication fundamentally. In particular, mathematicians, physicists and other natural scientists intensify, accelerate and extend their communication by the use of the Internet and its tools, from electronic mail up to the World Wide Web. In doing so, they also exchange scientific results of a new kind and quality yet unknown to traditional information providers such as publishers, libraries, and database suppliers (e.g. in the form of current research software, scientific data collections, observations and experimental data, visualizations, animations etc.). They, on the other hand, perceive the new ways, which are passing their own field of activity, as breakdowns of traditional publishing, as it was termed by the Association of Computing Machinery. In addition, scientific libraries find themselves caught in a structural crisis -- not only because of budget restraints. The {\it Deutsche Mathematiker-Vereinigung} (DMV), however, sees the new electronic means as an opportunity to master a crisis of this kind rather than a threat. By discussing concrete models, which may be - in a certain technical sense -- realizable already today, the article gives an introduction into the subject of a {\it Distributed Information- and Communication System for Mathematics}, a project prepared and planned by the DMV for the years 1996 to 1998. In the context of possible realization variants it also deals with questions of costs, resulting load of network connections, and -- showing the beginnings -- the (absolutely essential) solution of problems related to quality, authenticity, archival and intellectual property rights, which arise with the employment of electronic means. Obviously (even if not discussed explicitly) also computing centers, whose tasks and position are also affected by the electronic revolution, have the chance to find a new and forward-looking role in this field - in particular by new forms of cooperation with scientific libraries.

Description: We present parallel formulations of the well established extrapolation algorithms EULSIM and LIMEX and its implementation on a distributed memory architecture. The discretization of partial differential equations by the method of lines yields large banded systems, which can be efficiently solved in parallel only by iterative methods. Polynomial preconditioning with a Neumann series expansion combined with an overlapping domain decomposition appears as a very efficient, robust and highly scalable preconditioner for different iterative solvers. A further advantage of this preconditioner is that all computation can be restricted to the overlap region as long as the subdomain problems are solved exactly. With this approach the iterative algorithms operate on very short vectors, the length of the vectors depends only on the number of gridpoints in the overlap region and the number of processors, but not on the size of the linear system. As the most reliable and fast iterative methods based on this preconditioning scheme appeared GMRES or FOM and BICGSTAB. To further reduce the number of iterations in GMRES or FOM we can reuse the Krylov-spaces constructed in preceeding extrapolation steps. The implementation of the method within the program LIMEX results in a highly parallel and scalable program for solving differential algebraic problems getting an almost linear speedup up to 64 processors even for medium size problems. Results are presented for a difficult application from chemical engineering simulating the formation of aerosols in industrial gas exhaust purification.

Description: We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.

Description: The paper presents computations of decaying two--dimensional turbulence in an adaptive wavelet basis. At each time step the vorticity is represented by an adaptively selected set of wavelet functions which adjusts to the instantaneous distribution of vorticity. The results of this new algorithm are compared to a classical Fourier method and a Fourier method supplemented with wavelet compression in each time step.

Description: For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.

Description: In General Relativity, the motion of expanding shearfree perfect fluids is governed by the ordinary differential equation $y^{\prime \prime }=$ $% F(x)\,y^2$ , where $F$ is an arbitrary function from which the equation of state can be computed. A complete symmetry analysis of this differential equation is given; its solutions are classified according to this scheme, and in particular the relation to Wyman's Painlev\'e analysis is clarified.

Description: We perform a high statistics calculation of the equation of state for non-compact QED on large lattices. The calculation extends to fermionic correlation lengths of $\approx 8$, and it is combined with a finite size scaling analysis of the lattice data.

Description: We consider the fast solution of large, piecewise smooth minimization problems as resulting from the approximation of elliptic free boundary problems. The most delicate question in constructing a multigrid method for a nonlinear, non--smooth problem is how to represent the nonlinearity on the coarse grids. This process usually involves some kind of linearization. The basic idea of monotone multigrid methods to be presented here is first to select a neighborhood of the actual smoothed iterate in which a linearization is possible and then to constrain the coarse grid correction to this neighborhood. Such a local linearization allows to control the local corrections at each coarse grid node in such a way that the energy functional is monotonically decreasing. This approach leads to globally convergent schemes which are robust with respect to local singularities of the given problem. The numerical performance is illustrated by approximating the well-known Barenblatt solution of the porous medium equation.

Description: We prove inequalities relating the inradius of a convex body with interior containing no point of the integral lattice, with the volume or surface area of the body. These inequalities are tight and generalize previous results.

Description: \small Many interesting phenomena in molecular systems like interactions between macro-molecules, protein-substrate docking, or channeling processes in membranes are gouverned to a high degree by classical Coulomb or van-der-Waals forces. The visualization of these force fields is important for verifying numerical simulations. Moreover, by inspecting the forces visually we can gain deeper insight into the molecular processes. Up to now the visualization of vector fields is quite unusual in computational chemistry. In fact many commercial software packages do not support this topic at all. The reason is not that vector fields are considered unimportant, but mainly because of the lack of adequate visualization methods. In this paper we survey a number of methods for vector field visualization, ranging from well-known concepts like arrow or streamline plots to more advanced techniques like line integral convolution, and show how these can be applied to computational chemistry. A combination of the most meaningful methods in an interactive 3D visualization environment can provide a powerful tool box for analysing simulations in molecular dynamics.

Description: In this paper we generalize a result by Rubin and Ungar on Hamiltonian systems containing a strong constraining potential to Langevin dynamics. Such highly oscillatory systems arise, for example, in the context of molecular dynamics. We derive constrained equations of motion for the slowly varying solution components. This includes in particular the derivation of a correcting force-term that stands for the coupling of the slow and fast degrees of motion. We will identify two limiting cases: (i) the correcting force becomes, over a finite interval of time, almost identical to the force term suggested by Rubin and Ungar (weak thermal coupling) and (ii) the correcting force can be approximated by the gradient of the Fixman potential as used in statistical mechanics (strong thermal coupling). The discussion will shed some light on the question which of the two correcting potentials is more appropriate under which circumstances for molecular dynamics. In Sec.~7, we also discuss smoothing in the context of constant temperature molecular dynamics.

Description: We present efficient techniques for the numerical approximation of complicated dynamical behavior. In particular, we develop numerical methods which allow to approximate SBR-measures as well as (almost) cyclic behavior of a dynamical system. The methods are based on an appropriate discretization of the Frobenius-Perron operator, and two essentially different mathematical concepts are used: the idea is to combine classical convergence results for finite dimensional approximations of compact operators with results from Ergodic Theory concerning the approximation of SBR-measures by invariant measures of stochastically perturbed systems. The efficiency of the methods is illustrated by several numerical examples.

Description: We present Multilevel Finite Element computations for twodimensional reaction-diffusion systems modelling laminar flames. These systems are prototypes for extreme stiffness in time and space. The first of these two rather general features is accounted for by an improved control mechanism for the time step. The second one is reflected through very thin travelling reaction fronts for which we propose an anisotropic discretization by local directional refinement.

Description: Simplified chemical kinetic schemes are a crucial prerequisite for the simulation of complex three-dimensional turbulent flows, and various methods for the generation of reduced mechanisms have been developed in the past. The method of intrinsic low-dimensional manifolds (ILDM), e.g., provides a mathematical tool for the automatic simplification of chemical kinetics, but one problem of this method is the fact that the information which comes out of the mechanism reduction procedure has to be stored for subsequent use in reacting flow calculations. In most cases tabulation procedures are used which store the relevant data (such as reduced reaction rates) in terms of the reaction progress variables, followed by table look-up during the reacting flow calculations. This can result in huge amounts of storage needed for the multi-dimensional tabulation. In order to overcome this problem we present a storage scheme which is based on orthogonal polynomials. Instead of using small tabulation cells and local mesh refinement, the thermochemical state space is divided into a small number of coarse cells. Within these coarse cells polynomial approximations are used instead of frequently used multi-linear interpolation. This leads to a considerable decrease of needed storage. The hydrogen-oxygen system is considered as an example. Even for this small chemical system we obtain a decrease of the needed storage requirement by a factor of 100.

Description: The Car-Parrinello (CP) approach to ab initio molecular dynamics serves as an approximation to time-dependent Born-Oppenheimer (BO) calculations. It replaces the explicit minimization of the energy functional by a fictitious Newtonian dynamics and therefore introduces an artificial mass parameter $\mu$ which controls the electronic motion. A recent theoretical investigation shows that the CP-error, i.e., the deviation of the CP--solution from the BO-solution {\em decreases} like $\mu^{1/2}$ asymptotically. Since the computational effort {\em increases} like $\mu^{-1/2}$, the choice of $\mu$ has to find a compromise between efficiency and accuracy. The asymptotical result is used in this paper to construct an easily implemented algorithm which automatically controls $\mu$: the parameter $\mu$ is repeatedly adapted during the simulation by choosing $\mu$ as large as possible while pushing an error measure below a user-given tolerance. The performance and reliability of the algorithm is illustrated by a typical example.

Description: The Car-Parrinello method for ab-initio molecular dynamics avoids the explicit minimization of energy functionals given by functional density theory in the context of the quantum adiabatic approximation (time-dependent Born-Oppenheimer approximation). Instead, it introduces a fictitious classical dynamics for the electronic orbitals. For many realistic systems this concept allowed first-principle computer simulations for the first time. In this paper we study the {\em quantitative} influence of the involved parameter $\mu$, the fictitious electronic mass of the method. In particular, we prove by use of a carefully chosen two-time-scale asymptotics that the deviation of the Car-Parrinello method from the adiabatic model is of order ${\rm O}(\mu^{1/2})$ --- provided one starts in the ground state of the electronic system and the electronic excitation spectrum satisfies a certain non-degeneracy condition. Analyzing a two-level model problem we prove that our result cannot be improved in general. Finally, we show how to use the gained quantitative insight for an automatic control of the unphysical ``fake'' kinetic energy of the method.

Description: We consider backward error analysis of numerical approximations to ordinary differential equations, i.e., the numerical solution is formally interpreted as the exact solution of a modified differential equation. A simple recursive definition of the modified equation is stated. This recursion is used to give a new proof of the exponentially closeness of the numerical solutions and the solutions to an appropriate truncation of the modified equation. We also discuss qualitative properties of the modified equation and apply these results to the symplectic variable step-size integration of Hamiltonian systems, the conservation of adiabatic invariants, and numerical chaos associated to homoclinic orbits.

Description: This paper presents two Lagrangean relaxation approaches for the {\em NP}-hard multiple-depot vehicle scheduling problem in public mass transit and reports on computational investigations. Our Lagrangean relaxation approaches can be applied to generate very tight lower bounds and to compute feasible solutions efficiently. A further application is to use the Lagrangean relaxations as new pricing strategies for a delayed column generation of a branch-and-cut approach. The computational investigations are based on real-world test sets from the cities of Berlin and Hamburg having up to 25 thousand timetabled trips and 70 million dead-head trips.

Description: It is well-known that by polynomial elimination methods, in particular by the computation of Gröbner bases, proofs for geometric theorems can be automatically generated. %% Several monographs On the other hand, it is much less known that Gröbner bases, in combination with rational factorization, can be even used to {\sl find} new geometric theorems. In this article such a method is described, and some new theorems on plane triangles are deduced.