Library

Description: The paper's main result is a simple derivation rule for the Jacobi polynomials with respect to their parameters, i.e. for $\partial_{\alpha} P_n^{\alpha,\beta}$, and $\partial_{\beta} P_n^{\alpha,\beta}$. It is obtained via relations for the Gaussian hypergeometric function concerning parameter derivatives and integer shifts in the first two arguments. These have an interest on their own for further applications to continuous and discrete orthogonal polynomials. The study is motivated by a Galerkin method with moving weight, presents all proofs in detail, and terminates in a brief discussion of the generated polynomials.

Description: We derive a simple accuracy matching strategy for inexact Gauss Newton methods and apply it to the numerical solution of boundary value problems of ordinary differential equations by collocation. The matching strategy is based on an affine contravariant convergence theorem, i. e. , the characteristic constants are invariant under affine transformations of the domain. The inexact Gauss Newton method is applied to an integral formulation of the BVP. As discretization for the arising linear subproblems we employ adaptive collocation at Gaussian nodes with varying local orders and stepsizes. The grids are chosen via adaptive refinement and order selection.

Description: In this article we present a method to implement orthogonal polynomials and many other special functions in Computer Algebra systems enabling the user to work with those functions appropriately, and in particular to verify different types of identities for those functions. Some of these identities like differential equations, power series representations, and hypergeometric representations can even dealt with algorithmically, i.\ e.\ they can be computed by the Computer Algebra system, rather than only verified. The types of functions that can be treated by the given technique cover the generalized hypergeometric functions, and therefore most of the special functions that can be found in mathematical dictionaries. The types of identities for which we present verification algorithms cover differential equations, power series representations, identities of the Rodrigues type, hypergeometric representations, and algorithms containing symbolic sums. The current implementations of special functions in existing Computer Algebra systems do not meet these high standards as we shall show in examples. They should be modified, and we show results of our implementations.

Description: {\newcommand{\R} {{\rm {\mbox{\protect\makebox[.15em][l]{I}R}}}} Given a list of $n$ numbers in $\R $, one wants to decide wether every number in the list occurs at least $k$ times. I will show that $(1-\epsilon)n\log_3(n/k)$ is a lower bound for the depth of a linear decision tree determining this problem. This is done by using the Björner-Lov\'asz method, which turns the problem into one of estimating the Möbius function for a certain partition lattice. I will also calculate the exponential generating function for the Möbius function of a partition poset with restricted block sizes in general.}

Description: Die Autoren sind sich dar{ü}ber im klaren, daß zahlreiche Imponderabilien die Ergebnisse der vorgelegten Modellrechnungen beeinflussen k{ö}nnen. Immerhin repräsentiert jedoch das vorgelegte mathematische Modell die Summe unserer derzeitigen Kenntnisse zur Fragestellung AIDS--Epidemie; neu hinzukommende Erkenntnisse lassen sich rasch einarbeiten und in ihren Konsequenzen überschauen. Die Entwicklung neuer effizienter numerischer Methoden spielte eine Schlüsselrolle bei der tatsächlichen Simulation dieses umfangreichen realitätsnahen mathematischen Modells.

Description: We present an adaptive Rothe method for two--dimensional problems combining an embedded Runge--Kutta scheme in time and a multilevel finite element discretization in space. The spatial discretization error is controlled by a posteriori error estimates based on interpolation techniques. A computational example for a thermodiffusive flame propagation model illustrates the high accuracy that is possible with the proposed method.

Description: The multicommodity linear formulation of the Fixed Charge Network Flow Design problem is known to have significantly sharp linear relaxation lower bounds. However the tradeoff is the introduction of a large amount of artificial variables. We exhibit a class of special instances for which the lower bound is tight. Further we completly describe the polyhedron in the space of the natural variables.

Description: Die von der DMV-Fachgruppe Scientific Computing in Kooperation mit dem gleichnamigen GAMM-Fachausschuss organisierte Tagung \glqq Scientific Computing in der Theoretischen Physik\grqq~fand vom 16. - 18. März 1994 am Fachbereich Mathematik und Informatik der Freien Universität Berlin statt. Ziel des Workshops war, die Kontakte zwischen den Fachleuten der Gebiete {\em Computational Physics} und {\em Scientific Computing} zu intensivieren. Schwerpunkte des Workshops waren numerische Simulation von Transportmodellen der Astrophysik und Halbleiterphysik, Multilevel-Methoden für partielle Differentialgleichungen sowie Monte-Carlo-Methoden und molekulardynamische Verfahren für Probleme der Statistischen Physik und Quantenfeldtheorie. Der Workshop fand ein äusserst positives Echo und führte über 70 Teilnehmer der verschiedenen Teilgebiete der Theoretischen Physik und ca. 50 Teilnehmer aus dem Bereich der Numerischen Mathematik zusammen. \originalTeX

Description: We give an overview of an approach on special functions due to Truesdell, and show how it can be used to develop certain type of identities for special functions. Once obtained, these identities may be verified by an independent algorithmic method for which we give some examples.

Description: {\newcommand{\N} {{\rm {\mbox{\protect\makebox[.15em][l]{I}N}}}} In several publications the first author published an algorithm for the conversion of analytic functions for which derivative rules are given into their representing power series $\sum\limits_{k=0}^{\infty}a_{k}z^{k}$ at the origin and vice versa, implementations of which exist in {\sc Mathematica}, {\sc Maple} and {\sc Reduce}. One main part of this procedure is an algorithm to derive a homogeneous linear differential equation with polynomial coefficients for the given function. We call this type of ordinary differential equations {\sl simple}. Whereas the opposite question to find functions satisfying given differential equations is studied in great detail, our question to find differential equations that are satisfied by given functions seems to be rarely posed. In this paper we consider the family $F$ of functions satisfying a simple differential equation generated by the rational, the algebraic, and certain transcendental functions. It turns out that $F$ forms a linear space of transcendental functions. % with polynomial function coefficients. Further $F$ is closed under multiplication and under the composition with rational functions and rational powers. These results had been published by Stanley who had proved them by theoretical algebraic considerations. In contrast our treatment is purely algorithmically oriented. We present algorithms that generate simple differential equation for $f+g$, $f\cdot g$, $f\circ r$ ($r$ rational), and $f\circ x^{p/q}$ ($p,q\in\N_0$), given simple differential equations for $f$, and $g$, and give a priori estimates for the order of the resulting differential equations. We show that all order estimates are sharp. After finishing this article we realized that in independent work Salvy and Zimmermann published similar algorithms. Our treatment gives a detailed description of those algorithms and their validity.}

Description: The power of the symbolic math system {\small REDUCE} for solving large and difficult problems in science and engineering is demonstrated by a set of model problems. These include algebraic equation solving, formal variable elimination, formal power series, symbolic treatment of differential equations and applications from theoretical physics.

Description: Results from finite-element-calculations are usually visualized by colored surface- and contour-line-plots or polygonal patches or simply displaced lines and grids. In computer graphics however more advanced techniques like texture-mapping and NURBS are well established and there exist efficient algorithms and implementations. We show that these techniques are not only easy to use, but form a very natural and far more efficient approach for visualization of higher order finite-element's solutions like in $p$- and $h$-$p$-version. Texture-mapping is useful for displaying vector-valued data, too.

Description: In Quantum Chemistry the field of Laser--Assisted Molecular Control'' has received a considerable amount of attention recently. One key problem in this new field is the simulation of the dynamical reaction of a molecule subjected to external radiation. This problem is described by the Schrödinger equation, which, after eigenfunction expansion, can be written in the form of a large system of ordinary differential equations, the solutions of which show a highly oscillatory behaviour. The oscillations with high frequencies and small amplitudes confine the stepsizes of any numerical integrator -- an effect, which, in turn, blows up the simulation time. Larger stepsizes can be expected by averaging these fast oscillations, thus smoothing the trajectories. Standard smoothing techniques (averaging, filtering) would kill the whole process and thus, lead to wrong numerical results. To avoid this unwanted effect and nevertheless speed up computations, this paper presents a quasiresonant smoothing algorithm (QRS). In QRS, a natural splitting parameter $\delta$ controls the smoothing properties. An adaptive QRS--version (AQRS) is presented which includes an error estimation scheme for choosing this parameter $\delta$ in order to meet a given accuracy requirement. In AQRS $\delta$ is permanently adapted to the solution properties for computing the chemically necessary information'' only. The performance of AQRS is demonstrated in several test problems from the field Laser--Assisted Selective Excitation of Molecules'' in which the external radiation is a picosecond laser pulse. In comparison with standard methods speedup factors of the order of $10^2$ are observed.

Description: This article describes the REDUCE package ZEILBERG implemented by Gregor Stölting and the author. The REDUCE package ZEILBERG is a careful implementation of the Gosper (The sum package contains also a partial implementation of the Gosper algorithm.) and Zeilberger algorithms for indefinite, and definite summation of hypergeometric terms, respectively. An expression $a_k$ is called a {\sl hypergeometric term} (or {\sl closed form}), if $a_{k}/a_{k-1}$ is a rational function with respect to $k$. Typical hypergeometric terms are ratios of products of powers, factorials, $\Gamma$ function terms, binomial coefficients, and shifted factorials (Pochhammer symbols) that are integer-linear in their arguments.

Description: We test the performance of the multicanonical approach for biological molecules. The simulated molecules are frustrated systems with a complicated energy landscape. The resulting slowing down in simulations is alleviated by our ansatz. We perform a multicanonical simulation of nonpolar amino acids and study their $\alpha$-helix propensities. The results are shown to be in agreement with recent experimental results.

Description: In an array of coupled oscillators {\em synchronous chaos} may occur in the sense that all the oscillators behave identically although the corresponding motion is chaotic. When a parameter is varied this fully symmetric dynamical state can lose its stability, and the main purpose of this paper is to investigate which type of dynamical behavior is expected to be observed once the loss of stability has occurred. The essential tool is a classification of Lyapunov exponents based on the symmetry of the underlying problem. This classification is crucial in the derivation of the analytical results but it also allows an efficient computation of the dominant Lyapunov exponent associated with each symmetry type. We show how these dominant exponents determine the stability of invariant sets possessing various instantaneous symmetries and this leads to the idea of {\em symmetry breaking bifurcations of chaotic attractors}. Finally the results and ideas are illustrated for several systems of coupled oscillators.

Description: We present new Monte Carlo results in non-compact lattice QED with staggered fermions down to $m_0 = 0.005$. This extends our previous investigations on the nature of the continuum limit of QED.

Description: The celebrated Zeilberger algorithm which finds holonomic recurrence equations for definite sums of hypergeometric terms $F(n,k)$ is extended to certain nonhypergeometric terms. An expression $F(n,k)$ is called hypergeometric term if both $F(n+1,k)/F(n,k)$ and $F(n,k+1)/F(n,k)$ are rational functions. Typical examples are ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are integer-linear with respect to $n$ and $k$ in their arguments. We consider the more general case of ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are rational-linear with respect to $n$ and $k$ in their arguments, and present an extended version of Zeilberger's algorithm for this case, using an extended version of Gosper's algorithm for indefinite summation. In a similar way the Wilf-Zeilberger method of rational function certification of integer-linear hypergeometric identities is extended to rational-linear hypergeometric identities. The given algorithms on definite summation apply to many cases in the literature to which neither the Zeilberger approach nor the Wilf-Zeilberger method is applicable. Examples of this type are given by theorems of Watson and Whipple, and a large list of identities (``Strange evaluations of hypergeometric series'') that were studied by Gessel and Stanton. It turns out that with our extended algorithms practically all hypergeometric identities in the literature can be verified. Finally we show how the algorithms can be used to generate new identities. REDUCE and MAPLE implementations of the given algorithms can be obtained from the author, many results of which are presented in the paper.

Description: We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework. \\{\bf Abstract: }We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework.

Description: We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes and similar linear programs with exponential decreasing paths. The analysis of two randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds conjectured in the literature. At the same time, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.

Description: We consider nested iterations, in which the multigrid method is replaced by some simple basic iteration procedure, and call them {\em cascadic iterations}. They were introduced by Deuflhard, who used the conjugate gradient method as basic iteration (CCG method). He demonstrated by numerical experiments that the CCG method works within a few iterations if the linear systems on coarser triangulations are solved accurately enough. Shaidurov subsequently proved multigrid complexity for the CCG method in the case of $H^2$-regular two-dimensional problems with quasi-uniform triangulations. We show that his result still holds true for a large class of smoothing iterations as basic iteration procedure in the case of two- and three-dimensional $H^{1+\alpha}$-regular problems. Moreover we show how to use cascadic iterations in adaptive codes and give in particular a new termination criterion for the CCG method.

Description: The results from invariant theory and the results for semi-invariants and equivariants are summarized in a way suitable for the combination with Gröbner basis computation. An algorithm for the determination of fundamental equivariants using projections and a Poincar\'{e} series is described. Secondly, an algorithm is given for the representation of an equivariant in terms of the fundamental equivariants. Several ways for the exact determination of zeros of equivariant systems are discussed

Description: We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.

Description: In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design.

Description: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set $N$ of items, a capacity $F \in \N$ and weights $a_i \in \N$, $i \in N$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{i \in N} a_i x_i \leq F.$$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where $a_i \in \{\mu,\lambda\}$ for all items $i \in N$ and $1 \leq \mu 〈 \lambda \leq b$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.}

Description: We compare a few variants of the recently proposed multicanonical method with the well known simulated annealing for the effectiveness in search of the energy global minimum of a biomolecular system. For this we study in detail Met-enkephalin, one of the simplest peptides. We show that the new method not only outperforms simulated annealing in the search of the energy groundstate but also provides more statistical-mechanical information about the system.

Description: We demonstrate the effectiveness of the multicanonical algorithm for the tertiary structure prediction of peptides and proteins. Unlike to simulated annealing the relationship to the canonical ensemble remains exactly controlled. Hence, the new method allows not only the prediction of the lowest-energy conformation, but also the calculation of thermodynamic quantities at various temperature from one run.

Description: Die enorme algorithmische Beschleunigung durch diskrete Galerkin-Methoden f{ü}r abz{ä}hlbare Differentialgleichungssysteme hat der Simulation von Polymerisationsprozessen neue, industriell relevante Problembereiche er{ö}ffnet, die mit den bis dahin verf{ü}gbaren Methoden nicht zug{ä}nglich waren.

Description: Large chemical computations show the need for full adaptivity supporting the development of robust and highly efficient programs. For solutions possessing sharp moving spatial transitions, as travelling wavefronts or emerging boundary and internal layers, an automatic adjustment of both the space and the time stepsize is generally accepted to be more successful in efficient resolving critical regions of high spatial and temporal activity. In contrast to the widespread discretization sequence first space then time the reversed sequence first time then space is employed. Full adaptivity of the proposed algorithm is realized by combining embedded time discretization and multilevel finite element space discretization. In this paper the algorithm is described for one--dimensional problems. The numerical results show the significantly new perspectives opened by this approach.

Description: An error controlled finite elemente method (FEM) for solving stationary Schrödinger equations in three space dimensions is proposed. The method is based on an adaptive space discretization into tetrahedra and local polynomial basis functions of order $p=1$--$5$ defined on these tetrahedra. According to a local error estimator the triangulation is automatically adapted to the solution. Numerical results for standard problems appearing in vibrational motion and molecular structure calculations are presented and discussed. Relative precisions better than 1e-8 are obtained. For equilateral H$_3^{++}$ the adaptive FEM turns out to be superior to global basis set expansions in the literature. Our precise FEM results exclude in a definite manner the stability or metastability of equilateral H$_3^{++}$ in its groundstate.

Description: {\def\NP{\hbox{$\cal N\kern-.1667em\cal P$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be $\NP$-hard in the strong sense. We show that the storage assignment problem is $\NP$-hard for {\sl bounded sizes and capacities}, even if the sizes have values $1$ and~$2$ and the capacities value~$2$ only, a case we encountered in practice. Moreover, we prove that no polynomial time $\epsilon$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}

Description: We consider the numerical treatment of Hamiltonian systems that contain a potential which grows large when the system deviates from the equilibrium value of the potential. Such systems arise, e.g., in molecular dynamics simulations and the spatial discretization of Hamiltonian partial differential equations. Since the presence of highly oscillatory terms in the solutions forces any explicit integrator to use very small step-size, the numerical integration of such systems provides a challenging task. It has been suggested before to replace the strong potential by a holonomic constraint that forces the solutions to stay at the equilibrium value of the potential. This approach has, e.g., been successfully applied to the bond stretching in molecular dynamics simulations. In other cases, such as the bond-angle bending, this methods fails due to the introduced rigidity. Here we give a careful analysis of the analytical problem by means of a smoothing operator. This will lead us to the notion of the smoothed dynamics of a highly oscillatory Hamiltonian system. Based on our analysis, we suggest a new constrained formulation that maintains the flexibility of the system while at the same time suppressing the high-frequency components in the solutions and thus allowing for larger time steps. The new constrained formulation is Hamiltonian and can be discretized by the well-known SHAKE method.

Description: We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.

Description: We consider periodic orbits of autonomous parameter dependent ODE's. Starting from a shooting algorithm for the numerical computation of periodic orbits via an adaptive Poincar\'e-section we develop a pathfollowing algorithm for periodic solutions based on a tangential continuation method with implicit reparametrization. For ODE's equivariant w.r.t. a finite group we show that spatial as well as spatio-temporal symmetries of periodic orbits can be exploited within the (multiple) shooting context. We describe how turning points, period doubling bifurcations and Hopf points along the branch of periodic solutions can be handled. Furthermore equivariant Hopf points and generic secondary bifurcations of periodic orbits with $ Z_m$-symmetry are treated. We tested the code with standard examples, e.g., the period doubling cascade in the Lorenz equations. To show the efficiency of the described methods we also used the program for an application from electronics, a ring oscillator with $n $ inverters. In this example the exploitation of symmetry reduces the amount of work for the continuation of periodic orbits from ${\cal O}(n^2)$ to ${\cal O}(n)$

Description: In this article algorithmic methods are presented that have been incorporated in computer algebra systems in the last five years. The methods can be used to identify transcendental functions. The essential idea due to Zeilberger is to represent the functions by systems of holonomic differential and recurrence equations, and the identification procedure utilizes algorithms of Stanley and Zeilberger. Also a noncommutative version of the Buchberger algorithm can be applied.

Description: In this paper we modify Buchberger's $S$-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established.

Description: Adopting a statistical approach for the computation of turbulent combustion flows an approximation for the probability density function (PDF) of the composition variables is often required to treat the highly non-linear reaction term in a satisfactory way. One class of methods currently being used are the moment methods which employ transport equations for low order statistical moments and use a parametrized shape of the PDF. A second class solves a transport equation for the joint PDF by a Monte Carlo method. In the present paper we develop an intermediate algorithm based on a Galerkin method for the PDF transport equation. The solution is developed in terms of an orthogonal or bi-orthogonal basis of a suitable Hilbert space. The unconventional use of the related weight function as a prefactor (moving weight approach) permits adaptivity and results in a generalization of the $\beta-$closure for bounded scalar quantities. We present the approximation procedure in detail and apply it to the evolution of the composition in a homogeneous well-stirred reactor. The extension to non-homogeneous flow simulations is straightforward.

Description: Combinatorial optimization problems pervade many areas of human problem solving especially in the fields of business, economics and engineering. Intensive mathematical research and vast increases in raw computing power have advanced the state of the art in exact and heuristic problem solving at a pace that is unprecedented in human history. We survey here in layman's terms some of the fundamental concepts and principles that have led this progress. (This article will appear -- possibly in modified form -- in a popular science magazine.)

Description: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set $N$ of items and a capacity $b \in \N$, and let $N_j$ be the set of items with weight $j$, $1 \leq j \leq b$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.$$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) $N_j = \emptyset$ for all $1 〈 j \leq \lfloor {b \over 2} \rfloor$ and (b) $N_j = \emptyset$ for all $1 〈 j \leq \lfloor {b \over 3} \rfloor$ and $N_j = \emptyset$ for all $j \geq \lfloor {b \over 2} \rfloor + 1$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.}

Description: In the field of deep regional hyperthermia, one of the most widely used devices is the BSD--2000 Hyperthermia System which employs the Sigma 60 applicator. The Sigma 60 consists of four independent sources, giving it the potential to control the energy pattern within the patient. The independent amplitudes and phases, as well as frequency selection and applicator position, present a large number of parameters for the operator to determine. Computer simulation has long been recognized as an attractive approach to optimizing these parameters. A treatment planning program was used in clinical practice at Stanford University Medical Center for two years. It demonstrated the feasibility of computer simulation for deep regional hyperthermia in a clinical situation. However, several parts of this system were written in a language specific to one workstation, which severely restricted the wider distribution of the program to other users of the Sigma 60. A new treatment planning system for the BSD 2000 has been developed and put into clinical practice at the Rudolf Virchow Clinic of the Free University of Berlin. The new method, which we will refer to as the Berlin system, has a simpler model construction program and a considerably better graphics capability. However, the most important feature is that all programs are written in FORTRAN, C, or the X Window graphics system. Therefore, the entire treatment planning system is completely portable to other workstations.

Description: In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.

Description: The aim of this paper is to compute all isolated solutions to symmetric polynomial systems. Recently, it has been proved that modelling the sparse structure of the system by its Newton polytopes leads to a computational breakthrough in solving the system. In this paper, it will be shown how the Lifting Algorithm, proposed by Huber and Sturmfels, can be applied to symmetric Newton polytopes. This symmetric version of the Lifting Algorithm enables the efficient construction of the symmetric subdivision, giving rise to a symmetric homotopy, so that only the generating solutions have to be computed. Efficiency is obtained by combination with the product homotopy. Applications illustrate the practical significance of the presented approach.

Description: In this paper we describe the convex hull of all solutions of the integer bounded knapsack problem in the special case when the weights of the items are divisible. The corresponding inequalities are defined via an inductive scheme that can also be used in a more general setting.

Description: Die Kombination von elektronischer Fachinformation mit den neuen Mitteln der Kommunikation eröffnet neue Perspektiven für die Mathematik in Deutschland. Aufbauend auf das laufende, BMFT-geförderte Projekt ``Fachinformation'' der Deutschen Mathematiker-Vereinigung (DMV) plant die DMV eine Querschnittsaktivität für die Mathematik. Diese soll nicht nur die mathematischen Fachbereiche und Forschungsinstitute einbeziehen, sondern auch mathematische Forschungslabors aus der Industrie und die Informationsversorger der Mathematik, insbesondere die wissenschaftlichen Verlage, die TIB Hannover, die Bibliotheken der Universitäten und \mbox{-- nicht zuletzt --} das FIZ Karlsruhe mit dem Zentralblatt für Mathematik. \noindent Auf der technischen Grundlage des Internet und seiner weltweit verbreiteten Informationsdienste (Gopher, WAIS, WorldWideWeb, Hyper-G, ftp und E-mail) soll ein verteiltes, mathematisches Informationssystem geschaffen werden, bei dem die Partner des gemeinsamen Vorhabens ihre örtlichen Ressourcen untereinander und zugleich weltweit verfügbar machen. Diese Ziele sind durch konsequenten Einsatz von Software erreichbar, die nach dem Client-Server-Modell strukturiert und die im Internet verbreitet bzw.~anerkannt ist. \noindent Die Bereitstellung von Technik reicht keineswegs aus. Ohne die Schaffung einer personellen, organisatorischen und technischen Infrastruktur ist die Durchführung eines solchen Projekts nicht möglich. Als Massnahmen sind - für alle Partner - geplant: \hspace*{2mm} * Schaffung der Funktion des Informationsbeauftragten \hspace*{2mm} * Einrichtung eines gemeinsamen ``Forums für mathematische Information'' \hspace*{2mm} * Errichtung und Betreuung von mathematischen Informationsstationen \hspace*{2mm} * Teilnahme an nationalen und internationalen Standardisierungsmassnahmen \hspace*{2mm} * Workshops und regelmässige Schulungen, Öffentlichkeitsarbeit \noindent Als Aktivitäten - mit Focus auf mathematische Fachinformation - sind folgende Teilaufgaben und Pilotvorhaben bei allen Partnern geplant: \hspace*{2mm} * Einrichtung von elektronischen Informationssystemen \hspace*{2mm} * Verteiltes elektronisches Angebot von Preprints und Skripten (Volltexte) \hspace*{2mm} * Verteiltes elektronisches Angebot von Software- und Datensammlungen \hspace*{2mm} * Zugriff auf globale Informationssysteme in der Mathematik \hspace*{2mm} * Organisation eines Lebenden Mathematischen Museums \hspace*{2mm} * Zugriff auf elektronische Kataloge von Bibliotheken, insbesondere Fachbereichsbibliotheken \hspace*{2mm} * Schaffung eines organisatorischen Rahmens für elektronische mathematische Journale \hspace*{2mm} * Elektronisches Angebot von eingescannten historischen Dokumenten und Büchern \hspace*{2mm} * Schaffung einer Organisationsform für elektronisches Reviewing \hspace*{2mm} * Erprobung von Verfahren zur elektronischen Lieferung von Dokumenten \hspace*{2mm} * Elektronische Projektorganisation \noindent Das Vorhaben zielt ab auf die Schaffung einer informationstechnischen Infrastruktur für Datenbank-Retrieval, E-mail, ``Electronic Conferencing'' und fachspezifische Informationsnetze in exemplarischer Form für Wissenschaft und Industrie - auch für andere Fachgebiete.

Description: \begin{footnotesize} \noindent Combining electronic specialized information, such as electronic information retrieval from central databases, with the new means of communication opens up new perspectives for mathematics in Germany. Based on the current Fachinformationsprojekt (Specialized Information Project) run by the Deutsche Mathematiker-Vereinigung (DMV) and supported by the Federal Minister for Research and Technology (BMFT), the DMV is planning a new infrastructure activity for mathematics. This activity will not only include mathematical university departments and research institutes, but also partners from mathematical research laboratories in industry as well as suppliers of mathematical information, in particular, scientific publishing houses, the Technical Information Library (TIB) Hannover, university libraries and -- last but not least -- the Fachinformationszentrum (FIZ) Karlsruhe with the Zentralblatt für Mathematik. \noindent On the technical basis of the Internet and its worldwide information services (Gopher, WAIS, World Wide Web, Hyper-G, ftp and e-mail), a distributed mathematical information system is to be created, whose partners make their local resources available both to other partners and to the worldwide Internet community. These aims can be achieved by means of the consequent use of software that is structured according to the client-server model and distributed and accepted within the Internet. \noindent Providing the technical equipment, however, is by far not enough. Without the creation of a personal, technical and organizational infrastructure, realization of such a project will not be possible. For every partner the realization of the following measures is envisaged:\\[-7mm] \noindent \end{footnotesize} \begin{small} \begin{itemize} \item[*] Establishing an Information Coordinator\/ at every participating institution\\[-8mm] \item[*] Creation of a Forum for Mathematical Information\/\\[-8mm] \item[*] Installation and maintenance of Mathematical Information Stations\/\\[-8mm] \item[*] Participation in national and international Standardization Activities\/\\[-8mm] \item[*] Regular workshops and training courses, public relations\\[-7mm] \end{itemize} \noindent The following activities (carried out by all partners or within pilot projects by special groups) focusing on mathematical and mathematics-related information are planned:\\[-7mm] \noindent \begin{itemize} \item[*] Set up of Electronic Information Systems\/ by all partners \\[-8mm] \item[*] Distributed\/ electronic offer of Preprints\/ and scripts (full texts) by all partners\\[-8mm] \item[*] Distributed\/ electronic offer of Software and Data Collections\/ by all partners\\[-8mm] \item[*] Access to Global Information Systems in Mathematics\/\\[-8mm] \item[*] Organization of a Living Museum of Mathematics\/\\[-8mm] \item[*] Access to {\it Electronic Library Catalogs,}\/ esp.~to libraries of university departments\\[-8mm] \item[*] Electronic offer of Scanned Historical Books and Documents\/\\[-8mm] \item[*] Creation and management of Electronic Mathematical Journals\/\\[-8mm] \item[*] Creation of a framework for various kinds of Electronic Reviewing\/\\[-8mm] \item[*] Testing of new methods for Electronic Document Delivery\/\\[-8mm] \item[*] Electronic Project Organization\/\\[-7mm] \end{itemize} \noindent \end{small} \begin{footnotesize} The project aims, at its beginning, at the creation of an information infrastructure for database retrieval, e-mail, electronic conferencing and subject-specific information networks. Its focus is on mathematics in Germany. The general scope, however, is broader. The project is open for discussion, coordination, and cooperation with partners in other areas of science, industry or in other countries. It is also hoped that this project may form an example along which other models of electronic information and communication can be developed. Moreover, the project is also meant to enhance the offer from German mathematics to the worldwide "give and take" within the Internet community. \end{footnotesize}

Description: Manufacturing is a topic that provides rich opportunities for important mathematical contributions to real-world problems. The purpose of this paper is to show, by means of several examples, where and how mathematical problems of a discrete nature arise in manufacturing and to demonstrate the savings and improvements that can be achieved by employing the techniques of combinatorial optimization. The topics covered range from the design phase of a product (e. g.,routing, placement and via minimization in VLSI design), the control of CNC machines (e. g., drilling and plotting), to the management of assembly lines, storage systems and whole factories. We also point out difficulties in the modelling of complex situations and outline the algorithmic methods that are used for the solution of the mathematical problems arising in manufacturing. {\bf Key words:} discrete mathematics , combinatorial optimization, applications to manufacturing.

Description: Large scale combustion simulations show the need for adaptive methods. First, to save computation time and mainly to resolve local and instationary phenomena. In contrast to the widespread method of lines, we look at the reaction- diffusion equations as an abstract Cauchy problem in an appropriate Hilbert space. This means, we first discretize in time, assuming the space problems solved up to a prescribed tolerance. So, we are able to control the space and time error separately in an adaptive approach. The time discretization is done by several adaptive Runge-Kutta methods whereas for the space discretization a finite element method is used. The different behaviour of the proposed approaches are demonstrated on many fundamental examples from ecology, flame propagation, electrodynamics and combustion theory. {\bf Keywords:} initial boundary value problem, Rothe- method, adaptive Runge-Kutta method, finite elements, mesh refinement. {\bf AMS CLASSIFICATION:} 65J15, 65M30, 65M50.

Description: In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.

Description: Let $G=(V,E)$ be a graph and $T\subseteq V$ be a node set. We call an edge set $S$ a Steiner tree with respect to $T$ if $S$ connects all pairs of nodes in $T$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph $G=(V,E)$ with edge weights $w_e$, edge capacities $c_e, e \in E,$ and node sets $T_1,\ldots,T_N$, find edge sets $S_1,\ldots,S_N$ such that each $S_k$ is a Steiner tree with respect to $T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper SC 92-09.

Description: The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about $NP$-hardness and the existence of $\varepsilon$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design.

Description: Dieses Paper enthält die ersten beiden Teile einer geplanten Serie von Aufsätzen über die $CPLEX^2$-Implementierung des Simplex- Verfahrens. Der erste Teil ist eine Einführung: er liefert eine kurze Beschreibung des Verfahrens für Probleme mit beschränkten Variablen, zusammen mit einer relativ ausführlichen Diskussion der numerischen Eigenschaften der Netlib-Probleme. Diese Probleme bilden auch das Fundament der rechnerischen Untersuchungen in den folgenden Teilen. Der zweite Teil enthält die Hauptergebnisse dieses Papers, eine Beschreibung der Methode, die von CPLEX verwendet wird, um eine Startbasis zu konstruieren.

Description: Models for occupation dynamics in discrete quantum systems lead to large or even infinite systems of ordinary differential equations. Some new mathematical techniques, developed for the simulation of chemical processes, make a numerical solution of countable systems of ordinary differential equations possible. Both, a basic physical concept for the construction of such systems and the structure of the numerical tools for solving them are presented. These conceptual aspects are illustrated by a simulation of an occupation process from spectroscopy. In this example the structures of rotation spectra observed in infrared spectroscopy are explained and some possibilities for an extension of the model are shown.

Description: We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir

Description: In two-parameter systems two symmetry breaking bifurcation points of different types coalesce generically within one point. This causes secondary bifurcation points to exist. The aim of this paper is to understand this phenomenon with group theory and the innerconnectivity of irreducible representations of supergroup and subgroups. Colored pictures of examples are included.

Description: In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is ${\cal N}\hskip-2pt{\cal P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point $y$, a lower bound for the gap $\alpha-a^Ty$ over all alternating cycle inequalities $a^Tx\ge\alpha$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge.

Description: Gegeben sei ein Graph $G=(V,E)$ mit positiven Kantenkapazitäten $c_e$ und Knotenmengen $T_1,\ldots,T_N$. Das Steinerbaumpackungs-Problem besteht darin, Kantenmengen $S_1,\ldots,S_N$ zu finden, so da\ss\ jedes $S_k$ die Knoten aus $T_k$ verbindet und jede Kante $e$ in höchstens $c_e$ Kantenmengen aus $S_1,\ldots,S_N$ vorkommt. Eine zulässige Lösung dieses Problems nennen wir eine Steinerbaumpackung. Ist zusätzlich eine Gewichtung der Kanten gegeben und nach einer bezüglich dieser Gewichtung minimalen Steinerbaumpackung gesucht, so sprechen wir vom gewichteten Steinerbaumpackungs-Problem. Die Motivation zum Studium dieses Problems kommt aus dem Entwurf elektronischer Schaltungen. Ein dort auftretendes Teilproblem ist das sogenannte Verdrahtungsproblem, das im wesentlichen darin besteht, gegebene Punktmengen unter bestimmten Nebenbedingungen und Optimalitätskriterien auf einer Grundfläche zu verbinden. Wir studieren das Steinerbaumpackungs-Problem aus polyedrischer Sicht und definieren ein Polyeder, dessen Ecken genau den Steinerbaumpackungen entsprechen. Anschlie\ss end versuchen wir, dieses Polyeder durch gute'' beziehungsweise facetten-definierenden Ungleichungen zu beschreiben. Basierend auf diesen Ungleichungen entwickeln wir ein Schnittebenenverfahren. Die Lösung des Schnittebenenverfahrens liefert eine untere Schranke für die Optimallösung und dient als Grundlage für die Entwicklung guter Primalheuristiken. Wir haben das von uns implementierte Schnittebenenverfahren an einem Spezialfall des Verdrahtungsproblems, dem sogenannten Switchbox-Verdrahtungsproblem, getestet und vielversprechende Ergebnisse erzielt.

Description: The numerical treatment of Equivariant parameter-dependent onlinear equation systems, and even more its automation requires the intensive use of group theory. This paper illustrates the group theoretic computations which are done in the preparation of the numerical computations. The bifurcation graph which gives the bifurcation subgroups is determined from the interrelationship of the irreducible representations of a group and its subgroups. The Jacobian is transformed to block diagonal structure using a modification of the transformation which transforms to block diagonal structure with respect to a supergroup. The principle of conjugacy is used everywhere to make symbolic and numerical computations even more efficient. Finally, when the symmetry reduced problems and blocks of Jacobian matrices are evaluated numerically, the fact that the given representation is a quasi-permutation representation is exploited automatically.

Description: {\def\N{{\cal N}} \def\R{\hbox{\rm I\kern-2pt R}} \def\MN{{\rm I\kern-2pt N}} In this paper we study the following problem, which we call the weighted routing problem. Let be given a graph $G=(V,E)$ with non-negative edge weights $w_e\in\R_+$ and integer edge capacities $c_e\in\MN$ and let $\N=\{T_1,\ldots,T_N\}$, $N\ge 1$, be a list of node sets. The weighted routing problem consists in finding edge sets $S_1,\ldots,S_N$ such that, for each $k\in\{1,\ldots,N\}$, the subgraph $(V(S_k),S_k)$ contains an $[s,t]$-path for all $s,t\in T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We briefly sketch our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.}

Description: A new method for the numerical aproximation of an implicitly defined surface is presented. It is a generalization of the Euler- Gauss-Newton method for implicitly defined (one- parameter) curves to the case of (two-parameter) surfaces. The basic task in the more general case is an efficient combination of modern CAGD techniques (such as triangular Bernstein-Bzier patches and the nine parameter Hermite interpolant) and the rank deficient Gauss-Newton method.

Description: We propose an extended box method which turns out to be a variant of standard finite element methods in the case of pure diffusion and an extension of backward differencing to irregular grids if only convective transport is present. Together with the adaptive orientation proposed in a recent paper and a streamline ordering of the unknowns, this discretization leads to a highly efficient adaptive method for the approximation of internal layers in the case of large local Peclet numbers.

Description: Based on a simple stability analysis for the semi--implicit Euler discretization a new dynamic sparsing procedure is derived. This procedure automatically eliminates ``small'' elements of the Jacobian matrix. As a consequence, the amount of work needed to handle the linear algebra within a semi--implicit extrapolation integrator can be reduced drastically. Within the course of integration the sparsing criterion, which decides what ``small'' means, is dynamically adapted to ensure stability of the discretization scheme. Thus, stepsize restrictions due to instability can be avoided. Numerical experiments for quite different problems show robustness and efficiency of this dynamic sparsing technique. The techniques developed here in the context of stiff extrapolation integrators can, in principle, be applied to W--methods, where exact Jacobians may be replaced by ``sufficiently good'' approximations. {\bf Keywords:} Large scale integration, extrapolation methods, stiff ODEs, W--methods, sparse matrix techniques.

Description: In this paper we continue the investigations in [GMW92a] for the \def\sbppo{Steiner tree packing polyhedron} \sbppo. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-defining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic circuits.

Description: Subspace decompositions of finite element spaces based on $L2$-like orthogonal projections play an important role for the construction and analysis of multigrid like iterative methods. Recently several authors proved the equivalence of the associated discrete norms with the $H^1$-norm. The present report gives an elementary, self-contained derivation of this result which is based on the use of $ K$-functionals known from the theory of interpolation spaces. {\bf Keywords:} multilevel methods, nonuniform meshes, optimal convergence rates. {\bf AMS(MOS) Subject classifications:} 65N55, 65N30, 65N50.

Description: Using the perturbational-variational Rayleigh-Ritz matrix formalism, the 1/Z-expansion for the ground state of the isoelectronic $H_2$ sequence in the range of the internuclear distance $0.2\le R \le 9.0$ is calculated. Also lower bounds of the radius of convergence, based on Kato's theory of linear operators, are given. The numerical results of the 1/Z-expansion can be compared with the exact results and do not converge in the whole R-range. This behavior is in qualitative agreement with the lower bounds for the radius of convergence and enlights some still open properties of 1/Z- expansions for this sequence in the literature. {\bf PACS:} 31.15 + q; 31.20 Di; 31.20 Tz.

Description: Let $\Re$ be the set of all binary relations on a finite set $N$ and $d$ be the symmetric difference distance defined on $\Re$. For a given profile $\Pi = (R_1,...,R_m) \in R^m$, a relation $R* \in \Re $ that minimizes the function $\sum^m_{k=1} d(R_k,R) $ is called a median relation of $\Pi$. A number of problems occuring in the social sciences, in qualitative data analysis and in multicriteria decision making can be modelled as problems of finding medians of a profile of binary relations. In these contexts the profile $\Pi$ represents collected data (preferences, similarities, games) and the objective is that of finding a median relation of $\Pi$ with some special feature (representing e. g., consensus of preferences, clustering of similar objects, ranking of teams, etc.). In this paper we analyse the computational complexity of all such problems in which the median is required to satisfy one or more of the properties: reflexitivity, symmetry, antisymmetry, transitivity and completeness. We prove that whenever transitivity is required (except when symmetry and completeness are also simultaneously required) then the corresponding median problem is $NP$-hard. In some cases we prove that they remain $NP$-hard when the profile $\Pi$ has a fixed number of binary relations.

Description: MEXX (short for MEXanical systems eXtrapolation integrator) is a Fortran code for time integration of constrained mechanical systems. MEXX is suited for direct integration of the equations of motion in descriptor form. It is based on extrapolation of a time stepping method that is explicit in the differential equations and linearly implicit in the nonlinear constraints. It only requires the solution of well--structured systems of linear equations which can be solved with a computational work growing linearly with the number of bodies, in the case of multibody systems with few closed kinematic loops. Position and velocity constraints are enforced throughout the integration interval, whereas acceleration constraints need not be formulated. MEXX has options for time--continuous solution representation (useful for graphics) and for the location of events such as impacts. The present article describes MEXX and its underlying concepts.

Description: We consider the approximate solution of selfadjoint elliptic problems in three space dimensions by piecewise linear finite elements with respect to a highly non-uniform tetrahedral mesh which is generated adaptively. The arising linear systems are solved iteratively by the conjugate gradient method provided with a multilevel preconditioner. Here, the accuracy of the iterative solution is coupled with the discretization error. as the performance of hierarchical bases preconditioners deteriorate in three space dimensions, the BPX preconditioner is used, taking special care of an efficient implementation. Reliable a-posteriori estimates for the discretization error are derived from a local comparison with the approximation resulting from piecewise quadratic elements. To illustrate the theoretical results, we consider a familiar model problem involving reentrant corners and a real-life problem arising from hyperthermia, a recent clinical method for cancer therapy.

Description: A Hamiltonian system subject to smooth constraints can typically be viewed as a Hamiltonian system on a manifold. Numerical computations, however, must be performed in $ R^n$. In this paper, canonical transformations from ``Hamiltonian differential--algebraic equations'' to ODEs in Euclidean space are considered. In \S2, canonical parameterizations or local charts are developed and it is shown how these can be computed in a practical framework. In \S3 we consider the construction of unconstrained Hamiltonian ODE systems in the space in which the constraint manifold is embedded which preserve the constraint manifold as an integral invariant and whose flow reduces to the flow of the constrained system along the manifold. It is shown that certain of these unconstrained Hamiltonian systems force Lyapunov stability of the constraint--invariants, while others lead to an unstable invariant. In \S4, we compare various projection techniques which might be incorporated to better insure preservation of the constraint--invariants in the context of numerical discretization. Numerical experiments illustrate the degree to which the constraint and symplectic invariants are maintained under discretization of various formulations. {\bf Keywords:} differential--algebraic equations, Hamiltonian systems, canonical discretization schemes. {\bf AMS(MOS):} subject classification 65L05.

Description: In this paper, two classes of second order accurate high resolution schemes are presented on regular triangular meshes for initial value problem of two dimensional conservation laws. The first class are called Runge-Kutta-FVM MmB (locally Maximum- minimum Bounds preserving) schemes, which are first discretized by (FVM) finite volume method in space direction and modifying numerical fluxes, and then by Runge-Kutta methods in time direction; The second class, constructed by Taylor expansion in time, and then by FVM methods and making modifications to fluxes, are called Taylor- FVM MmB schemes. MmB properties of both schemes are proved for 2-D scalar conservation law. Numerical results are given for Riemann problems of 2-D scalar conservation law and 2-D gas dynamics systems and some comparisons are made between the two classes of the schemes. Key words and phrases: MmB schemes, 2-D, conservation laws, gas dynamics systems, Runge-Kutta-FVM, Taylor-FVM.