Library

Description: We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.

Description: Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.

Description: The latest machine generation installed at supercomputer centres in Germany offers a peak performance in the tens of Tflop/s range. We study performance and scaling of our quantum chromodynamics simulation programme BQCD that we obtained on two of these machines, an IBM Blue Gene/L and an SGI Altix 4700. We compare the performance of Fortran/MPI code with assembler code. The latter allows to exploit concurrency at more levels, in particular in overlapping communication and computation as well as prefetching data from main memory.

Description: We study the optimal control of a maximum-norm objective functional subject to an elliptic-type PDE and pointwise state constraints. The problem is transformed into a problem where the non-differentiable L^{\infty}-norm in the functional will be replaced by a scalar variable and additional state constraints. This problem is solved by barrier methods. We will show the existence and convergence of the central path for a class of barrier functions. Numerical experiments complete the presentation.

Description: Der Artikel gibt einen Einblick in das reiche Feld der Zusammenarbeit zwischen Mathematik und Medizin. Beispielhaft werden drei Erfolgsmodelle dargestellt: Medizinische Bildgebung, mathematische Modellierung und Biosignalverarbeitung im Bereich der Dynamik des Herzens sowie mathematische Modellierung und Simulation in der Krebstherapie Hyperthermie und der Mund-Kiefer-Gesichts-Chirurgie. In allen Fällen existiert ein Gleichklang der Interessen von Medizin und Mathematik: Beide Disziplinen wollen die Resultate schnell und zuverlässig. Für die Klinik heißt das, dass notwendige Rechnungen in möglichst kurzer Zeit, und zwar auf dem PC, ablaufen müssen und dass die Resultate so genau und belastbar sein müssen, dass medizinische Entscheidungen darauf aufbauen können. Für die Mathematik folgt daraus, dass höchste Anforderungen an die Effizienz der verwendeten Algorithmen und die darauf aufbauende Software in Numerik und Visualisierung zu stellen sind. Jedes Kapitel endet mit einer Darstellung der Perspektive des jeweiligen Gebietes. Abschließend werden mögliche Handlungsoptionen für Politik und Wirtschaft diskutiert.

Description: This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.

Description: Mit dem Informationsdienst Math&Industry soll ein Prototyp eines dezentralen Informationssystems für Förderprogramme und Forschungsprojekte geschaffen werden, das sich auf andere Programme (bezüglich angewandter Mathematik, aber auch darüber hinaus) übertragen lässt. Das betrifft sowohl die Konzeption (Strukturierung der Informationen) als auch die Werkzeuge, die anderen BMBF-Förderprogrammen zur Verfügung gestellt werden können. Damit sollen diese in die Lage versetzt werden, die in Math&Industry entwickelten Konzepte und Werkzeuge an ihre spezifischen Bedürfnisse anzupassen.

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

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

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

Description: Die Business Unit PC in Augsburg ist die zentrale Produktionsstätte der Siemens--Nixdorf Informationssysteme (SNI) AG für Personal Computer sowie für einige Periphärgeräte. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es für ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engpässe im Produktionsbetrieb darstellen. Das Management suchte nach Möglichkeiten, den Produktionsfluß zu verbessern, ohne teure technische Änderungen am System vornehmen zu müssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums für Informationstechnik (die ehemals an der Universität Augsburg ansässig war) analysierte, unterstützt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ansätze, die hier dargestellt werden sollen, sind teilweise schon in Grötschel [Grö92] angesprochen worden.

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

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

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

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

Description: Orthogonal polynomials %like the Chebyshev polynomials can be calculated by computation of determinants, by the use of generating functions, in terms of Rodrigues formulas, by iterating recurrence equations, calculating the polynomial solutions of differential equations, through closed form representations and by other means. In this article, we give an overview about the efficiency of the above methods in Maple, Mathematica, and REDUCE. As a noncommercial package we include the MuPAD system.

Description: Many physical systems exhibit rapid motion coupled to a slowly varying motion. Often the rapid motion is associated with a stiff contribution in the potential energy function. In this context, the situation typically considered in the literature is the one with a strictly convex potential. Under some technical assumptions, one can then show that the slow motion is reproduced by a properly constrained system. In this paper we are concerned with a different situation: Often different time-scales can be found because of many local minima and barrier crossing between these minima. We suggest here to replace the detailed motion in the minima and the local barrier crossings by a statistical model which is then coupled to the slow equations of motion over long periods of time. This leads to Langevin type equations of motion subject to an appropriate time transformation.

Description: This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.

Description: This paper presents an explicit and symplectic integrator called PICKABACK for quantum-classical molecular dynamics. This integration scheme is time reversible and unitary in the quantum part. We use the Lie formalism in order to construct a formal evolution operator which then is split using the Strang splitting yielding the symplectic discretization PICHABACK. Finally the new method is compared with a hybrid method in application to two examples: a collinear collision with a quantum oscillator and additionally a photodissociation process of a collinear ArHCI-molecule.

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

Description: Based on the concept of free energy, we give a Hamiltonian formulation for the torsion dynamics of macromolecules. The appropriate reaction coordinates for the free energy calculations are defined in terms of soft constraints as introduced in Brooks, B.R., Zhou, J., and Reich, S., Elastic molecular dynamics with flexible constraints, in preparation and Reich, S., Smoothed Dynamics of Highly Oscillatory Hamiltonian Systems, Physica D, to appear, 1995. We consider a few simplifications that allow one to calculate the free energy analytically and to write the corresponding equations of motion as a constrained Hamiltonian system. We also discuss a possible stochastic embedding of the reduced dynamics by means of a generalized Langevin approach.

Description: Integer stochastic linear programming is considered from the viewpoint of discontinuous optimization. After reviewing solution approaches via mollifier subgradients and decomposition we outline how to base a solution method on efficient pointwise calculation of the objective employing computer algebra.

Description: A set of adaptive algorithms for quadrature on multi-dimensional polyhedral domains is presented. Several kinds of refinement are discussed, covering local improvement of quadrature order and splitting the domain into sub-domains, resulting in isotropic, graded or anisotropic grids. The algorithms are pure local heuristics using no a priori knowledge or tuning parameters. This approach was motivated by results from finite element theory for optimal approximation results. Numerical experiments show the optimality of pure local greedy-like algorithms for singularity-type functions typically occurring in finite element computations.

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

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

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

Description: Durch extrem steigende Preise für traditionelle wissenschaftliche Zeitschriften bei gleichzeitiger Stagnation der Bibliotheksetats an den Hochschulen und bei weltweit weiterhin anwachsenden Forschungsleistungen ist die adäquate Versorgung der Wissenschaften mit relevanter Literatur gefährdet. Dokumentenliefersysteme werden vielerorts als Lösung dieser ``Bibliothekskrise'' propagiert. Dieser Weg ist für den derzeitigen Literaturversorgungsmarkt sinnvoll, aber er bietet keine langfristig stabile Lösung. Wenn die Grundversorgung der Bibliotheken weiter schrumpft, wird Dokumentenlieferung in der zur Zeit üblichen bzw. geplanten Form die Kosten nur noch zusätzlich in die Höhe treiben. Wir plädieren in diesem Aufsatz für einen grundsätzlich neuen Ansatz. Wir sind der Meinung, da\ss{} einzig der Übergang auf elektronische Medien eine bezahlbare, umfassende und benutzerfreundliche Versorgung der Wissenschaftler mit Literatur sichern kann. Wir zeigen -- unter anderem anhand elektronischer Zeitschriften -- wie zum Beispiel durch Kooperation von Bibliotheken mit Fachbereichen und wissenschaftlichen Gesellschaften neue Wege der Informationsversorgung beschritten werden können. Dieser Vorschlag einer neuen Organisation des wissenschaftlichen Publikationswesen erfordert Umdenken in vielen Bereichen. Neue Organisationsformen sind erforderlich, Rechte müssen anders verteilt, Aufgaben auf andere Schultern geladen werden. Die Bibliotheken werden besonders betroffen sein. Aber für sie ist die konsequente Nutzung der sich rasch ausbreitenden Informationstechnik (darunter verstehen wir u. a. globale elektronische Netze, leistungsfähige Rechner, kostengünstige Speichermedien, benutzerfreundliche Such- und Retrieval-Systeme, Entwicklung weltweit akzeptierter Datenformate) eine wirkliche und möglicherweise die einzige Chance, ihrem Auftrag zur umfassenden Versorgung der Wissenschaften mit Literatur zu gesamtwirtschaftlich niedrigen Kosten weiterhin nachzukommen. Au\ss{}erdem bietet die Bereitstellung und Archivierung wissenschaftlicher Literatur auf elektronischem Wege bedeutende Vorteile gegenüber der traditionellen Dokumentation auf Papier, die im übrigen, falls erwünscht, weiterhin betrieben werden kann.

Description: Seit 1991 verfolgt die Berliner Wissenschaft verstärkt das Ziel, ihre Einrichtungen untereinander breitbandig mit Transferraten oberhalb von 34 Mb/s in Glasfasertechnik zu vernetzen. Im ersten Halbjahr 1995 ist es gelungen, die erste Stufe des Berliner Breitbandnetzes für die Wissenschaft ({\it Berlin Research Area Information Network - BRAIN}) aufzubauen. Dieser Bericht beschreibt die verschiedenen Phasen der Vernetzung der Wissenschaftseinrichtungen Berlins von den Anfängen im Jahre 1975 über die Planungen zum Breitbandnetz ab 1991 und die Realisierungsschritte durch die erfolgreiche Zusammenarbeit mit dem Landesamt für Informationstechnik Berlin (LIT) insbesondere bei der Verwendung von Glasfaserleitungen des Landes. Weiterhin werden der Aufbau des Berlin Regional Testbed in seiner Realisierung einschliesslich seiner Anwendungsprojekte mit Stand Juni 1995 und sodann die Pläne der Berliner Wissenschaftseinrichtungen für die zukünftige breitbandige Vernetzung einer Vielzahl von Standorten als allumfassendes Berlin Research Area Information Network dargestellt.

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

Description: Die vorliegende Arbeit ist die (z.T.~wesentlich) erweiterte Fassung eines Vortrages auf dem Deutschen Dokumentartag im September 1995 an der Fachhochschule Potsdam. Unser Ziel ist eine Bestandsaufnahme der gegenwärtigen Entwicklungen auf dem Gebiet der elektronischen Information und Kommunikation. Wir diskutieren Chancen und Risiken, beleuchten gesellschaftliche Rahmenbedingungen - vor allem im Vergleich mit den Vereinigten Staaten von Amerika - und skizzieren Aufgaben im Bereich von Forschung, Staat und Wirtschaft, die unserer Meinung nach noch zu bewältigen sind. Wir führen insbesondere in Gebiete ein, die vermutlich in naher Zukunft die Landschaft des Dokumentierens und Archivierens wesentlich verändern werden. Wir benutzen dabei häufig Beispiele und Modellvorstellungen aus der Mathematik, unserem eigenen Fachgebiet, die u.a. zeigen, wie Elemente des Informierens, Dokumentierens und Archivierens durch die neuen Technologien der elektronischen Datenverarbeitung und Kommunikation ineinander flie\"sen. Mehr Leistung kann mit geringeren Kosten erzielt werden. Wir schliessen mit einer Auflistung von neuen Perspektiven und Möglichkeiten zum Handeln in diesem Bereich.

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

Description: {\begin{footnotesize} Dieser Artikel beschreibt die ersten Schritte auf dem Wege zu einem Verteilten Informationssystem für die Mathematik, das von der ``Deutschen Mathematiker-Vereinigung'' (DMV) vorbereitet wird. Die Darstellung erfolgt aus zwei unterschiedlichen Perspektiven. Der erste Teil soll vor allem Lesern, die an der Motivation des Vorhabens und den organisatorischen Rahmenbedingungen interessiert sind, einen Zugang zu den zugrundeliegenden technischen Ideen bieten. Er skizziert zunächst die wissenschaftliche Zielsetzung des geplanten Vorhabens. Dann diskutiert er das Verteilte Informationssystem als Kombination aus einem elektronischen Nachrichtensystem (auf der Basis von E-mail), einem globalen Hypertextsystem (das die Informationsangebote der Partner des Projekts miteinander vernetzt) und einer verteilten, objektorientierten Datenbank (mit Interfaces zu den bereits genannten Komponenten). Dieser Teil schliesst mit einer knappen Betrachtung der Verhältnisse (auch der Chancen, Kosten einzusparen), die beim Übergang von traditionellen zu elektronischen Publikationsformen zu erwarten sind. Er führt insbesondere neue Möglichkeiten an, das geplante System auch für Zwecke des ``Zentralblatt für Mathematik'' einzusetzen. Der zweite Teil richtet sich an den eher technisch interessierten Leser. Er diskutiert einen ersten Vorschlag zur Strukturierung der bei den Partnern verteilt vorliegenden Informationsangebote -- vorwiegend aus Nutzersicht, d.h. möglichst unabhängig von den Idiosynkrasien der heute im Internet gegebenen Informationssysteme. Er enthält die technischen Kerngedanken zur Realisierung einer homogenen Informationsinfrastruktur bei den Partnern, die ein verteiltes und gleichzeitig hierachisches Retrieval in den Informationsangeboten der Mathematik in Deutschland ermöglichen soll. Dieser Teil benennt erste Chancen zur Implementierung innerhalb der Hyper-G- und, als Fernziel, auch der WWW-Welt. Er zeigt aber, neben den neuen Möglichkeiten, auch Risiken und Grenzen der Machbarkeit mit heutigen Mitteln auf. Die gesamte Darstellung orientiert sich an den Inhalten der bereits an anderer Stelle ausführlich vorgestellten Teilaufgaben und Teilprojekte und leitet daraus sowohl die vorgeschlagene Informationsstruktur als auch die technischen Mittel ab. Die wissenschaftlichen Inhalte und organisatorischen Ziele des Verteilten Informationssystems wurden in einer breiten (auch elektronisch geführten) Diskussion im Kreise der potentiellen Partner des Projekts ermittelt, insbesondere der Fachinformationsbeauftragten der Mathematik. Eine Anlage stellt eine vergleichende Betrachtung der Kosten auf, die einem mathematischen Fachbereich oder Forschungsinstitut bei der Weitergabe seiner wissenschaftlichen Reports auf Papier bzw. auf elektronischem Wege entstehen. \end{footnotesize}}

Description: Die Arbeit beschreibt Konzept, Struktur und Ausstattung des ZIB. Übergeordnetes Ziel des ZIB ist die Beschleunigung des {\it Know-how Transfers} aus der mathematischen Grundlagenforschung über die Entwicklung von Algorithmen und Software bis hin zur tatsächlichen Nutzung in der Industrie. In der Tat ist Computational Mathematics inzwischen zu einer der wichtigsten {\it Schlüsseltechnologien} geworden, die nicht zuletzt im Zusammenhang mit der Standort-Diskussion eine wichtige Rolle spielt und vermehrt spielen wird. Dazu müssen Methodenentwicklung und Rechenzentrum auf höchstem Niveau sowie interdisziplinäre Forschung möglichst vereint in einer Institution mit enger Anbindung an ein universitäres Umfeld realisiert sein. Das Konrad-Zuse-Zentrum hat die wesentlichen Voraussetzungen als SC Zentrum bereits geschaffen; ein Ausbau zum HPSC Zentrum wäre eine natürliche Entwicklung - falls die Politik diese Chance rechtzeitig begreift!

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

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

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

Description: Recently, Todorov and Wilf independently realized that de Branges' original proof of the Bieberbach and Milin conjectures and the proof that was later given by Weinstein deal with the same special function system that de Branges had introduced in his work. In this article, we present an elementary proof of this statement based on the defining differential equations system rather than the closed representation of de Branges' function system. Our proof does neither use special functions (like Wilf's) nor the residue theorem (like Todorov's) nor the closed representation (like both), but is purely algebraic. On the other hand, by a similar algebraic treatment, the closed representation of de Branges' function system is derived. Our whole contribution can be looked at as the study of properties of the Koebe function. Therefore, in a very elementary manner it is shown that the known proofs of the Bieberbach and Milin conjectures can be understood as a consequence of the Löwner differential equation, plus properties of the Koebe function.

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

Description: Dynamical simulation of industrially relevant processes strongly advises the use of algorithms, which are {\em adaptive} both in time and in space discretization. The paper presents two alternatives: (a) a fully adaptive method of lines approach, which is based on finite difference methods and essentially applicable to 1D problems; (b) a fully adaptive Rothe method, which is based on a fast multilevel finite element method and applicable to 1D up to 3D.

Description: A theoretical investigation of the dynamic properties of integrated optical Er--doped waveguide lasers is presented. It includes the construction of a physical model and of numerical techniques which allow reliable simulations of the dynamical behaviour of the laser signal depending on essential parameters of the laser device and on its external, time--dependent pump radiation. Therefore, a physical theory is developed which describes the propagation of light and its interaction with the active substrate in the laser cavity. This is realized in two steps. First, a {\em fundamental model} based on Maxwell's equations and on rate equations for the transitions in the active medium is constructed. Since this turns out to prohibit reliable simulations, it is, in a second step, reformulated via averaging in time and space which suppresses the fluctuations on the fastest time scales but represents them correctly. For this {\em reduced model} reliable and efficient simulation techniques using adaptive control schemes are designed and implemented. We apply the linear--implicit Euler discretization with extrapolation in time and a multilevel quadrature scheme in space. Finally, the model is justified in comparison with experimental observations in four cases of technological relevance.

Description: The paper analyzes a splitting technique into fast and slow dynamical components of ODE systems as suggested by {\sc Maas and Pope} recently. Their technique is based on a real block -- Schur decomposition of the Jacobian of the right hand side of the ODE. As a result of the analysis, a computationally cheap monitor for the possible necessary recovering of the splitting is derived by singular perturbation theory. Numerical experiments on moderate size, but challenging reaction kinetics problems document the efficiency of the new device within a linearly-implicit stiff integrator.

Description: In the introduction an approach to solving differential equations is motivated in which non-linear DEs are not attacked directly but properties like infinitesimal symmetries or the existence of an equivalent variational principle are investigated. In the course of such investigations overdetermined PDE-systems are generated which are to be solved (where the term `overdetermined' just stands for `more conditions than free functions'). In section 2.\ algorithms for simplifying and solving overdetermined PDE systems are given together with examples. References for more details of the corresponding program {\tt CRACK}, written by A.\ Brand and the author, are given. In sections 3.-05.\ applications of the program {\tt CRACK} are discussed. The first application is the investigation of symmetries of space-time metrics by solving Killing equations for Killing vectors and Killing tensors and their integrability conditions. A program {\tt CLASSYM} that formulates these equations, written by G.\ Grebot, is briefly described. In section 4.\ an example of the original application of {\tt CRACK} is discussed which is the determination of symmetries of a PDE system. The problem is to find the symmetries of an unusual unified field theory of gravitational and hadronic interactions. The application of symmetries with a program {\tt APPLYSYM} is the content of section 5.\ where an ODE, resulting from an attempt to generalize Weyl's class of solutions of Einsteins field equations, is solved. The final section is devoted to future work on, first, making a general PDE-solver more flexible and effective, and secondly, on applying it to more advanced applications. This section contains so far unpublished work. An example requiring the extension of {\tt CRACK} to deal with non-polynomial non-linearities results from an investigation of interior solutions of Einstein's field equations for a spherically symmetric perfect fluid in shear-free motion by H.\ Stephani. A possible future application of {\tt CRACK} is the determination of Killing tensors of higher rank. In the last sub-section an algorithm for formulating corresponding integrability conditions has been sketched. The maximal number of Killing tensors of rank $r$ in a $n$-dimensional Riemannian space has been found to be $\frac{1}{r+1}\left( ^{n + r - 1}_{\;\;\;\;\,r} \right) \left( ^{ n+r}_{\;\;\,r} \right)$.

Description: This paper presents a mathematical derivation of a model for quantum-classical molecular dynamics (QCMD) as a {\em partial} classical limit of the full Schrödinger equation. This limit is achieved in two steps: separation of the full wavefunction and short wave asymptotics for its ``classical'' part. Both steps can be rigorously justified under certain smallness assumptions. Moreover, the results imply that neither the time-dependent self-consistent field method nor mixed quantum-semi-classical models lead to better approximations than QCMD since they depend on the separation step, too. On the other hand, the theory leads to a characterization of the critical situations in which the models are in danger of largely deviating from the solution of the full Schrödinger equation. These critical situations are exemplified in an illustrative numerical simulation: the collinear collision of an Argon atom with a harmonic quantum oscillator.

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

Description: The interaction potential of molecular systems which are typically used in molecular dynamics can be split into two parts of essentially different stiffness. The strong part of the potential forces the solution of the equations of motion to oscillate on a very small time scale. There is a strong need for eliminating the smallest time scales because they are a severe restriction for numerical long-term simulations of macromolecules. This leads to the idea of just freezing the high frequency degrees of freedom (bond stretching and bond angles). However, the naive way of doing this via holonomic constraints is bound to produce incorrect results. The paper presents a mathematically rigorous discussion of the limit situation in which the stiffness of the strong part of the potential is increased to infinity. It is demonstrated that the average of the limit solution indeed obeys a constrained Hamiltonian system but with a {\em corrected soft potential}. An explicit formula for the additive potential correction is given and its significant contribution is demonstrated in an illustrative example. It appears that this correcting potential is definitely not identical with the Fixman-potential as was repeatedly assumed in the literature.

Description: We consider a single server system consisting of $n$ queues with different types of customers (Poisson streams) and $k$ permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). The stability condition and a pseudo work conservation law will be given for arbitrary service time distributions; for exponential service times a pseudo conservation law for the mean sojourn times can be derived. In case of two queues and exponential service times, the generating function of the stationary distribution satisfies a functional equation being a Riemann-Hilbert problem which can be reduced to a Dirichlet problem for a circle. The solution yields the mean sojourn times as an elliptic integral, which can be computed numerically very efficiently. In case $n\ge 2$ a numerical algorithm for computing the performance measures is presented, which is efficient for $n=2,3$. Since for $n\ge 4$ an exact analytical or/and numerical treatment is too complex a heuristic approximation for the mean sojourn times of the different types of customers is given, which in case of a (complete) symmetric system is exact. The numerical and simulation results show that, over a wide range of parameters, the approximation works well.

Description: The paper studies Hamiltonian systems with a strong potential forcing the solutions to oscillate on a very small time scale. In particular, we are interested in the limit situation where the size $\epsilon$ of this small time scale tends to zero but the velocity components remain oscillating with an amplitude variation of order ${\rm O}(1)$. The process of establishing an effective initial value problem for the limit positions will be called {\em homogenization} of the Hamiltonian system. This problem occurs in mechanics as the problem of realization of holonomic constraints, in plasma physics as the problem of guiding center motion, in the simulation of biomolecules as the so called smoothing problem. We suggest the systematic use of the notion of {\em weak convergence} in order to approach this problem. This methodology helps to establish unified and short proofs of the known results which throw light on the inherent structure of the problem. Moreover, we give a careful and critical review of the literature.

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

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

Description: The $h$-$p$-version of finite-elements delivers a sub-exponential convergence in the energy norm. A step towards a full adaptive implementation is taken in the context of unstructured meshes of simplices with variable order $p$ in space. Both assumptions lead to desirable properties of shape functions like symmetry, $p$-hierarchy and simple coupling of elements. In a first step it is demonstrated that for standard polynomial vector spaces on simplices not all of these features can be obtained simultaneously. However, this is possible if these spaces are slightly extended or reduced. Thus a new class of polynomial shape functions is derived, which are especially well suited for three dimensional tetrahedra. The construction is completed by directly minimizing the condition numbers of the arising preconditioned local finite element matrices. The preconditioner is based on two-step domain decomposition techniques using a multigrid solver for the global linear problem $p=1$ and direct solvers for local higher order problems. Some numerical results concerning an adaptive (feedback) version of $h$-$p$ finite elements are presented.

Description: In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the integer expected recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest possible improvements to economize on the number of function evaluations needed.

Description: The paper describes a fast algorithm for the discrete periodic wavelet transform and its inverse without using the scaling function. The approach permits to compute the decomposition of a function into a lacunary wavelet basis, i.e. a basis constituted of a subset of all basis functions up to a certain scale, without modification. The construction is then extended to operator--adapted biorthogonal wavelets. This is relevant for the solution of non--linear evolutionary PDEs where a priori information about the significant coefficients is available. We pursue the approach described in FrSc94 which is based on the explicit computation of the scalewise contributions of the approximated function to the values at points of hierarchical grids. Here, we present an improved construction employing the cardinal function of the multiresolution. The new method is applied to the Helmholtz equation and illustrated by comparative numerical results. It is then extended for the solution of a nonlinear parabolic PDE with semi--implicit discretization in time and self--adaptive wavelet discretization in space. Results with full adaptivity of the spatial wavelet discretization are presented for a one--dimensional flame front as well as for a two--dimensional problem.

Description: In this paper a unified approach to central and decentral approximations of the distribution function $F(x,n)$ of the sum of $n$ iid random variables with compact support in $I\!\!R_+$ is given. This approach yields direct Edgeworth expansion (especially the Central limit theorem) and indirect Edgeworth expansion (Theorem of Bahadur-Rao, large deviation results) within a unified framework. An approximative inversion of the LST of $F(x,n)$ (approximation of the complex inversion integral over a line by an integral over a proper bounded arc with a proper integrand) allows to get these approximations and moreover explicit error bounds.

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

Description: Im Rahmen des EDV-gestützten Systems zur {\bf{}BE}t{\bf{}R}iebseinsa{\bf{}T}zplanung und -{\bf{}A}uswertung (BERTA) der Berliner Verkehrsbetriebe (BVG) wird ein Modul zur Wagenumlaufoptimierung realisiert. In diesem Aufsatz berichten wir über die betrieblichen Anforderungen und Nebenbedingungen an eine mathematische Optimierung und erläutern unsere Konzepte zur Realisierung eines exakten mathematischen Verfahrens.

Description: The results of analyzing experimental data using a parametric model may heavily depend on the chosen model. With this paper we describe computational tools in Splus for the adequate selection of nonlinear regression models if the intended use of the model is among the following: 1. estimation of the unknown regression function, 2. prediction of future values of the response variable, 3. calibration or 4. estimation of some parameter with a certain meaning in the corresponding field of application. Moreover, we provide programs for variance modelling and for selecting an appropriate nonlinear transformation of the observations which may lead to an improved accuracy. We describe how the accuracy of the parameter estimators is assessed by a "moment oriented bootstrap procedure". This procedure is also used for the construction of confidence, prediction and calibration intervals. The use of our tools is illustrated by an example. Help files are given in an appendix.

Description: We establish a verifiable sufficient condition for strong convexity of the expected recourse as a function of the tender variable in a two-stage stochastic program with linear recourse. Generalizing a former result where all components of the second-stage right-hand side vector were random we treat the case where only a subvector of the right-hand side is random. As prerequisite, a refined analysis of the polyhedral complex of lineality regions of the second-stage value function is carried out. The sufficient condition for strong convexity allows to widen the class of recourse models for which certain quantitative results on stability and asymptotic convergence of optimal solutions are valid.

Description: A fully adaptive method is presented for the numerical solution of highly nonlinear, coupled systems of parabolic differential equations in one space dimension. Time discretization is by means of the linearly--implicit Euler discretization. Space discretization is by finite differences on non--uniform grids. Both basic discretizations are combined with extrapolation. Based on local error estimates for both the time and the space discretization error, the accuracy of the numerical approximation is controlled and the discretization stepsizes are adapted automatically and simultaneously. The algorithm is implemented in a user friendly software package, PDEX1M. To be a powerful tool for users coming from applications the package has been equipped with some additional useful devices.

Description: We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.

Description: We present computational experiments for solving quadratic $(0,1)$ problems. Our approach combines a semidefinite relaxation with a cutting plane technique, and is applied in a Branch and Bound setting. Our experiments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 binary variables, in a routine manner.

Description: We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0-1 variables represent different paths. An associated integral polytope is studied and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported.

Description: The results of analyzing experimental data using a parametric model may heavily depend on the chosen model. In this paper we propose procedures for the adequate selection of nonlinear regression models if the intended use of the model is among the following: 1. prediction of future values of the response variable, 2. estimation of the unknown regression function, 3. calibration or 4. estimation of some parameter with a certain meaning in the corresponding field of application. Moreover, we propose procedures for variance modelling and for selecting an appropriate nonlinear transformation of the observations which may lead to an improved accuracy. We show how to assess the accuracy of the parameter estimators by a "moment oriented bootstrap procedure". This procedure may also be used for the construction of confidence, prediction and calibration intervals. Programs written in Splus which realize our strategy for nonlinear regression modelling and parameter estimation are described as well. The performance of the selected model is discussed, and the behaviour of the procedures is illustrated by examples.

Description: ``Das System ist zerbrochen!'', so lautet das Urteil von Keith Dennis, Professor an der Cornell University und neuer Verantwortlicher für die Mathematical Reviews, über das traditionelle Publikationswesen in der Mathematik. Was sind die Ursachen? Hauptsächlich sind es das starke Wachstum der mathematischen Literatur, die langen Verzögerungen von der Erstellung bis zum Erscheinen einer Arbeit, die hohen Ablehnungsraten bei mathematischen Journalen aufgrund beschränkter Seitenzahlen (und nicht wegen mangelnder Qualität) sowie drastisch steigende Preise für Zeitschriften und Bücher bei gleichzeitiger Reduktion der Bibliotheksetats.

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

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

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

Description: A family of secant methods based on general rank-1 updates has been revisited in view of the construction of iterative solvers for large non- Hermitian linear systems. As it turns out, both Broydens "good" and "bad" update techniques play a special role - but should be associated with two different line search principles. For Broydens "bad" update technique, a minimum residual principle is natural - thus making it theorectically comparable with a series of well-known algorithms like GMRES. Broydens "good" update technique, however, is shown to be naturally linked with a minimum "next correction" principle - which asymptotically mimics a minimum error principle. The two minimization principles differ significantly for sufficiently large system dimension. Numerical experiments on discretized PDE's of convection diffusion type in 2-D with internal layers give a first impression of the possible power of the derived "good" Broyden variant. {\bf Key Words:} nonsymmetric linear system, secant method, rank-1 update, Broydens method, line search, GMRES. AMS(MOS) {\bf Subject Classifications:} 65F10, 65N20.

Description: A new adaptive multilevel approach for parabolic PDE's is presented. Full adaptivity of the algorithm is realized by combining multilevel time discretization, better known as extrapolation methods, and multilevel finite element space discretization. In the theoretical part of the paper the existence of asymptotic expansions in terms of time-steps for single-step methods in Hilbert space is established. Finite element approximation then leads to perturbed expansions, whose perturbations, however, can be pushed below a necessary level by means of an adaptive grid control. The theoretical presentation is independent of space dimension. In this part I of the paper details of the algorithm and numerical examples are given for the 1D case only. The numerical results clearly show the significant perspectives opened by the new algorithmic approach.

Description: In this paper we consider symplectic difference schemes for perturbed Hamiltonian systems of integrable ones, which can cover many important problems. Symplectic difference schemes for general Hamiltonian systems can also be used to these problems. But the perturbation property has not been paid proper attention to, which is important in the method proposed here. Numerical simulation shows that, for this method the time step size can be taken quite large and the qualitative property , such as preserving invariant tori, is also better than usual symplectic difference schemes.

Description: $G$-invariant cubature formulas for numerical integration over n-dimensional, $G$- invariant integration regions are computed symbolically. The nodes are the common zeros of some $d$-orthogonal polynomials which build an $H$-basis of an ideal. Approaches for these polynomials depending on parameters are made with the help of the theory of linear representations of a group $G$. This theory is also used for the effective computation of necessary conditions which determines the parameters. Another approach uses invariant theory and gröbner bases.

Description: The FORTRAN preprocessor fpp in the newly introduced Autotasking System of CRAY Research allows automatic vectorization and parallelization on basis of a data dependence analysis. An introduction into data dependence analysis is given, showing how data dependence graphs unveil opportunities for program transformations like vectorization and concurrentization. The report contains a complete description of the preprocessors functionality, its options and directives for increasing the effectiveness of the dependence analyzer and steering the code transformations. Finally, some advice is given for the practical use of fpp on CRAY computers.

Description: Countable systems of ordinary differential equations appear frequently in chemistry, physics, biology and medicine. They can be considered as ordinary differential equations in sequence spaces. In this work, a full adaptive algorithm for the computational treatment of such systems is developed. The method combines time discretization with extrapolation in Hilbert spaces with a discrete Galerkin approach as discretization of the stationary subproblems. The Galerkin method is based on orthogonal functions of a discrete variable , which are generated by certain weight functions. A theory of countable systems in the associated weighted sequence spaces is developed as well as a theory of the Galerkin method. The Galerkin equations can be assembled either by use of analytical properties of the orthogonal functions or numerically by a multilevel summation algorithm. The resulting algorithm CODEX is applied to many examples of technological interest, in particular from polymer chemistry.

Description: Parameter-dependent systems of nonlinear equations with symmetry are treated by a combination of symbolic and numerical computations. In the symbolic part of the algorithm the complete analysis of the symmetry occurs, and it is here where symmetrical normal forms, symmetry reduced systems, and block diagonal Jacobians are computed. Given a particular problem, the symbolic algorithm can create and compute through the list of possible bifurcations thereby forming a so-called tree of decisions correlated to the different types of symmetry breaking bifurcation points. The remaining part of the algorithm deals with the numerical pathfollowing based on the implicit reparametrisation as suggested and worked out by Deuflhard/Fiedler/Kunkel. The symmetry preserving bifurcation points are computed using recently developed augmented systems incorporating the use of symmetry. {\bf Keywords:} pathfollowing, mixed symbolic-numeric algorithm, parameter-dependent, nonlinear systems, linear representations.

Description: Systems of polynomial equations often have symmetry. The Buchberger algorithm which may be used for the solution ignores this symmetry. It is restricted to moderate problems unless factorizing polynomials are found leading to several smaller systems. Therefore two methods are presented which use the symmetry to find factorizing polynomials, decompose the ideal and thus decrease the complexitiy of the system a lot. In a first approach projections determine factorizing polynomials as input for the solution process, if the group contains reflections with respect to a hyperplane. Two different ways are described for the symmetric group Sm and the dihedral group Dm. While for Sm subsystems are ignored if they have the same zeros modulo G as another subsystem, for the dihedral group Dm polynomials with more than two factors are generated with the help of the theory of linear representations and restrictions are used as well. These decomposition algorithms are independent of the finally used solution technique. We used the REDUCE package Groebner to solve examples from CAPRASSE, DEMARET and NOONBURG which illustrate the efficiency of our REDUCE program. A short introduction to the theory of linear representations is given. In a second approach problems of another class are transformed such that more factors are found during the computation; these transformations are based on the theory of linear representations. Examples illustrate these approaches. The range of solvable problems is enlarged significantly.

Description: Symplectic difference schemes have been shown to be a right formalism for numerical computation of Hamiltonian systems. They are suitable to long time computation and of good qualitative properties. These properties are ensured by the fact that a symplectic difference scheme approximating to a time-independent Hamiltonian system can be regarded as a perturbed time-dependent Hamiltonian system of the original one. That is, a solution of a symplectic difference scheme is a solution of a certain perturbed time dependent Hamiltonian system evaluated at discrete (time) points. This is the main result of the paper. Moreover, linear symplectic difference schemes approximating to a linear time-independent Hamiltonian system can be regarded as a perturbed time-independent Hamiltonian system. So it has all properties that a linear Hamiltonian system has. Based on these results, stochastic webs and chaos in symplectic difference schemes are also discussed. They will appear in numerical simulation for Hamiltonian systems, even with one degree of freedom.

Description: The potential distribution of reverse biased pn-junctions can be described by a double obstacle problem for the Laplacian. This problem is solved by a self adaptive Finite Element Method involving automatic termination criteria for the iterative solver, local error estimation and local mesh refinement. Special attention is paid to the efficient resolution of the geometries typically arising in semiconductor device simulation. The algorithm is applied to a reverse biased pn- junction with multi-step field plate and stop- electrode to illustrate its efficiency and reliability.

Description: The paper presents a theoretical characterization of the often observed asymptotic mesh independence of Newton's method, which means that Newton's method applied to discretized operator equations behaves essentially the same for all sufficiently fine discretizations. The theory does not need any uniform Lipschitz assumptions that were necessary in comparable earlier treatments. The refined Newton-Mysovskii theorem, which will be of interest in a wider context, gives both existence and uniqueness of the solution and quadratic convergence for sufficiently good starting points. Attention is restricted to Galerkin approximations even though similar results should hold for finite difference methods - but corresponding proofs would certainly be more technical. As an illustrative example, adaptive 1-D collocation methods are discussed.

Description: Oxidation mechanisms even for rather simple hydrocarbons like heptane consist due to the occurrence of many isomeric structures of thousands of reactions of hundreds of species. The automatic generation of these reaction mechanisms using artificial intelligence means is described. Results are presented for n-heptane-air mixtures, where a hand-written reaction mechanism tested against experimental data is available.

Description: The paper surveys three aspects of chemical computing, which seem to play a role in recent developments. First, extrapolation methods for the numerical treatment of differential- algebraic equations are introduced. The associated extrapolation code LIMEX has reached a certain level of sophistication, which makes it a real competitor to the elsewhere widely used multi-step code DASSL of Petzold. Second, adaptive methods of lines for partial differential equations such as those arising in combustion problems are treated. Both static and dynamic regridding techniques are discussed in some detail. Finally, some new ideas about the treatment of the kinetic equations arising from polymer reactions are presented. The new feature of the suggested approach is the application of a Galerkin procedure using sets of orthogonal polynomials over a discrete variable (which, of course, in the case of polymer reactions is the polymer degree). The new approach may open the door to a new reliable low dimensional treatment of complex polymer reactions.

Description: The discrete Galerkin method developed by the authors has turned out to be an efficient tool for the computational treatment of very large scale ODE systems arising in polyreaction kinetics. Up to now, this approach has been worked out in detail for homogeneous polymer reactions. The present paper deals with one line of possible extensions of the method to the case of so-called heterogeneous processes, which may appear e. g. in smog reactions. The associated mathematical models involve reaction coefficients depending on the chain length of the reacting polymer. The herein suggested extension is worked out in some detail on the basis of the earlier paper. In addition, a numerical example describing polymer degradation is included.

Description: Newton methods for nonlinear problems are known to require the solution of a sequence of linear problems of the same type. For very large scale problems, as understood herein, the arising linear systems can only be solved by iterative methods. Then Newtons iteration appears as outer iteration. The question of interest will be to control the accuracy of the inner iteration such that the convergence speed of Newtons method is preserved. The purpose of the paper is to combine the concept of inexact Newton methods with the concept of the affine invariant exact Newton methods - which is important for problems with ill- conditioned Jacobian matrices (such as typical 2-D or 3-D discretized partial differential equations).

Description: A variety of secant methods has been revisited in view of the construction of iterative solvers for large nonsymmetric linear systems $ Ax = b $ stemming from the discretization of convection diffusion equations. In the first section, we tried to approximate $ A ^{-1} $ directly. Since the sparsity structure of A- is not known, additional storage vectors are needed during the iteration. In the next section, an incomplete factorization $ LU $ of $ A $ is the starting point and we tried to improve this easy invertible approximation of $ A $. The update is constructed in such a way that the sparsity structure of $ L $ and $ U $ is maintained. Two different sparsity preserving updates are investigated from theoretical and practical point of view. Numerical experiments on discretized PDEs of convection diffusion type in 2- D with internal layers and on "arbitrary" matrices with symmetric sparsity structure are given. {\bf Key words:} nonsymmetric linear system, sparse secant method, Broyden's method, incomplete factorization.

Description: The mathematical modeling of macromolecular reactions leads to countable (possibly infinite) systems of ordinary differential equations (CODE's). This paper reviews two recent developments of the so-called discrete Galerkin method, which has been developed for the numerical treatment of countable systems, which arise e.g. in polymer chemistry. The first approach can be considered as a method of lines with moving basis functions and has been implemented recently in the program package MACRON. The second type of the Galerkin method is characterized by a so-called outer time discretization of the complete problem and an appropriate and efficient solution of the arising subproblems. This method is realized in the research code CODEX.

Description: In continuation of part I this paper develops a variable-order time discretization in Hilbert space based on a multiplicative error correction. Matching of time and space errors as explained in part I allows to construct an adaptive multilevel discretization of the parabolic problem. In contrast to the extrapolation method in time, which has been used in part I, the new time discretization allows to separate space and time errors and further to solve fewer elliptic subproblems with less effort, which is essential in view of the application to space dimension greater than one. Numerical examples for space dimension one are included which clearly indicate the improvement.

Description: In the present paper, the improvement of an incomplete factorization of a non-symmetric matrix A is discussed. Starting from the ideas of sparsity preserving quasi-Newton methods, an algorithm is developed which improves the approximation of A by the incomplete factorization maintaining the sparsity structure of the matrices. No renumbering of the unknowns or the admittance of additional fill-in is necessary. The linear convergence of the algorithm is proved under the assumption, that $ L $ and $ U $* have the same sparsity structure and an incomplete factorization with some reasonable approximation property exits. In combination with this algorithm, the method of incomplete factorization and its several modifications are applicable to a wider class of problems with improved convergence qualities. This is shown by a numerical example. {\bf Key Words:} non-symmetric linear system, sparse secant method, incomplete factorization. AMS(MOS) {\bf Subject Classifications:} 65F10, 65N20, 65N30.

Description: Das CRAY-Handbuch des ZIB beschreibt nach einer grundlegenden bersicht detailliert die Handhabung von UNICOS-Dateien, die Verwendung von UNICOS-Kommandos und schließlich die (für Benutzer allein zugelassene) Ausführung von Batchjobs auf der CRAY. Neben der Erreichbarkeit der CRAY über das TCP/IP-Netz werden die Compiler FORTRAN, PASCAL und C beschrieben und schließlich auf die Optimierung der Rechenzeit ebenso wie auf die Fehlersuche eingegangen. Ein umfangreicher Anhang führt bereitgestellte Programmpakete, weiterführende Literatur, Zahlenbereiche und Zeichendarstellung an der CRAY auf.

Description: Diese Vorlesung ist eine Einführung in die Numerische Mathematik als einem der drei Bereiche (neben den Naturwissenschaften und der Informatik) des am besten mit dem Begriff Scientific Computing charakterisierten Forschungsgebietes. Aufgabe dieser relativ jungen Wissenschaft ist die Entwicklung von Rechenverfahren für Probleme aus den Naturwissenschaften mit Hilfe mathematischer Methoden.

Description: This paper presents the new program package MACRON for the simulation of macromolecular kinetics including standard chemical reactions. Such problems lead to countable (possibly) infinite systems of ordinary differential equations (CODE's), which are numerically treated by the so-called discrete Galerkin method here. By a chemical compiler the required analytical preprocessing is performed, such that the complete reaction system, standard kinetics as well as macromolecular reactions, can be entered in the chemical formalism. Typical macromolecular reaction steps are chain addition, termination, chain transfer and degradation (cracking). In order to ensure efficiency and reliability, high sophisticated numerical routines are built within the package. MACRON can be used without a detailed knowledge of the used numerical methods. As an illustration the application of MACRON to some realistic problems is presented.

Description: We study the power-law type solutions of the fourth order field equations derived from a generic quadratic Lagrangian density in the case of multidimensional Bianchi I cosmological models. All the solutions of the system of algebraic equations have been found, using computer algebra, from a search of the Groebner bases associated to it. While, in space dimension $ d = 3 $ , the Einsteinian Kasner metric is still the most general power-law type solution, for $ d 〉 3 $ , no solution, other than the Minkowski space-time, is common to the three systems of equations associated with the three contributions to the Lagrangian density. In the case of a pure Riemann-squared contribution (suggested by a recent calculation of the effective action for the heterotic string), the possibility exists to realize a splitting of the $ d $-dimensional space into a ( $ d - 3 $)-dimensional internal space and a physical 3- dimensional space, the latter expanding in time as a power bigger than 2 (about 4.5 when $ d = 9 $).

Description: Im vorliegenden Bericht wird die Parallelisierung zweier numerischer Algorithmen zur Lösung gewöhnlicher Differentialgleichungssysteme 1.Ordnung (explizite und semi-implizite Euler- Diskretisierung und $h$-Extrapolation) beschrieben. Implementiert wurden die Algorithmen mit OCCAM2 unter TDS (Transputer Development System) mit bis zu 4 Transputern T800. Meßwerte für die erreichten Beschleunigungen werden anhand mehrer Beispiele von Differentialgleichungs-systemen angegeben. {\bf Schlüsselwörter:} Adaptive, parallele Systeme; OCCAM2; Transputer; numerische Gleichungslöser; Euler-Diskretisierung; $h$-Extrapolation.

Description: BOXES computes a triangulation from a 2D domain description which consists of an arbitrary set of rectangles. Each rectangle may have attributes to control the triangulating process, define subdomain classes, or specify boundary conditions. The output of the program can be used as a coarse grid for KASKADE or one of its variants. Additional features are extensive checking of the user input, graphical display, and simple editing.

Description: This report presents the final realization and implementation of a global inexact Newton method proposed by Deuflhard. In order to create a complete piece of software, a recently developed iterative solver (program GBIT) due to Deuflhard, Freund, Walter is adapted and serves as the standard iterative linear solver. Alternative linear iterative solvers may be adapted as well, e.g. the widely distributed code GMRES. The new software package GIANT (Global Inexact Affine Invariant Newton Techniques) allows an efficient and robust numerical solution of very large scale highly nonlinear systems. Due to the user friendly interface and its modular design, the software package is open for an easy adaptation to specific problems. Numerical experiments for some selected problems illustrate performance and usage of the package.

Description: Efficient implementations of irregular problems on vector and parallel architectures are generally hard to realize. An important class of problems are Gauß-Seidel iteration schemes applied to irregular data sets. The unstructured data dependences arising there prevent restructuring compilers from generating efficient code for vector or parallel machines. It is shown, how to structure the data dependences by decomposing the underlying data set using graph coloring techniques and by specifying a particular execution order already on the algorithm level. Methods to master the irregularities originating from different types of tasks are proposed. An application is given and some open issues and future developments are discussed.