TY - GEN A1 - Grammel, Martin A1 - Hege, Hans-Christian A1 - Wunderling, Roland T1 - On the Impact of Communication Latencies on Distributed Sparse LU Factorization. N2 - Sparse LU factorization offers some potential for parallelism, but at a level of very fine granularity. However, most current distributed memory MIMD architectures have too high communication latencies for exploiting all parallelism available. To cope with this, latencies must be avoided by coarsening the granularity and by message fusion. However, both techniques limit the concurrency, thereby reducing the scalability. In this paper, an implementation of a parallel LU decomposition algorithm for linear programming bases is presented for distributed memory parallel computers with noticable communication latencies. Several design decisions due to latencies, including data distribution and load balancing techniques, are discussed. An approximate performance model is set up for the algorithm, which allows to quantify the impact of latencies on its performance. Finally, experimental results for an Intel iPSC/860 parallel computer are reported and discussed. T3 - ZIB-Report - SC-93-28 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1245 ER - TY - GEN A1 - Koepf, Wolfram T1 - A package on formal power series. N2 - Formal Laurent-Puiseux series of the form \[ f(x)=\sum \limits_{k=k_0}^{\infty}a_{k}x^{k/n} \] are important in many branches of mathematics. Whereas {\sc Mathematica} supports the calculation of truncated series with its {\tt Series} command, and the {\sc Mathematica} package {\tt SymbolicSum} that is shipped with {\sc Mathematica} version 2 is able to convert formal series of the type mentioned above in some instances to their corresponding generating functions, in six publications of the author we developed an algorithmic procedure to do these conversions that is implemented by the author, A.\ Rennoch and G.\ Stölting in the {\sc Mathematica} package {\tt PowerSeries}. The implementation enables the user to reproduce most of the results of the extensive bibliography on series of Hansen, E.\ R.: A table of series and products. Prentice-Hall, 1975. Moreover a subalgorithm of its own significance generates differential equations satisfied by the input function. T3 - ZIB-Report - SC-93-27 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1231 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Noncrossing Case. N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, 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. T3 - ZIB-Report - SC-93-26 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1225 ER - TY - GEN A1 - Richter-Gebert, Jürgen A1 - Ziegler, Günter M. T1 - Zonotopal Tilings and the Bohne-Dress Theorem. N2 - We prove a natural bijection between the polytopal tilings of a zonotope $Z$ by zonotopes, and the one-element-liftings of the oriented matroid ${\cal M}(Z)$ associated with $Z$. This yields a simple proof and a strengthening of the Bohne-Dress Theorem on zonotopal tilings. T3 - ZIB-Report - SC-93-25 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1212 ER - TY - GEN A1 - Deuflhard, Peter A1 - Schmidt, Frank T1 - Discrete Transparent Boundary Conditions for the Numerical Solution of Fresnel's Equation. N2 - The paper presents a construction scheme of deriving transparent , i. e. reflection-free, boundary conditions for the numerical solution of Fresnel's equation (being formally equivalent to Schrödinger's equation). These boundary conditions appear to be of a nonlocal Cauchy type. As it turns out, each kind of linear implicit discretization induces its own discrete transparent boundary conditions. T3 - ZIB-Report - SC-93-24 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1205 ER - TY - GEN A1 - Deuflhard, Peter A1 - Bölling, Reinhard A1 - Bott, Raoul H. T1 - Materialien zur Euler-Vorlesung in Sanssouci. N2 - Aus dem Inhalt: Vorwort; Leonhard Euler - aus der Zeit seines Wirkens in Berlin; Introductory Remarks. T3 - ZIB-Report - TR-93-10 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5029 ER - TY - GEN A1 - Deuflhard, Peter T1 - Cascadic Conjugate Gradient Methods for Elliptic Partial Differential Equations I. Algorithm and Numerical Results. N2 - Cascadic conjugate gradient methods for the numerical solution of elliptic partial differential equations consists of Galerkin finite element methods as outer iteration and (possibly preconditioned) conjugate gradient methods as inner iteration. Both iterations are known to minimize the energy norm of the arising iterations errors. A simple but efficient strategy to control the discretization errors versus the PCG iteration errors in terms of energy error norms is derived and worked out in algorithmic detail. In a unified setting, the relative merits of different preconditioners versus the case of no preconditioning is compared. Surprisingly, it appears that the cascadic conjugate gradient method without any preconditioning is not only simplest but also fastest. The numerical results seem to indicate that the cascade principle in itself already realizes some kind of preconditioning. A theoretical explanation of these observations will be given in Part II of this paper. T3 - ZIB-Report - SC-93-23 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1197 ER - TY - GEN A1 - Lang, Jens T1 - KARDOS - KAskade Reaction Diffusion One-dimensional System. N2 - A software package for the adaptive solution of time--dependent reaction--diffusion systems and linear elliptic systems in one space dimension is presented. The used algorithm is based on fundamental arguments in J.~Lang, A.~Walter: {\it A Finite Element Method Adaptive in Space and Time for Nonlinear Reaction--Diffusion Systems.} IMPACT of Computing in Science and Engineering, 4, p.~269--314 (1992). Here, only brief outlines of the algorithm are given. This software package is based on the KASKADE toolbox B.~Erdmann, J.~Lang, R.~Roitzsch: {\it KASKADE -- Manual.} To appear as Technical Report TR 93--5, Konrad--Zuse--Zentrum (ZIB) (1993). T3 - ZIB-Report - TR-93-09 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5019 ER - TY - GEN A1 - Deuflhard, Peter A1 - Ackermann, Jörg T1 - Adaptive Discrete Galerkin-Methods for Macromolecular Processes. N2 - In this paper, a rather recent algorithmic approac to the numerical simulation of macromolecula processes is surveyed. It avoids the numerical stiff integration o thousands up to millions of ODE's by constructing a scale of discret Hilbert spaces, especially weighted sequence spaces, and establishing corresponding Galerkin method. Examples including polyreactions o industrial relevance and ecological waste management by biochemica recycling illustrate the importance and efficiency of the algorithm. T3 - ZIB-Report - SC-93-22 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1180 ER - TY - GEN A1 - Stoer, Mechthild A1 - Dahl, Geir T1 - A Polyhedral Approach to Multicommodity Survivable Network Design. N2 - The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and non-redundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. Computational work using this model and the additional inequalities is in progress. T3 - ZIB-Report - SC-93-20 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1162 ER - TY - GEN A1 - Kornhuber, Ralf A1 - Yserentant, Harry T1 - Multilevel Methods for Elliptic Problems on Domains not Resolved by the Coarse Grid. N2 - Elliptic boundary value problems are frequently posed on complicated domains which cannot be covered by a simple coarse initial grid as it is needed for multigrid like iterative methods. In the present article, this problem is resolved for selfadjoint second order problems and Dirichlet boundary conditions. The idea is to construct appropriate subspace decompositions of the corresponding finite element spaces by way of an embedding of the domain under consideration into a simpler domain like a square or a cube. Then the general theory of subspace correction methods can be applied. T3 - ZIB-Report - SC-93-21 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1170 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Monotone Multigrid Methods for Elliptic Variational Inequalities I. N2 - Extending well--known linear concepts of successive subspace correction, we arrive at extended relaxation methods for elliptic variational inequalities. Extended underrelaxations are called monotone multigrid methods, if they are quasioptimal in a certain sense. By construction, all monotone multigrid methods are globally convergent. We take a closer look at two natural variants, which are called symmetric and unsymmetric multigrid methods, respectively. While the asymptotic convergence rates of the symmetric method suffer from insufficient coarse--grid transport, it turns out in our numerical experiments that reasonable application of the unsymmetric multigrid method may lead to the same efficiency as in the linear, unconstrained case. T3 - ZIB-Report - SC-93-18 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1147 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Monotone Multigrid Methods for Elliptic Variational Inequalities II. N2 - We derive fast solvers for discrete elliptic variational inequalities of the second kind as resulting from the approximation by piecewise linear finite elements. Following the first part of this paper, monotone multigrid methods are considered as extended underrelaxations. Again, the coarse grid corrections are localized by suitable constraints, which in this case are fixed by fine grid smoothing. We consider the standard monotone multigrid method induced by the multilevel nodal basis and a truncated version. Global convergence results and asymptotic estimates for the convergence rates are given. The numerical results indicate a significant improvement in efficiency compared with previous multigrid approaches. T3 - ZIB-Report - SC-93-19 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1151 ER - TY - GEN A1 - Hohmann, Andreas T1 - An Implementation of Extrapolation Codes in C++. N2 - This report describes the new object oriented implementation of extrapolation codes {\sc Eulex, Eulsim, Difex} for ordinary differential equations. The resulting C++ class library provides a simple and flexible interface to these methods and incorporates advanced features like continuous output and order-stepsize freezing. The interface of the ODE classes allows in particular a user-defined solver for the linear systems occuring in the linearly implicit discretization scheme. The library also provides some classes for numerical objects such as vectors and (full) matrices. Due to the underlying data-view concept it is possible to access substructures without copying. In addition, we included several utility classes such as a timer and a minimal command language that may be useful in other contexts, too. T3 - ZIB-Report - TR-93-08 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5009 ER - TY - GEN A1 - Diaconics, Persi A1 - Sturmfels, Bernd T1 - Algebraic Algorithms for Sampling from Conditional Distributions. N2 - We construct Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic. Examples include generating tables with fixed row and column sums and higher dimensional analogs. The algorithms involve finding bases for associated polynomial ideals and so an excursion into computational algebraic geometry. T3 - ZIB-Report - SC-93-17 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1131 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Paths and Steiner Trees: Routing of Electronic Circuits. N2 - One of the challenging problems in the design of electronic circuits is the so-called routing problem. Roughly speaking, the task is to connect so-called terminal sets via wires on a predefined area. In addition, certain design rules are to be taken into account and an objective function such as the wiring length must be minimized. The routing problem in general is too complex to be solved in one step. Depending on the user's choice of decomposing the chip design problem into a hierarchy of stages, on the underlying technology, and on the given design rules, various subproblems arise. We discuss several variants of practically relevant routing problems and give a short overview on the underlying technologies and design rules. Many of the routing problems that come up this way can be formulated as the problem of packing so-called Steiner trees in certain graphs. We consider the Steiner tree packing problem from a polyhedral point of view and present three possibilities to define an appropriate polyhedron. Weighing their pros and cons we decide for one of these polytopes and sketch some of our investigations. T3 - ZIB-Report - SC-93-15 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1113 ER - TY - GEN A1 - Grötschel, Martin A1 - Lovász, Lászlo T1 - Combinatorial Optimization. N2 - This paper will appear as Chapter 28 of the forthcoming "Handbook on Combinatorics" (editors: R. Graham, M. Grötschel, L. Lovasz) to be published in 1994, by North-Holland. T3 - ZIB-Report - SC-93-13 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1098 ER - TY - GEN A1 - Gatermann, Karin A1 - Werner, Bodo T1 - Secondary Hopf Bifurcation Caused by Steady-State Steady-State Mode Interaction. N2 - In two-parameter systems with symmetry two steady state bifurcation points of different symmetry types coalesce generically within one point. Under certain group theoretic conditions involving the action of the symmetry group on the kernels, we show that secondary Hopf bifurcation is borne by the mode interaction. We explain this phenomenon by using linear representation theory. For motivation an example with $D_3$-symmetry is investigated where the main properties causing the Hopf bifurcation are summarized. T3 - ZIB-Report - SC-93-16 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1122 ER - TY - GEN A1 - Hege, Hans-Christian A1 - Höllerer, Tobias A1 - Stalling, Detlev T1 - Volume Rendering - Mathematicals Models and Algorithmic Aspects. N2 - In this paper various algorithms for rendering gaseous phenomena are reviewed. In computer graphics such algorithms are used to model natural scenes containing clouds, fog, flames and so on. On the other hand it has become an important technique in scientific visualization to display three dimensional scalar datasets as cloudy objects. Our emphasis is on this latter subject of so-called {\em direct volume rendering}. All algorithms will be discussed within the framework of linear transport theory. The equation of transfer is derived. This equation is suitable to describe the radiation field in a participating medium where absorption, emission, and scattering of light can occur. Almost all volume rendering algorithms can be shown to solve special cases of the equation of transfer. Related problems like the mapping from data values to model parameters or possible parallelization strategies will be discussed as well. T3 - ZIB-Report - TR-93-07 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4994 ER - TY - GEN A1 - Schütte, Christof A1 - Hohmann, Andreas A1 - Dinand, Manfred T1 - Numerical Simulation of Relaxation Oscillations of Waveguide-Lasers. N2 - An analysis of relaxation oscillations in local Er-doped optically pumped lasers is reported. It is based on a time dependent rate equation model for a quasi-two-level-system with wavelength dependent emission- and absorption cross-sections. For the first time a numerically reliable simulation of the characteristic laser behaviour was possible: the onset and decay of the oscillations, the time-dependent repetition period and the steady state signal output power. The characteristic waveguide parameters, as the erbium-concentration profile, the polarization dependent pump- and signal mode intensity profiles, the scattering losses, the cavity length and the front and rear reflectivities were all taken into account. The basic formulas are general and can also be used for Er-doped fiber lasers. Mathematically the problem can be characterized as a large boundary value problem, which can approximately be replaced by a stiff initial value problem of ordinary differential equations. The used algorithmic replacement procedure is motivated and discussed in detail. Here, pump- and signal evolution versus time are presented for an planar Er-diffused $\rm Ti$:$\rm LiNbO_{3}$ waveguide laser. The numerically obtained results show a nearly quantitative agreement with experimental investigations. Simultanously they supply knowledge about non-measureable (space-dependent population dynamic of the Er-atoms) and till today not measured data (dynamical response of the laser by a sharp peak in the external pump). T3 - ZIB-Report - SC-93-14 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1106 ER - TY - GEN A1 - Ziegler, Günter M. T1 - Lectures on Polytopes. N2 - These lecture notes have several aims: \begin{itemize} \item to give an introduction to some basic facts about convex polytopes, with an emphasis on the basic methods that yield them (Fourier-Motzkin elimination, Schlegel diagrams, shellability, Gale transforms and oriented matroids), \item to discuss some important examples and elegant constructions (cyclic and neighborly polytopes, zonotopes, Minkowski sums, permutahedra and associahedra, fiber polytopes, the Lawrence construction) \item and to illustrate why polytope theory is exciting, with highlights like Kalai's new diameter bounds, the construction of non-rational polytopes, the Bohne-Dress tiling theorem, shellability and the upper bound theorem, .... \end{itemize} For several of these topics the decisive break-through is very recent, which suggests that there is much more discovered. T3 - ZIB-Report - TR-93-06 Y1 - 1993 N1 - No preprint available; published as Ziegler, G. M. (1994) Lectures on Polytopes. ISBN 354094365X, New York: Springer ER - TY - GEN T1 - Jahresbericht 1993 T3 - Jahresbericht - 1993 KW - Annual Report Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9668 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1992 T3 - Jahresbericht - 1992 KW - Annual Report Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9686 SN - 0934-5892 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim A1 - Sperber, Wolfram T1 - Wissenschaftliches Publizieren und Elektronische Fachinformation im Umbruch: ein Situationsbericht aus der Sicht der Mathematik. N2 - In diesem Aufsatz geben wir einen Bericht über den Stand der elektronischen Fachinformation in der Mathematik in Deutschland. Wir sehen diesen Bereich nicht als ein organisatorisch isoliertes Unterfangen, sondern eingebettet in weltweite Bestrebungen und Entwicklungen in der Informationstechnik, im wissenschaftlichen Publikationswesen und natürlich auch in der Mathematik selber. Unser Artikel endet mit einigen weitreichenden (und einigen Lesern möglicherweise spektakulär erscheinenden) Vorschlägen, die sowohl die Informationsanbieter (wie die Fachinformationszentren und Verlage), die öffentlichen Geldgeber als auch die mathematischen Organisationen (wie z.~B.~ die DMV und die mathematischen Fachbereiche) betreffen. Um den gegenwärtigen Zustand der elektronischen Fachinformation und unsere Gedanken zu diesem Thema adäquat beschreiben zu können, präsentieren wir eine breit angelegte Situationsanalyse. Wir stellen den gegenwärtigen Stand der technologischen Entwicklung im elektronischen Publizieren dar und skizzieren seine Auswirkungen. Wir beschreiben das Feld der Interessen und Kräfte im Bereich des mathematischen Publizierens. Wir geben einen kurzen historischen Abriss der Geschichte der Klassifikation und des Referatewesens und zeigen, wie dieses in die elektronische Fachinformation auf dem Gebiet der Mathematik mündete und dann zum DMV-Projekt Fachinformation führte, das der Anlass zur Abfassung dieses Artikels war. Wir skizzieren die gegenwärtige Rezeption elektronischer Fachinformation in der Mathematik in Deutschland. Ausgehend von einer Darstellung und Bewertung verschiedener Modelle des Referatewesens zeigen wir unter Einbeziehung der vorhandenen technischen Gegebenheiten (elektronische Netze etc.) verschiedene Möglichkeiten zur Liberalisierung und Rationalisierung des weltweiten mathematischen Informationswesens auf. Wir sehen den Austausch von Information in engem Zusammenhang mit dem Austausch von Software im Wissenschaftsbereich und regen auch in diesem Bereich an, internationale Kooperation und Offenheit anzustreben. \originalTeX T3 - ZIB-Report - TR-93-04 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4966 ER - TY - GEN A1 - Ackermann, Jörg A1 - Roitzsch, Rainer T1 - On a Two-Dimensional Multilevel Adaptive Finite Element Method for the Time-Independent Schrödinger-Equation. N2 - The subject of this study is a multilevel Finite Element Method based on an error estimator and step by step grid refinement as an universal tool for solving time--independent Schrödinger--eigenvalue problems. Numerical results for standard problems appearing in vibrational motion and molecular electronic structure calculations are given and discussed. T3 - ZIB-Report - SC-93-12 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1086 ER - TY - GEN A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Roitzsch, Rainer T1 - Kaskade Manual - Version 2.0. N2 - The KASKADE toolbox defines an interface to a set of C subroutines which can be used to implement adaptive multilevel Finite Element Methods solving systems of elliptic equations in two and three space dimensions. The manual contains the description of the data structures and subroutines. The main modules of the toolbox are a runtime environment, triangulation and node handling, assembling, direct and iterative solvers for the linear systems, error estimators, refinement strategies, and graphic utilities. Additionally, we included appendices on the basic command language interface, on file formats, and on the definition of the partial differential equations which can be solved. The software is available on the ZIB ftp--server {\tt elib} in the directory {\tt pub/kaskade}. TR 93--5 supersedes TR 89--4 and TR 89--05. T3 - ZIB-Report - TR-93-05 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4970 ER - TY - GEN A1 - Reiner, Victor A1 - Ziegler, Günter M. T1 - Coxeter-associahedra. N2 - \def\KPA{\hbox{\rm KPA}}\def\A{{\rm A}}\def\KPW{\hbox{\rm KPW}}\def\W{{\rm W}}\def\B{{\rm B}} \def\D{{\rm D}} Recently M.~M.~Kapranov [Kap] defined a poset $\KPA_{n-1}$, called the {\it permuto-associahedron}, which is a hybrid between the face poset of the permutahedron and the associahedron. Its faces correspond to the partially parenthesized, ordered, partitions of the set $\{1,2,\ldots,n\}$, with a natural partial order. Kapranov showed that $\KPA_{n-1}$ is the face poset of a CW-ball, and explored its connection with a category-theoretic result of MacLane, Drinfeld's work on the Knizhnik-Zamolodchikov equations, and a certain moduli space of curves. He also asked the question of whether this CW-ball can be realized as a convex polytope. We show that this permuto-associahedron corresponds to the type $\A_{n-1}$ in a family of convex polytopes $\KPW$ associated to each of the classical Coxeter groups, $\W = \A_{n-1}, \B_n, \D_n$. The embedding of these polytopes relies on the secondary polytope construction of the associahedron due to Gel'fand, Kapranov, and Zelevinsky. Our proofs yield integral coordinates, with all vertices on a sphere, and include a complete description of the facet-defining inequalities. Also we show that for each $\W$, the dual polytope $\KPW^*$ is a refinement (as a CW-complex) of the Coxeter complex associated to $\W$, and a coarsening of the barycentric subdivision of the Coxeter complex. In the case $\W=\A_{n-1}$, this gives an elementary proof of Kapranov's original sphericity result. T3 - ZIB-Report - SC-93-11 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1075 ER - TY - GEN A1 - Langendorf, Jens A1 - Paetsch, Olaf T1 - GRAZIL - Beschreibung der Version 6.0 des Plotpaketes. N2 - GRAZIL ist ein interaktives Programmpaket zur grafischen Darstellung von zwei-dimensionalen Kurvenverläufen. Dem Benutzer stehen zahlreiche Kommandos und ein grafisches User-Interface zum Gestalten des Layouts der Zeichnung zur Verfügung. Die Eingabedaten müssen dem GRAZIL-Eingabe-Format genügen. Somit wird eine hohe Flexibilität und eine gro\"se Bandbreite der Einsatzmöglichkeiten erreicht. GRAZIL wurde mit der grafischen Grundsoftware GKS entwickelt. Dadurch kann ein breites Rechner- und Ausgabegerätespektrum genutzt werden. T3 - ZIB-Report - TR-93-01 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4930 ER - TY - GEN A1 - Schütte, Christof T1 - A quasiresonant smoothing algorithm for the fast analysis of selective vibrational excitation. N2 - One key problem in modern chemistry is the simulation of the dynamical reaction of a molecule subjected to external radiation. This is described by the Schrödinger equation, which, after eigenfunction expansion, can be written in form of a system of ordinary differential equations, whose solutions 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. This idea leads to the construction of a quasiresonant smoothing algorithm (QRS). In QRS, a natural and computationally available splitting parameter $\delta$ controls the smoothing properties. The performance of QRS is demonstrated in two applications treating the selective excitation of vibrational states by picosecond laser pulses. In comparison with standard methods a speedup factor of 60--100 is observed. A closer look to purely physically motivated quasiresonant approximations such as WFQRA shows some additional advantages of the above smoothing idea. Among these the possibility of an adaptive formulation of QRS via the parameter $\delta$ is of particular importance. T3 - ZIB-Report - SC-93-10 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1066 ER - TY - GEN A1 - Erdmann, Bodo A1 - Hoppe, Ronald H. W. A1 - Kornhuber, Ralf T1 - Adaptive Multilevel-Methods for Obstacle Problems in Three Space Dimensions. N2 - We consider the discretization of obstacle problems for second order elliptic differential operators in three space dimensions by piecewise linear finite elements. Linearizing the discrete problems by suitable active set strategies, the resulting linear sub--problems are solved iteratively by preconditioned cg--iterations. We propose a variant of the BPX preconditioner and prove an $O(j)$ estimate for the resulting condition number. To allow for local mesh refinement we derive semi--local and local a posteriori error estimates. The theoretical results are illustrated by numerical computations. T3 - ZIB-Report - SC-93-08 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1049 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Design of Survivable Networks T3 - ZIB-Report - SC-93-09 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1054 ER - TY - GEN A1 - Weismantel, Robert A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - A Cutting Plane Based Algorithm for the Multiple Knapsack Problem. N2 - In this paper we describe a cutting plane based algorithm for the multiple knapsack problem. We use our algorithm to solve some practical problem instances arising in the layout of electronic circuits and in the design of main frame computers, and we report on our computational experience. This includes a discussion and evaluation of separation algorithms, an LP-based primal heuristic and some implementation details. The paper is based on the polyhedral theory for the multiple knapsack polytope developed in our companion paper SC 93-04 and meant to turn this theory into an algorithmic tool for the solution of practical problems. T3 - ZIB-Report - SC-93-07 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1031 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus-Disposition: Ein Konzept zur Serviceverbesserung bei gleichzeitiger Kostensenkung.[nur hausintern] N2 - "`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums für Informationstechnik (ZIB) hat das Ziel, den Fahrdienst (insbesondere die Disposition der Telebusse) zu verbessern, d.h. kundenfreundlicher zu gestalten und gleichzeitig billiger zu machen. In diesem Bericht werden die bisherigen Ergebnisse dargestellt und weitere Möglichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX T3 - ZIB-Report - TR-93-03 Y1 - 1993 N1 - Volltext nur Hausintern ER - TY - GEN A1 - Deuflhard, Peter T1 - A Study of Lanczos-Type Iterations for Symmetric Indefinite Linear Systems N2 - The Lanczos iteration for symmetric indefinite linear systems seems to be well--known for quite a while. However, in order to modify it with the aim of improved performance, the present paper studies certain aspects in terms of an adjoint scalar three--term recurrence. Thus, at least a different view is opened. Moreover, an alternative $3n$--implementation in terms of the Euclidean orthogonal basis has been found that easily permits generalizations. The study is understood as a start--off for further numerical investigations and experiments. T3 - ZIB-Report - SC-93-06 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1029 ER - TY - GEN A1 - Richter-Gebert, Jürgen T1 - Mechanical Theorem Proving in Projective Geometry. N2 - We present an algorithm that is able to confirm projective incidence statements by carrying out calculations in the ring of all formal determinants (brackets) of a configuration. We will describe an implementation of this power and present a series of examples treated by the prover, including {\it Pappos' and Desargues' Theorems,} the {\it Sixteen Point Theorem, Saam's Theorem, }the {\it Bundle Condition,} the uniqueness of a harmonic Point and {\it Pascal's Theorem.} T3 - ZIB-Report - SC-93-05 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1013 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Facets for the Multiple Knapsack Problem. N2 - In this paper we consider the multiple knapsack problem which is defined as follows: given a set $N$ of items with weights $f_i$, $i \in N$, a set $M$ of knapsacks with capacities $F_k$, $k \in M$, and a profit function $c_{ik}, i \in N, k \in M$; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07. T3 - ZIB-Report - SC-93-04 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1007 ER - TY - GEN A1 - Melenk, Herbert T1 - Algebraic Solution of Nonlinear Equation Systems in REDUCE. N2 - The strategy for solving nonlinear equation systems automatically in the computer algebra system REDUCE is described. Kernel of the solver is a factoring Buchberger algorithm. Pre -- and postprocessors enable the use of the Gröbner techniques in a black box manner. In addition to polynomials equations with surds, trigonometric functions and separable transcendental functions are covered. T3 - ZIB-Report - TR-93-02 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4944 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Grötschel, Martin A1 - Kiefl, Stefan A1 - Krispenz, Ludwig A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Some Integer Programs Arising in the Design of Main Frame Computers. N2 - In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult -- at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are also $NP$-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well. T3 - ZIB-Report - SC-92-25 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-957 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements. N2 - We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain ``two-connected" survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements which shows promise for providing good solutions to these difficult problems. \def\NP{$\cal NP$} T3 - ZIB-Report - SC-92-24 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-944 ER - TY - GEN A1 - Gatermann, Karin A1 - Werner, Bodo T1 - Group Theoretical Mode Interactions with Different Symmetries. N2 - 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. T3 - ZIB-Report - SC-93-03 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-994 ER - TY - GEN T1 - Handbuch zur Visualisierung am ZIB N2 - Scientists intending to employ scientific visualization techniques are confronted with the unpleasant task of choosing visualization software that meets their specific needs. A good choice requires consideration of several aspects. Most important are functionality, i.e. the set of supported visual representations, and restrictions due to the user's production environment (i.e. available hardware and software platforms, software compatibility constraints, need of specific input and output formats, network distribution requirements). Crucial are quality demands, ranging from simple graphics for interactive control of simulations, to images of highest quality (glossy prints, slides or video movies) for presentation purposes. Further aspects of consideration are: ease of use, level on which the user is willing to program, portability, conformity to prevalent standards, availability in the world-wide user community, future dissemination, as well as emerging trends in computer graphics and scientific visualization. The aim of this manual is to give a survey on the graphics and visualization software that is currently being provided at ZIB (mainly for internal use). The whole range of computer graphics software relevant in mathematical, natural and technical sciences is covered: image synthesis (basic and higher graphics libraries, plot programs, visualization environments, combined text and drawing programs, renderers), image processing and storage (raster and vector formats, page description languages, raster toolkits for image processing and format conversion), capturing of images as well as printing on paper and recording on photographic film or video tape. This information together with a glossary and recommendations for further reading should help prospective users in getting started and assist them in making good choices of graphics and visualization software. T3 - ZIB-Report - TR-92-07 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4920 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Routing in Grid Graphs by Cutting Planes. N2 - {\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.} T3 - ZIB-Report - SC-92-26 KW - routing in VLSI-design KW - Steiner tree KW - Steiner tree packing KW - cutting plane algorithm Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-967 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Further Facets. N2 - 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. T3 - ZIB-Report - SC-93-01 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-975 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Separation Algorithms. N2 - 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. T3 - ZIB-Report - SC-93-02 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-984 ER - TY - GEN A1 - Grötschel, Martin A1 - Monma, Clyde A1 - Stoer, Mechthild T1 - A Polyhedral Approach to Network Connectivity Problems (Extended Abstract). N2 - We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir T3 - ZIB-Report - SC-92-22 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-924 ER - TY - GEN A1 - Chu, Nguyen Ngoc T1 - An Algorithm for Optimizing a Linear Function over the Integer Efficient Set. N2 - Whereas optimization of a linear function over an efficient set is a favourite topic for theoretical studies, the problem ($P^I$) of finding a maximal value of a linear function $dx$ over an integer efficient set is still open. The problem ($P^I$) is NP-hard and it is very unlikely that the maximal objective value of the integer problem ($P^I$) in many cases is greater than the maximal objective value of it's corresponding continuous problem ($P$). In this paper we pay atention to the study of the problem ($P^I$) and some related properties of the problem ($P$). In particular, we establish conditions determining whether or not an optimal solution to the problem ($P$) is an optimal solution to the it's corresponding linear program. For the problem ($P^I$) we find an upper bound for it's optimal objective value and present an algorithm which gives a global optimal solution after a finite number of steps. We also study two particular classes of problems ($P^I$) : the bicriteria case and the case when $d$ is a nonnegative linear combination of the vectors-criteria defining the efficient set. Key words: Multiple objective linear programming, integer efficient set, efficient cone, cutting plane. T3 - ZIB-Report - SC-92-23 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-930 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim A1 - Sperber, Wolfram T1 - Elektronische Fachinformation im Bereich der Mathematik an Hochschulen und Statusbericht zum DMV-Projekt. "Fachinformation". N2 - Im Bereich der Mathematik entwickelte sich in Deutschland die elektronische Fachinformation in Form der Online-Datenbank MATH und der CD-ROM CompactMATH auf der Grundlage der Arbeiten des Referateorgans "Zentralblatt für Mathematik und Ihre Grenzgebiete". Das "Zentralblatt" fand weithin Anerkennung und Verbreitung. Die Rezeption elektronischer Fachinformation ging jedoch - nicht nur im Bereich der Mathematik - nur zögerlich vonstatten. Die Gründe dafür werden in einer vom Bundesminister für Forschung und Technologie (BMFT) initiierten Studie analysiert. Ein kürzlich von der Deutschen Mathematiker - Vereinigung begonnenes und vom BMFT gefördertes Vorhaben hat die "Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online-Datenbanken und CD-ROM für Mathematische Institute in der Bundesrepublik Deutschland" zum Ziel. Insgesamt 51 mathematische Fachbereiche und Institute nehmen daran teil. Elektronische Fachinformation soll zu einem festen Bestandteil des methodischen Instrumentariums der wissenschaftlichen Arbeit werden. Diese Schrift soll die Ausgangslage in den Fachbereichen darstellen und die organisatorischen und technischen Infrastrukturmaßnahmen erläutern, mit denen den spezifischen Nutzungshemmnissen begegnet werden soll. T3 - ZIB-Report - TR-92-06 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4910 ER - TY - GEN A1 - Nowak, Ulrich T1 - Dynamic Sparsing in Stiff Extrapolation Methods. N2 - 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. T3 - ZIB-Report - SC-92-21 KW - large scale integration KW - extrapolation methods KW - stiff ODEs KW - W-methods KW - sparse matrix techniques Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-911 ER - TY - GEN A1 - Yang, Shuli T1 - Numerical Riemann solutions in multi-pieces for 2-D gas dynamics systems I. Contact discontinuities. N2 - The numerical solutions of Riemann problems in three, four, five and six pieces, which only contain contact discontinuities, are presented by using Taylor FVM MmB schemes on regular triangular meshes for 2-D gas dynamics systems. The 2-D Riemann initial data are as defined in [1], under the assumption that each jump in initial data outside of the origin projects exactly one planar wave of shocks, centered rarefaction waves , or contact discontinuities. The main ends of the paper are that spirals will be shown for some configurations and the relations of the solutions between different distibutions of Riemann initial data are explained by the numerical solutions of modified Riemann problems. Key words and phrases: Riemann problem, gas dynamics systems, spiral, MmB schemes. T3 - ZIB-Report - SC-92-20 KW - Riemann problem KW - gas dynamics systems KW - spiral Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-903 ER - TY - GEN A1 - Ziegler, Günter M. T1 - Shellability of Chessboard Complexes. N2 - The matchings in a complete bipartite graph form a simplicial complex, which in many cases has strong structural properties. We use an equivalent description as chessboard complexes: the complexes of all non-taking rook positions on chessboards of various shapes. In this paper we construct `certificate $k$-shapes' $\Sigma(m,n,k)$ such that if the shape $A$ contains some $\Sigma(m,n,k)$, then the $(k{-}1)$-skeleton of the chessboard complex $\Delta(A)$ is vertex decomposable in the sense of Provan & Billera. This covers, in particular, the case of rectangular chessboards $A=[m]{\times}[n]$, for which $\Delta(A)$ is vertex decomposable if $n\ge 2m{-}1$, and the $(\lfloor{m+n+1\over3}\rfloor{-}1)$-skeleton is vertex decomposable in general. The notion of vertex decomposability is a very convenient tool to prove shellability of such combinatorially defined simplicial complexes. We establish a relation between vertex decomposability and the CL-shellability technique (for posets) of Björner & Wachs. T3 - ZIB-Report - SC-92-19 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-890 ER - TY - GEN A1 - Hohmann, Andreas A1 - Wulff, Claudia T1 - Modular Design of Extrapolation Codes. N2 - In this paper we describe a modular implementation of the well-established extrapolation codes EULEX, EULSIM and DIFEX for initial value problems of ordinary differential equations. The basic module embodies an abstract extrapolation method with order and stepsize control. Based on this module the particular integration codes only have to provide the underlying discretization schemes. T3 - ZIB-Report - TR-92-05 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4909 ER - TY - GEN A1 - Bornemann, Folkmar A. T1 - Adaptive Solution of One-Dimensional Scalar Conservation Laws with Convex Flux. N2 - A new adaptive approach for one-dimensional scalar conservation laws with convex flux is proposed. The initial data are approximated on an adaptive grid by a problem dependent, monotone interpolation procedure in such a way, that the multivalued problem of characteristic transport can be easily and explicitly solved. The unique entropy solution is chosen by means of a selection criterion due to LAX. For arbitrary times, the solutions is represented by an adaptive monotone spline interpolation. The spatial approximation is controlled by local $L^1$-error estimated. As a distinctive feature of the approach, there is no discretization in time. The method is monotone on fixed grids. Numerical examples are included, to demonstrate the predicted behavior. {\bf Key words.} method of characteristics, adaptive grids, monotone interpolation, $L^1$-error estimates {\bf AMS(MOS) subject classification.} 65M15, 65M25, 65M50. T3 - ZIB-Report - SC-92-18 KW - method of characteristics KW - adaptive grids KW - monotone interpolation KW - L1-error estimates Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-880 ER -