@misc{Reich1994, author = {Reich, Sebastian}, title = {Smoothed Dynamics of Highly Oscillatory Hamiltonian Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1564}, number = {SC-94-28}, year = {1994}, abstract = {We consider the numerical treatment of Hamiltonian systems that contain a potential which grows large when the system deviates from the equilibrium value of the potential. Such systems arise, e.g., in molecular dynamics simulations and the spatial discretization of Hamiltonian partial differential equations. Since the presence of highly oscillatory terms in the solutions forces any explicit integrator to use very small step-size, the numerical integration of such systems provides a challenging task. It has been suggested before to replace the strong potential by a holonomic constraint that forces the solutions to stay at the equilibrium value of the potential. This approach has, e.g., been successfully applied to the bond stretching in molecular dynamics simulations. In other cases, such as the bond-angle bending, this methods fails due to the introduced rigidity. Here we give a careful analysis of the analytical problem by means of a smoothing operator. This will lead us to the notion of the smoothed dynamics of a highly oscillatory Hamiltonian system. Based on our analysis, we suggest a new constrained formulation that maintains the flexibility of the system while at the same time suppressing the high-frequency components in the solutions and thus allowing for larger time steps. The new constrained formulation is Hamiltonian and can be discretized by the well-known SHAKE method.}, language = {en} } @misc{AstonDellnitz1994, author = {Aston, Philip J. and Dellnitz, Michael}, title = {Symmetry Breaking Bifurcations of Chaotic Attractors}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1557}, number = {SC-94-27}, year = {1994}, abstract = {In an array of coupled oscillators {\em synchronous chaos} may occur in the sense that all the oscillators behave identically although the corresponding motion is chaotic. When a parameter is varied this fully symmetric dynamical state can lose its stability, and the main purpose of this paper is to investigate which type of dynamical behavior is expected to be observed once the loss of stability has occurred. The essential tool is a classification of Lyapunov exponents based on the symmetry of the underlying problem. This classification is crucial in the derivation of the analytical results but it also allows an efficient computation of the dominant Lyapunov exponent associated with each symmetry type. We show how these dominant exponents determine the stability of invariant sets possessing various instantaneous symmetries and this leads to the idea of {\em symmetry breaking bifurcations of chaotic attractors}. Finally the results and ideas are illustrated for several systems of coupled oscillators.}, language = {en} } @misc{SturmfelsWeismantelZiegler1994, author = {Sturmfels, Bernd and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {Gr{\"o}bner bases of lattices, corner polyhedra, and integer programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1548}, number = {SC-94-26}, year = {1994}, abstract = {We investigate the generating sets (``Gr{\"o}bner bases'') of integer lattices which correspond to the Gr{\"o}bner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gr{\"o}bner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gr{\"o}bner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.}, language = {en} } @misc{Hohmann1994, author = {Hohmann, Andreas}, title = {Multilevel Newton h-p Collocation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1530}, number = {SC-94-25}, year = {1994}, abstract = {We derive a simple accuracy matching strategy for inexact Gauss Newton methods and apply it to the numerical solution of boundary value problems of ordinary differential equations by collocation. The matching strategy is based on an affine contravariant convergence theorem, i. e. , the characteristic constants are invariant under affine transformations of the domain. The inexact Gauss Newton method is applied to an integral formulation of the BVP. As discretization for the arising linear subproblems we employ adaptive collocation at Gaussian nodes with varying local orders and stepsizes. The grids are chosen via adaptive refinement and order selection.}, language = {en} } @misc{Koepf1994, author = {Koepf, Wolfram}, title = {Algebraische Darstellung transzendenter Funktionen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1524}, number = {SC-94-24}, year = {1994}, abstract = {In this article algorithmic methods are presented that have been incorporated in computer algebra systems in the last five years. The methods can be used to identify transcendental functions. The essential idea due to Zeilberger is to represent the functions by systems of holonomic differential and recurrence equations, and the identification procedure utilizes algorithms of Stanley and Zeilberger. Also a noncommutative version of the Buchberger algorithm can be applied.}, language = {de} } @misc{DeuflhardNowakWeyer1994, author = {Deuflhard, Peter and Nowak, Ulrich and Weyer, J.}, title = {Prognoserechnung zur AIDS-Ausbreitung in der Bundesrepublik Deutschland}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1511}, number = {SC-94-23}, year = {1994}, abstract = {Die Autoren sind sich dar{{\"u}}ber im klaren, daß zahlreiche Imponderabilien die Ergebnisse der vorgelegten Modellrechnungen beeinflussen k{{\"o}}nnen. Immerhin repr{\"a}sentiert jedoch das vorgelegte mathematische Modell die Summe unserer derzeitigen Kenntnisse zur Fragestellung AIDS--Epidemie; neu hinzukommende Erkenntnisse lassen sich rasch einarbeiten und in ihren Konsequenzen {\"u}berschauen. Die Entwicklung neuer effizienter numerischer Methoden spielte eine Schl{\"u}sselrolle bei der tats{\"a}chlichen Simulation dieses umfangreichen realit{\"a}tsnahen mathematischen Modells.}, language = {de} } @misc{DeuflhardWulkow1994, author = {Deuflhard, Peter and Wulkow, Michael}, title = {Simulationsverfahren f{\"u}r die Polymerchemie}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1502}, number = {SC-94-22}, year = {1994}, abstract = {Die enorme algorithmische Beschleunigung durch diskrete Galerkin-Methoden f{{\"u}}r abz{{\"a}}hlbare Differentialgleichungssysteme hat der Simulation von Polymerisationsprozessen neue, industriell relevante Problembereiche er{{\"o}}ffnet, die mit den bis dahin verf{{\"u}}gbaren Methoden nicht zug{{\"a}}nglich waren.}, language = {de} } @misc{HansmannOkamoto1994, author = {Hansmann, Ulrich H. E. and Okamoto, Yuko}, title = {Comparative Study of Multicanonical and Simulated Annealing Algorithms in the Protein Folding Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1483}, number = {SC-94-20}, year = {1994}, abstract = {We compare a few variants of the recently proposed multicanonical method with the well known simulated annealing for the effectiveness in search of the energy global minimum of a biomolecular system. For this we study in detail Met-enkephalin, one of the simplest peptides. We show that the new method not only outperforms simulated annealing in the search of the energy groundstate but also provides more statistical-mechanical information about the system.}, language = {en} } @misc{Hansmann1994, author = {Hansmann, Ulrich H. E.}, title = {Towards Ab Initio Prediction of Protein Conformations - The Multicanonical Approach.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1494}, number = {SC-94-21}, year = {1994}, abstract = {We demonstrate the effectiveness of the multicanonical algorithm for the tertiary structure prediction of peptides and proteins. Unlike to simulated annealing the relationship to the canonical ensemble remains exactly controlled. Hence, the new method allows not only the prediction of the lowest-energy conformation, but also the calculation of thermodynamic quantities at various temperature from one run.}, language = {en} } @misc{DalitzGroetschelLueggeretal.1994, author = {Dalitz, Wolfgang and Gr{\"o}tschel, Martin and L{\"u}gger, Joachim and Sperber, Wolfram}, title = {Neue Perspektiven eines verteilten Informationssystems f{\"u}r die Mathematik.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5122}, number = {TR-94-07}, year = {1994}, abstract = {Die Kombination von elektronischer Fachinformation mit den neuen Mitteln der Kommunikation er{\"o}ffnet neue Perspektiven f{\"u}r die Mathematik in Deutschland. Aufbauend auf das laufende, BMFT-gef{\"o}rderte Projekt ``Fachinformation'' der Deutschen Mathematiker-Vereinigung (DMV) plant die DMV eine Querschnittsaktivit{\"a}t f{\"u}r die Mathematik. Diese soll nicht nur die mathematischen Fachbereiche und Forschungsinstitute einbeziehen, sondern auch mathematische Forschungslabors aus der Industrie und die Informationsversorger der Mathematik, insbesondere die wissenschaftlichen Verlage, die TIB Hannover, die Bibliotheken der Universit{\"a}ten und \mbox{-- nicht zuletzt --} das FIZ Karlsruhe mit dem Zentralblatt f{\"u}r Mathematik. \noindent Auf der technischen Grundlage des Internet und seiner weltweit verbreiteten Informationsdienste (Gopher, WAIS, WorldWideWeb, Hyper-G, ftp und E-mail) soll ein verteiltes, mathematisches Informationssystem geschaffen werden, bei dem die Partner des gemeinsamen Vorhabens ihre {\"o}rtlichen Ressourcen untereinander und zugleich weltweit verf{\"u}gbar machen. Diese Ziele sind durch konsequenten Einsatz von Software erreichbar, die nach dem Client-Server-Modell strukturiert und die im Internet verbreitet bzw.~anerkannt ist. \noindent Die Bereitstellung von Technik reicht keineswegs aus. Ohne die Schaffung einer personellen, organisatorischen und technischen Infrastruktur ist die Durchf{\"u}hrung eines solchen Projekts nicht m{\"o}glich. Als Massnahmen sind - f{\"u}r alle Partner - geplant: \hspace*{2mm} * Schaffung der Funktion des Informationsbeauftragten \hspace*{2mm} * Einrichtung eines gemeinsamen ``Forums f{\"u}r mathematische Information'' \hspace*{2mm} * Errichtung und Betreuung von mathematischen Informationsstationen \hspace*{2mm} * Teilnahme an nationalen und internationalen Standardisierungsmassnahmen \hspace*{2mm} * Workshops und regelm{\"a}ssige Schulungen, {\"O}ffentlichkeitsarbeit \noindent Als Aktivit{\"a}ten - mit Focus auf mathematische Fachinformation - sind folgende Teilaufgaben und Pilotvorhaben bei allen Partnern geplant: \hspace*{2mm} * Einrichtung von elektronischen Informationssystemen \hspace*{2mm} * Verteiltes elektronisches Angebot von Preprints und Skripten (Volltexte) \hspace*{2mm} * Verteiltes elektronisches Angebot von Software- und Datensammlungen \hspace*{2mm} * Zugriff auf globale Informationssysteme in der Mathematik \hspace*{2mm} * Organisation eines Lebenden Mathematischen Museums \hspace*{2mm} * Zugriff auf elektronische Kataloge von Bibliotheken, insbesondere Fachbereichsbibliotheken \hspace*{2mm} * Schaffung eines organisatorischen Rahmens f{\"u}r elektronische mathematische Journale \hspace*{2mm} * Elektronisches Angebot von eingescannten historischen Dokumenten und B{\"u}chern \hspace*{2mm} * Schaffung einer Organisationsform f{\"u}r elektronisches Reviewing \hspace*{2mm} * Erprobung von Verfahren zur elektronischen Lieferung von Dokumenten \hspace*{2mm} * Elektronische Projektorganisation \noindent Das Vorhaben zielt ab auf die Schaffung einer informationstechnischen Infrastruktur f{\"u}r Datenbank-Retrieval, E-mail, ``Electronic Conferencing'' und fachspezifische Informationsnetze in exemplarischer Form f{\"u}r Wissenschaft und Industrie - auch f{\"u}r andere Fachgebiete.}, language = {de} } @misc{DalitzGroetschelLueggeretal.1994, author = {Dalitz, Wolfgang and Gr{\"o}tschel, Martin and L{\"u}gger, Joachim and Sperber, Wolfram}, title = {New Perspectives of a Distributed Information System for Mathematics.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5139}, number = {TR-94-08}, year = {1994}, abstract = {\begin{footnotesize} \noindent Combining electronic specialized information, such as electronic information retrieval from central databases, with the new means of communication opens up new perspectives for mathematics in Germany. Based on the current Fachinformationsprojekt (Specialized Information Project) run by the Deutsche Mathematiker-Vereinigung (DMV) and supported by the Federal Minister for Research and Technology (BMFT), the DMV is planning a new infrastructure activity for mathematics. This activity will not only include mathematical university departments and research institutes, but also partners from mathematical research laboratories in industry as well as suppliers of mathematical information, in particular, scientific publishing houses, the Technical Information Library (TIB) Hannover, university libraries and -- last but not least -- the Fachinformationszentrum (FIZ) Karlsruhe with the Zentralblatt f{\"u}r Mathematik. \noindent On the technical basis of the Internet and its worldwide information services (Gopher, WAIS, World Wide Web, Hyper-G, ftp and e-mail), a distributed mathematical information system is to be created, whose partners make their local resources available both to other partners and to the worldwide Internet community. These aims can be achieved by means of the consequent use of software that is structured according to the client-server model and distributed and accepted within the Internet. \noindent Providing the technical equipment, however, is by far not enough. Without the creation of a personal, technical and organizational infrastructure, realization of such a project will not be possible. For every partner the realization of the following measures is envisaged:\\[-7mm] \noindent \end{footnotesize} \begin{small} \begin{itemize} \item[*] Establishing an Information Coordinator\/ at every participating institution\\[-8mm] \item[*] Creation of a Forum for Mathematical Information\/\\[-8mm] \item[*] Installation and maintenance of Mathematical Information Stations\/\\[-8mm] \item[*] Participation in national and international Standardization Activities\/\\[-8mm] \item[*] Regular workshops and training courses, public relations\\[-7mm] \end{itemize} \noindent The following activities (carried out by all partners or within pilot projects by special groups) focusing on mathematical and mathematics-related information are planned:\\[-7mm] \noindent \begin{itemize} \item[*] Set up of Electronic Information Systems\/ by all partners \\[-8mm] \item[*] Distributed\/ electronic offer of Preprints\/ and scripts (full texts) by all partners\\[-8mm] \item[*] Distributed\/ electronic offer of Software and Data Collections\/ by all partners\\[-8mm] \item[*] Access to Global Information Systems in Mathematics\/\\[-8mm] \item[*] Organization of a Living Museum of Mathematics\/\\[-8mm] \item[*] Access to {\it Electronic Library Catalogs,}\/ esp.~to libraries of university departments\\[-8mm] \item[*] Electronic offer of Scanned Historical Books and Documents\/\\[-8mm] \item[*] Creation and management of Electronic Mathematical Journals\/\\[-8mm] \item[*] Creation of a framework for various kinds of Electronic Reviewing\/\\[-8mm] \item[*] Testing of new methods for Electronic Document Delivery\/\\[-8mm] \item[*] Electronic Project Organization\/\\[-7mm] \end{itemize} \noindent \end{small} \begin{footnotesize} The project aims, at its beginning, at the creation of an information infrastructure for database retrieval, e-mail, electronic conferencing and subject-specific information networks. Its focus is on mathematics in Germany. The general scope, however, is broader. The project is open for discussion, coordination, and cooperation with partners in other areas of science, industry or in other countries. It is also hoped that this project may form an example along which other models of electronic information and communication can be developed. Moreover, the project is also meant to enhance the offer from German mathematics to the worldwide "give and take" within the Internet community. \end{footnotesize}}, language = {en} } @misc{Melenk1994, author = {Melenk, Herbert}, title = {The Complexity Barrier in REDUCE - a Case Study.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5119}, number = {TR-94-06}, year = {1994}, abstract = {The power of the symbolic math system {\small REDUCE} for solving large and difficult problems in science and engineering is demonstrated by a set of model problems. These include algebraic equation solving, formal variable elimination, formal power series, symbolic treatment of differential equations and applications from theoretical physics.}, language = {en} } @phdthesis{Schuette1994, author = {Sch{\"u}tte, Christof}, title = {A Quasiresonant Smoothing Algorithm for Solving Large Highly Differential Equations from Quantum Chemistry.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5090}, number = {TR-94-04}, year = {1994}, abstract = {In Quantum Chemistry the field of Laser--Assisted Molecular Control'' has received a considerable amount of attention recently. One key problem in this new field is the simulation of the dynamical reaction of a molecule subjected to external radiation. This problem is described by the Schr{\"o}dinger equation, which, after eigenfunction expansion, can be written in the form of a large system of ordinary differential equations, the solutions of which show a highly oscillatory behaviour. The oscillations with high frequencies and small amplitudes confine the stepsizes of any numerical integrator -- an effect, which, in turn, blows up the simulation time. Larger stepsizes can be expected by averaging these fast oscillations, thus smoothing the trajectories. Standard smoothing techniques (averaging, filtering) would kill the whole process and thus, lead to wrong numerical results. To avoid this unwanted effect and nevertheless speed up computations, this paper presents a quasiresonant smoothing algorithm (QRS). In QRS, a natural splitting parameter \$\delta\$ controls the smoothing properties. An adaptive QRS--version (AQRS) is presented which includes an error estimation scheme for choosing this parameter \$\delta\$ in order to meet a given accuracy requirement. In AQRS \$\delta\$ is permanently adapted to the solution properties for computing the chemically necessary information'' only. The performance of AQRS is demonstrated in several test problems from the field Laser--Assisted Selective Excitation of Molecules'' in which the external radiation is a picosecond laser pulse. In comparison with standard methods speedup factors of the order of \$10^2\$ are observed.}, language = {en} } @misc{Zumbusch1994, author = {Zumbusch, Gerhard}, title = {Visualizing Functions of the h-p-version of finite elements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5108}, number = {TR-94-05}, year = {1994}, abstract = {Results from finite-element-calculations are usually visualized by colored surface- and contour-line-plots or polygonal patches or simply displaced lines and grids. In computer graphics however more advanced techniques like texture-mapping and NURBS are well established and there exist efficient algorithms and implementations. We show that these techniques are not only easy to use, but form a very natural and far more efficient approach for visualization of higher order finite-element's solutions like in \$p\$- and \$h\$-\$p\$-version. Texture-mapping is useful for displaying vector-valued data, too.}, language = {en} } @misc{Weismantel1994, author = {Weismantel, Robert}, title = {Hilbert Bases and the Facets of Special Knapsack Polytopes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1475}, number = {SC-94-19}, year = {1994}, abstract = {{\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set \$N\$ of items, a capacity \$F \in \N\$ and weights \$a_i \in \N\$, \$i \in N\$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality \$\$\sum_{i \in N} a_i x_i \leq F.\$\$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where \$a_i \in \{\mu,\lambda\}\$ for all items \$i \in N\$ and \$1 \leq \mu < \lambda \leq b\$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.}}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1450}, number = {SC-94-16}, year = {1994}, abstract = {We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {The Node Capacitated Graph Partitioning Problem: A Computational Study.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1469}, number = {SC-94-17}, year = {1994}, abstract = {In this paper we consider the problem of \$k\$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design.}, language = {en} } @misc{Froehlich1994, author = {Fr{\"o}hlich, Jochen}, title = {Parameter Derivatives of the Jacobi Polynomials and the Gaussian Hypergeometric Function.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1440}, number = {SC-94-15}, year = {1994}, abstract = {The paper's main result is a simple derivation rule for the Jacobi polynomials with respect to their parameters, i.e. for \$\partial_{\alpha} P_n^{\alpha,\beta}\$, and \$\partial_{\beta} P_n^{\alpha,\beta}\$. It is obtained via relations for the Gaussian hypergeometric function concerning parameter derivatives and integer shifts in the first two arguments. These have an interest on their own for further applications to continuous and discrete orthogonal polynomials. The study is motivated by a Galerkin method with moving weight, presents all proofs in detail, and terminates in a brief discussion of the generated polynomials.}, language = {en} } @misc{AbdelHamidBorndoerfer1994, author = {Abdel-Hamid, Atef Abdel-Aziz and Bornd{\"o}rfer, Ralf}, title = {On the Complexity of Storage Assignment Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1430}, number = {SC-94-14}, year = {1994}, abstract = {{\def\NP{\hbox{\$\cal N\kern-.1667em\cal P\$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be \$\NP\$-hard in the strong sense. We show that the storage assignment problem is \$\NP\$-hard for {\sl bounded sizes and capacities}, even if the sizes have values \$1\$ and~\$2\$ and the capacities value~\$2\$ only, a case we encountered in practice. Moreover, we prove that no polynomial time \$\epsilon\$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}}, language = {en} } @misc{Lang1994, author = {Lang, Jens}, title = {High-Resolution Selfadapative Computations on Chemical Reaction-Diffusion Problems with Internal Boundaries}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1395}, number = {SC-94-09}, year = {1994}, abstract = {Large chemical computations show the need for full adaptivity supporting the development of robust and highly efficient programs. For solutions possessing sharp moving spatial transitions, as travelling wavefronts or emerging boundary and internal layers, an automatic adjustment of both the space and the time stepsize is generally accepted to be more successful in efficient resolving critical regions of high spatial and temporal activity. In contrast to the widespread discretization sequence first space then time the reversed sequence first time then space is employed. Full adaptivity of the proposed algorithm is realized by combining embedded time discretization and multilevel finite element space discretization. In this paper the algorithm is described for one--dimensional problems. The numerical results show the significantly new perspectives opened by this approach.}, language = {en} } @misc{Gatermann1994, author = {Gatermann, Karin}, title = {Semi-invariants, equivariants and algorithms.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1411}, number = {SC-94-11}, year = {1994}, abstract = {The results from invariant theory and the results for semi-invariants and equivariants are summarized in a way suitable for the combination with Gr{\"o}bner basis computation. An algorithm for the determination of fundamental equivariants using projections and a Poincar\'{e} series is described. Secondly, an algorithm is given for the representation of an equivariant in terms of the fundamental equivariants. Several ways for the exact determination of zeros of equivariant systems are discussed}, language = {en} } @misc{WulffHohmannDeuflhard1994, author = {Wulff, Claudia and Hohmann, Andreas and Deuflhard, Peter}, title = {Numerical Continuation of Periodic Orbits with Symmetry.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1421}, number = {SC-94-12}, year = {1994}, abstract = {We consider periodic orbits of autonomous parameter dependent ODE's. Starting from a shooting algorithm for the numerical computation of periodic orbits via an adaptive Poincar\'e-section we develop a pathfollowing algorithm for periodic solutions based on a tangential continuation method with implicit reparametrization. For ODE's equivariant w.r.t. a finite group we show that spatial as well as spatio-temporal symmetries of periodic orbits can be exploited within the (multiple) shooting context. We describe how turning points, period doubling bifurcations and Hopf points along the branch of periodic solutions can be handled. Furthermore equivariant Hopf points and generic secondary bifurcations of periodic orbits with \$ Z_m\$-symmetry are treated. We tested the code with standard examples, e.g., the period doubling cascade in the Lorenz equations. To show the efficiency of the described methods we also used the program for an application from electronics, a ring oscillator with \$n \$ inverters. In this example the exploitation of symmetry reduces the amount of work for the continuation of periodic orbits from \${\cal O}(n^2)\$ to \${\cal O}(n)\$}, language = {en} } @misc{Koepf1994, author = {Koepf, Wolfram}, title = {On Families of Iterated Derivatives.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5083}, number = {TR-94-03}, year = {1994}, abstract = {We give an overview of an approach on special functions due to Truesdell, and show how it can be used to develop certain type of identities for special functions. Once obtained, these identities may be verified by an independent algorithmic method for which we give some examples.}, language = {en} } @misc{AckermannErdmannRoitzsch1994, author = {Ackermann, J{\"o}rg and Erdmann, Bodo and Roitzsch, Rainer}, title = {A self-adaptive multilevel finite element method for the stationary Schr{\"o}dinger equation in three space dimensions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1403}, number = {SC-94-10}, year = {1994}, abstract = {An error controlled finite elemente method (FEM) for solving stationary Schr{\"o}dinger equations in three space dimensions is proposed. The method is based on an adaptive space discretization into tetrahedra and local polynomial basis functions of order \$p=1\$--\$5\$ defined on these tetrahedra. According to a local error estimator the triangulation is automatically adapted to the solution. Numerical results for standard problems appearing in vibrational motion and molecular structure calculations are presented and discussed. Relative precisions better than 1e-8 are obtained. For equilateral H\$_3^{++}\$ the adaptive FEM turns out to be superior to global basis set expansions in the literature. Our precise FEM results exclude in a definite manner the stability or metastability of equilateral H\$_3^{++}\$ in its groundstate.}, language = {en} } @misc{Bornemann1994, author = {Bornemann, Folkmar A.}, title = {On the Convergence of Cascadic Iterations for Elliptic Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1389}, number = {SC-94-08}, year = {1994}, abstract = {We consider nested iterations, in which the multigrid method is replaced by some simple basic iteration procedure, and call them {\em cascadic iterations}. They were introduced by Deuflhard, who used the conjugate gradient method as basic iteration (CCG method). He demonstrated by numerical experiments that the CCG method works within a few iterations if the linear systems on coarser triangulations are solved accurately enough. Shaidurov subsequently proved multigrid complexity for the CCG method in the case of \$H^2\$-regular two-dimensional problems with quasi-uniform triangulations. We show that his result still holds true for a large class of smoothing iterations as basic iteration procedure in the case of two- and three-dimensional \$H^{1+\alpha}\$-regular problems. Moreover we show how to use cascadic iterations in adaptive codes and give in particular a new termination criterion for the CCG method.}, language = {en} } @misc{GaertnerZiegler1994, author = {G{\"a}rtner, Bernd and Ziegler, G{\"u}nter M.}, title = {Randomized simplex algorithms on Klee-Minty cubes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1370}, number = {SC-94-07}, year = {1994}, abstract = {We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes and similar linear programs with exponential decreasing paths. The analysis of two randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds conjectured in the literature. At the same time, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.}, language = {en} } @misc{Linusson1994, author = {Linusson, Svante}, title = {Partitions with Restricted Block Sizes, M{\"o}bius Functions and the k-of-each Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1363}, number = {SC-94-06}, year = {1994}, abstract = {{\newcommand{\R} {{\rm {\mbox{\protect\makebox[.15em][l]{I}R}}}} Given a list of \$n\$ numbers in \$\R \$, one wants to decide wether every number in the list occurs at least \$k\$ times. I will show that \$(1-\epsilon)n\log_3(n/k)\$ is a lower bound for the depth of a linear decision tree determining this problem. This is done by using the Bj{\"o}rner-Lov\'asz method, which turns the problem into one of estimating the M{\"o}bius function for a certain partition lattice. I will also calculate the exponential generating function for the M{\"o}bius function of a partition poset with restricted block sizes in general.}}, language = {en} } @misc{Hohmann1994, author = {Hohmann, Andreas}, title = {Object Oriented Design of Multilevel Newton and Continuation Methods.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1342}, number = {SC-94-04}, year = {1994}, abstract = {We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework. \\{\bf Abstract: }We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework.}, language = {en} } @misc{Koepf1994, author = {Koepf, Wolfram}, title = {Algorithmic work with orthogonal polynomials and special functions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1354}, number = {SC-94-05}, year = {1994}, abstract = {In this article we present a method to implement orthogonal polynomials and many other special functions in Computer Algebra systems enabling the user to work with those functions appropriately, and in particular to verify different types of identities for those functions. Some of these identities like differential equations, power series representations, and hypergeometric representations can even dealt with algorithmically, i.\ e.\ they can be computed by the Computer Algebra system, rather than only verified. The types of functions that can be treated by the given technique cover the generalized hypergeometric functions, and therefore most of the special functions that can be found in mathematical dictionaries. The types of identities for which we present verification algorithms cover differential equations, power series representations, identities of the Rodrigues type, hypergeometric representations, and algorithms containing symbolic sums. The current implementations of special functions in existing Computer Algebra systems do not meet these high standards as we shall show in examples. They should be modified, and we show results of our implementations.}, language = {en} } @misc{KoepfSchmersau1994, author = {Koepf, Wolfram and Schmersau, Dieter}, title = {Spaces of Functions Satisfying Simple Differential Equations.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5074}, number = {TR-94-02}, year = {1994}, abstract = {{\newcommand{\N} {{\rm {\mbox{\protect\makebox[.15em][l]{I}N}}}} In several publications the first author published an algorithm for the conversion of analytic functions for which derivative rules are given into their representing power series \$\sum\limits_{k=0}^{\infty}a_{k}z^{k}\$ at the origin and vice versa, implementations of which exist in {\sc Mathematica}, {\sc Maple} and {\sc Reduce}. One main part of this procedure is an algorithm to derive a homogeneous linear differential equation with polynomial coefficients for the given function. We call this type of ordinary differential equations {\sl simple}. Whereas the opposite question to find functions satisfying given differential equations is studied in great detail, our question to find differential equations that are satisfied by given functions seems to be rarely posed. In this paper we consider the family \$F\$ of functions satisfying a simple differential equation generated by the rational, the algebraic, and certain transcendental functions. It turns out that \$F\$ forms a linear space of transcendental functions. \% with polynomial function coefficients. Further \$F\$ is closed under multiplication and under the composition with rational functions and rational powers. These results had been published by Stanley who had proved them by theoretical algebraic considerations. In contrast our treatment is purely algorithmically oriented. We present algorithms that generate simple differential equation for \$f+g\$, \$f\cdot g\$, \$f\circ r\$ (\$r\$ rational), and \$f\circ x^{p/q}\$ (\$p,q\in\N_0\$), given simple differential equations for \$f\$, and \$g\$, and give a priori estimates for the order of the resulting differential equations. We show that all order estimates are sharp. After finishing this article we realized that in independent work Salvy and Zimmermann published similar algorithms. Our treatment gives a detailed description of those algorithms and their validity.}}, language = {en} } @misc{VerscheldeGatermann1994, author = {Verschelde, Jan and Gatermann, Karin}, title = {Symmetric Newton Polytopes for Solving Sparse Polynomial Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1331}, number = {SC-94-03}, year = {1994}, abstract = {The aim of this paper is to compute all isolated solutions to symmetric polynomial systems. Recently, it has been proved that modelling the sparse structure of the system by its Newton polytopes leads to a computational breakthrough in solving the system. In this paper, it will be shown how the Lifting Algorithm, proposed by Huber and Sturmfels, can be applied to symmetric Newton polytopes. This symmetric version of the Lifting Algorithm enables the efficient construction of the symmetric subdivision, giving rise to a symmetric homotopy, so that only the generating solutions have to be computed. Efficiency is obtained by combination with the product homotopy. Applications illustrate the practical significance of the presented approach.}, language = {en} } @misc{DeuflhardHegeSedlmayred1994, author = {Deuflhard, Peter and Hege, Hans-Christian and Sedlmayr(ed.), E.}, title = {Scientific Computing in der Theoretischen Physik. Collected Abstracts.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5068}, number = {TR-94-01}, year = {1994}, abstract = {Die von der DMV-Fachgruppe Scientific Computing in Kooperation mit dem gleichnamigen GAMM-Fachausschuss organisierte Tagung \glqq Scientific Computing in der Theoretischen Physik\grqq~fand vom 16. - 18. M{\"a}rz 1994 am Fachbereich Mathematik und Informatik der Freien Universit{\"a}t Berlin statt. Ziel des Workshops war, die Kontakte zwischen den Fachleuten der Gebiete {\em Computational Physics} und {\em Scientific Computing} zu intensivieren. Schwerpunkte des Workshops waren numerische Simulation von Transportmodellen der Astrophysik und Halbleiterphysik, Multilevel-Methoden f{\"u}r partielle Differentialgleichungen sowie Monte-Carlo-Methoden und molekulardynamische Verfahren f{\"u}r Probleme der Statistischen Physik und Quantenfeldtheorie. Der Workshop fand ein {\"a}usserst positives Echo und f{\"u}hrte {\"u}ber 70 Teilnehmer der verschiedenen Teilgebiete der Theoretischen Physik und ca. 50 Teilnehmer aus dem Bereich der Numerischen Mathematik zusammen. \originalTeX}, language = {en} } @misc{SeebassSullivanWustetal.1994, author = {Seebass, Martin and Sullivan, Dennis and Wust, Peter and Deuflhard, Peter and Felix, Roland}, title = {The Berlin Extension of the Stanford Hyperthermia Treatment.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1304}, number = {SC-93-35}, year = {1994}, abstract = {In the field of deep regional hyperthermia, one of the most widely used devices is the BSD--2000 Hyperthermia System which employs the Sigma 60 applicator. The Sigma 60 consists of four independent sources, giving it the potential to control the energy pattern within the patient. The independent amplitudes and phases, as well as frequency selection and applicator position, present a large number of parameters for the operator to determine. Computer simulation has long been recognized as an attractive approach to optimizing these parameters. A treatment planning program was used in clinical practice at Stanford University Medical Center for two years. It demonstrated the feasibility of computer simulation for deep regional hyperthermia in a clinical situation. However, several parts of this system were written in a language specific to one workstation, which severely restricted the wider distribution of the program to other users of the Sigma 60. A new treatment planning system for the BSD 2000 has been developed and put into clinical practice at the Rudolf Virchow Clinic of the Free University of Berlin. The new method, which we will refer to as the Berlin system, has a simpler model construction program and a considerably better graphics capability. However, the most important feature is that all programs are written in FORTRAN, C, or the X Window graphics system. Therefore, the entire treatment planning system is completely portable to other workstations.}, language = {en} } @misc{Weismantel1994, author = {Weismantel, Robert}, title = {On the 0/1 Knapsack Polytope.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1312}, number = {SC-94-01}, year = {1994}, abstract = {{\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set \$N\$ of items and a capacity \$b \in \N\$, and let \$N_j\$ be the set of items with weight \$j\$, \$1 \leq j \leq b\$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality \$\$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.\$\$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) \$N_j = \emptyset\$ for all \$1 < j \leq \lfloor {b \over 2} \rfloor\$ and (b) \$N_j = \emptyset\$ for all \$1 < j \leq \lfloor {b \over 3} \rfloor\$ and \$N_j = \emptyset\$ for all \$j \geq \lfloor {b \over 2} \rfloor + 1\$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.}}, language = {en} } @misc{GroetschelMartinWeismantel1994, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {The Steiner Tree Packing Problem in VLSI-Design.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1328}, number = {SC-94-02}, year = {1994}, abstract = {In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.}, language = {en} } @misc{GroetschelPadberg1994, author = {Gr{\"o}tschel, Martin and Padberg, Manfred}, title = {Ulysses 2000: In Search of Optimal Solutions to Hard Combinatorial Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1296}, number = {SC-93-34}, year = {1994}, abstract = {Combinatorial optimization problems pervade many areas of human problem solving especially in the fields of business, economics and engineering. Intensive mathematical research and vast increases in raw computing power have advanced the state of the art in exact and heuristic problem solving at a pace that is unprecedented in human history. We survey here in layman's terms some of the fundamental concepts and principles that have led this progress. (This article will appear -- possibly in modified form -- in a popular science magazine.)}, language = {en} } @phdthesis{Nowak1993, author = {Nowak, Ulrich}, title = {Adaptive Linienmethoden f{\"u}r nichtlineare parabolische Systeme in einer Raumdimension.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5059}, number = {TR-93-14}, year = {1993}, abstract = {A new method for the numerical solution of highly nonlinear, coupled systems of parabolic differential equations in one space dimension is presented. The approach is based on a classical method of lines treatment. Time discretization is done by means of the semi--implicit Euler discretization. Space discretization is done with finite differences on non--uniform grids. Both basic discretizations are coupled with extrapolation techniques. With respect to time the extrapolation is of variable order whereas just one extrapolation step is done in space. 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. Besides the local adaptation of the space grids after each integration step (static regridding), the grid may even move within each integration step (dynamic regridding). Thus, the whole algorithm has a high degree of adaptivity. Due to this fact, challenging problems from applications can be solved in an efficient and robust way.}, language = {en} } @misc{Bornemann1993, author = {Bornemann, Folkmar A.}, title = {Interpolation Spaces and Optimal Multilevel Preconditioners.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1285}, number = {SC-93-33}, year = {1993}, abstract = {This paper throws light on the connection between the optimal condition number estimate for the BPX method and constructive approximation theory. We provide a machinery, which allows to understand the optimality as a consequence of an approximation property and an inverse inequality in \$H^{1+\epsilon}\$, \$\epsilon > 0\$. This machinery constructs so-called {\em approximation spaces}, which characterize a certain rate of approximation by finite elements and relates them with interpolation spaces, which characterize a certain smoothness.}, language = {en} } @misc{Zumbusch1993, author = {Zumbusch, Gerhard}, title = {Symmetric Hierarchical Polynomials for the h-p-Version of Finite Elements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1275}, number = {SC-93-32}, year = {1993}, abstract = {Adaptive numerical methods using the \$h\$-\$p\$-version of finite elements require special kinds of shape functions. Desirable properties of them are symmetry, hierarchy and simple coupling. In a first step it is demonstrated that for standard polynomial vector spaces not all of these features can be obtained simultaneously. However, this is possible if these spaces are extended. Thus a new class of polynomial shape functions is derived, which is well-suited for the \$p\$- and \$h\$-\$p\$-version of finite elements on unstructured simplices. The construction is completed by minimizing the condition numbers of the arising finite element matrices. The new shape functions are compared with standard functions widely used in the literature.}, language = {en} } @phdthesis{Hohmann1993, author = {Hohmann, Andreas}, title = {Inexact Gauss Newton Methods for Parameter Dependent Nonlinear Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5049}, number = {TR-93-13}, year = {1993}, abstract = {A new approach to inexact Gauss Newton methods for the solution of underdetermined nonlinear problems is presented. It is based on a convergence theorem being invariant under affine transformations of the domain and results in an easily implementable accuracy matching strategy for the arising linear subproblems which guarantees the quadratic convergence. Thanks to the weak assumptions on the given nonlinear problem, the results provide a general framework for multilevel Newton and continuation methods. As an example, a new multilevel Newton h-p collocation method for boundary value problems of ordinary differential equations is developed. It combines the inexact Newton method with a linear collocation solver using adaptive refinement and variable orders. The performance of the resulting C++ class library {\sc Cocon} is demonstrated by some numerical examples including singular perturbed problems. In addition, the new method is applied to a realistic railway bogie model in which a branch of periodic solutions emanates from a branch of fixed points at a Hopf bifurcation.}, language = {en} } @misc{GruntzKoepf1993, author = {Gruntz, Dominik and Koepf, Wolfram}, title = {Formal Power Series.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1267}, number = {SC-93-31}, year = {1993}, abstract = {{\newcommand{\C}{{\rm {\mbox{C{\llap{{\vrule height1.52ex}\kern.4em}}}}}} \newcommand{\Z} {{\rm {\mbox{\protect\makebox[.2em][l]{\sf Z}\sf Z}}}} \newcommand{\Maple}{{\sc Maple}} Formal Laurent-Puiseux series of the form \[ f(x)=\sum\limits_{k=k_0}^{\infty}a_{k}x^{k/n} \label{eq:formalLPS} \] with coefficients \$a_{k}\in\C\;(k\in\Z)\$ are important in many branches of mathematics. \Maple\ supports the computation of {\em truncated\/} series with its {\tt series} command, and through the {\tt powerseries} package infinite series are available. In the latter case, the series is represented as a table of coefficients that have already been determined together with a function for computing additional coefficients. This is known as {\em lazy evaluation\/}. But these tools fail, if one is interested in an explicit formula for the coefficients \$a_k\$. In this article we will describe the \Maple\ implementation of an algorithm presented in several papers of the second author which computes an {\em exact\/} formal power series of a given function. This procedure will enable the user to reproduce most of the results of the extensive bibliography on series. We will give an overview of the algorithm and then present some parts of it in more detail. This package is available through the \Maple-share library with the name {\tt FPS}. We flavor this procedure with the following example. \%\begin{maple} \begin{verbatim}> FormalPowerSeries(sin(x), x=0);\end{verbatim} \begin{samepage} \begin{verbatim} infinity ----- k (2 k + 1) \ (-1) x ) ---------------- / (2 k + 1)! ----- k = 0 \end{verbatim} \end{samepage} }}, language = {en} } @misc{Zuse1993, author = {Zuse, Konrad}, title = {Cellular Structured Space (Rechnender Raum) and Physical Phenomena.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5039}, number = {TR-93-12}, year = {1993}, abstract = {The problem of nonlocal correlation and symmetry in space is of great importance in physical phenomena like the \underline{Einstein-Poloski-Rosen-Paradox} and others. It is shown that in Cellular Automata (Rechnender Raum) the structure of the space offers solutions for such problems.}, language = {en} } @misc{BornemannErdmannKornhuber1993, author = {Bornemann, Folkmar A. and Erdmann, Bodo and Kornhuber, Ralf}, title = {A Posteriori Error Estimates for Elliptic Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1257}, number = {SC-93-29}, year = {1993}, abstract = {{\def\enorm {\mathop{\mbox{\boldmath{\$|\!|\$}}}\nolimits} Let \$u \in H\$ be the exact solution of a given self--adjoint elliptic boundary value problem, which is approximated by some \$\tilde{u} \in {\cal S}\$, \$\cal S\$ being a suitable finite element space. Efficient and reliable a posteriori estimates of the error \$\enorm u - \tilde{u}\enorm \$, measuring the (local) quality of \$\tilde{u}\$, play a crucial role in termination criteria and in the adaptive refinement of the underlying mesh. A well--known class of error estimates can be derived systematically by localizing the discretized defect problem using domain decomposition techniques. In the present paper, we provide a guideline for the theoretical analysis of such error estimates. We further clarify the relation to other concepts. Our analysis leads to new error estimates, which are specially suited to three space dimensions. The theoretical results are illustrated by numerical computations.}}, language = {en} } @misc{GrammelHegeWunderling1993, author = {Grammel, Martin and Hege, Hans-Christian and Wunderling, Roland}, title = {On the Impact of Communication Latencies on Distributed Sparse LU Factorization.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1245}, number = {SC-93-28}, year = {1993}, abstract = {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.}, language = {en} } @misc{Koepf1993, author = {Koepf, Wolfram}, title = {A package on formal power series.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1231}, number = {SC-93-27}, year = {1993}, abstract = {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{\"o}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.}, language = {en} } @misc{GroetschelMartinWeismantel1993, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Noncrossing Case.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1225}, number = {SC-93-26}, year = {1993}, abstract = {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.}, language = {en} } @misc{RichterGebertZiegler1993, author = {Richter-Gebert, J{\"u}rgen and Ziegler, G{\"u}nter M.}, title = {Zonotopal Tilings and the Bohne-Dress Theorem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1212}, number = {SC-93-25}, year = {1993}, abstract = {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.}, language = {en} } @misc{DeuflhardSchmidt1993, author = {Deuflhard, Peter and Schmidt, Frank}, title = {Discrete Transparent Boundary Conditions for the Numerical Solution of Fresnel's Equation.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1205}, number = {SC-93-24}, year = {1993}, abstract = {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{\"o}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.}, language = {en} } @misc{DeuflhardBoellingBott1993, author = {Deuflhard, Peter and B{\"o}lling, Reinhard and Bott, Raoul H.}, title = {Materialien zur Euler-Vorlesung in Sanssouci.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5029}, number = {TR-93-10}, year = {1993}, abstract = {Aus dem Inhalt: Vorwort; Leonhard Euler - aus der Zeit seines Wirkens in Berlin; Introductory Remarks.}, language = {de} } @misc{Deuflhard1993, author = {Deuflhard, Peter}, title = {Cascadic Conjugate Gradient Methods for Elliptic Partial Differential Equations I. Algorithm and Numerical Results.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1197}, number = {SC-93-23}, year = {1993}, abstract = {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.}, language = {en} } @misc{Lang1993, author = {Lang, Jens}, title = {KARDOS - KAskade Reaction Diffusion One-dimensional System.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5019}, number = {TR-93-09}, year = {1993}, abstract = {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).}, language = {en} } @misc{DeuflhardAckermann1993, author = {Deuflhard, Peter and Ackermann, J{\"o}rg}, title = {Adaptive Discrete Galerkin-Methods for Macromolecular Processes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1180}, number = {SC-93-22}, year = {1993}, abstract = {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.}, language = {en} } @misc{StoerDahl1993, author = {Stoer, Mechthild and Dahl, Geir}, title = {A Polyhedral Approach to Multicommodity Survivable Network Design.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1162}, number = {SC-93-20}, year = {1993}, abstract = {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.}, language = {en} } @misc{KornhuberYserentant1993, author = {Kornhuber, Ralf and Yserentant, Harry}, title = {Multilevel Methods for Elliptic Problems on Domains not Resolved by the Coarse Grid.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1170}, number = {SC-93-21}, year = {1993}, abstract = {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.}, language = {en} } @misc{Kornhuber1993, author = {Kornhuber, Ralf}, title = {Monotone Multigrid Methods for Elliptic Variational Inequalities I.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1147}, number = {SC-93-18}, year = {1993}, abstract = {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.}, language = {en} } @misc{Kornhuber1993, author = {Kornhuber, Ralf}, title = {Monotone Multigrid Methods for Elliptic Variational Inequalities II.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1151}, number = {SC-93-19}, year = {1993}, abstract = {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.}, language = {en} } @misc{Hohmann1993, author = {Hohmann, Andreas}, title = {An Implementation of Extrapolation Codes in C++.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5009}, number = {TR-93-08}, year = {1993}, abstract = {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.}, language = {en} } @misc{DiaconicsSturmfels1993, author = {Diaconics, Persi and Sturmfels, Bernd}, title = {Algebraic Algorithms for Sampling from Conditional Distributions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1131}, number = {SC-93-17}, year = {1993}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1993, author = {Martin, Alexander and Weismantel, Robert}, title = {Packing Paths and Steiner Trees: Routing of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1113}, number = {SC-93-15}, year = {1993}, abstract = {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.}, language = {en} } @misc{GroetschelLovasz1993, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo}, title = {Combinatorial Optimization.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1098}, number = {SC-93-13}, year = {1993}, abstract = {This paper will appear as Chapter 28 of the forthcoming "Handbook on Combinatorics" (editors: R. Graham, M. Gr{\"o}tschel, L. Lovasz) to be published in 1994, by North-Holland.}, language = {en} } @misc{GatermannWerner1993, author = {Gatermann, Karin and Werner, Bodo}, title = {Secondary Hopf Bifurcation Caused by Steady-State Steady-State Mode Interaction.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1122}, number = {SC-93-16}, year = {1993}, abstract = {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.}, language = {en} } @misc{HegeHoellererStalling1993, author = {Hege, Hans-Christian and H{\"o}llerer, Tobias and Stalling, Detlev}, title = {Volume Rendering - Mathematicals Models and Algorithmic Aspects.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4994}, number = {TR-93-07}, year = {1993}, abstract = {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.}, language = {en} } @misc{SchuetteHohmannDinand1993, author = {Sch{\"u}tte, Christof and Hohmann, Andreas and Dinand, Manfred}, title = {Numerical Simulation of Relaxation Oscillations of Waveguide-Lasers.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1106}, number = {SC-93-14}, year = {1993}, abstract = {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).}, language = {en} } @misc{Ziegler1993, author = {Ziegler, G{\"u}nter M.}, title = {Lectures on Polytopes.}, number = {TR-93-06}, year = {1993}, abstract = {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.}, language = {en} } @misc{OPUS4-966, title = {Jahresbericht 1993}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9668}, number = {1993}, year = {1993}, language = {de} } @misc{OPUS4-968, title = {Jahresbericht 1992}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9686}, number = {1992}, year = {1993}, language = {de} } @misc{GroetschelLueggerSperber1993, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim and Sperber, Wolfram}, title = {Wissenschaftliches Publizieren und Elektronische Fachinformation im Umbruch: ein Situationsbericht aus der Sicht der Mathematik.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4966}, number = {TR-93-04}, year = {1993}, abstract = {In diesem Aufsatz geben wir einen Bericht {\"u}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{\"u}rlich auch in der Mathematik selber. Unser Artikel endet mit einigen weitreichenden (und einigen Lesern m{\"o}glicherweise spektakul{\"a}r erscheinenden) Vorschl{\"a}gen, die sowohl die Informationsanbieter (wie die Fachinformationszentren und Verlage), die {\"o}ffentlichen Geldgeber als auch die mathematischen Organisationen (wie z.~B.~ die DMV und die mathematischen Fachbereiche) betreffen. Um den gegenw{\"a}rtigen Zustand der elektronischen Fachinformation und unsere Gedanken zu diesem Thema ad{\"a}quat beschreiben zu k{\"o}nnen, pr{\"a}sentieren wir eine breit angelegte Situationsanalyse. Wir stellen den gegenw{\"a}rtigen Stand der technologischen Entwicklung im elektronischen Publizieren dar und skizzieren seine Auswirkungen. Wir beschreiben das Feld der Interessen und Kr{\"a}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{\"u}ndete und dann zum DMV-Projekt Fachinformation f{\"u}hrte, das der Anlass zur Abfassung dieses Artikels war. Wir skizzieren die gegenw{\"a}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{\"o}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}, language = {de} } @misc{AckermannRoitzsch1993, author = {Ackermann, J{\"o}rg and Roitzsch, Rainer}, title = {On a Two-Dimensional Multilevel Adaptive Finite Element Method for the Time-Independent Schr{\"o}dinger-Equation.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1086}, number = {SC-93-12}, year = {1993}, abstract = {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{\"o}dinger--eigenvalue problems. Numerical results for standard problems appearing in vibrational motion and molecular electronic structure calculations are given and discussed.}, language = {en} } @misc{ErdmannLangRoitzsch1993, author = {Erdmann, Bodo and Lang, Jens and Roitzsch, Rainer}, title = {Kaskade Manual - Version 2.0.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4970}, number = {TR-93-05}, year = {1993}, abstract = {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.}, language = {en} } @misc{ReinerZiegler1993, author = {Reiner, Victor and Ziegler, G{\"u}nter M.}, title = {Coxeter-associahedra.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1075}, number = {SC-93-11}, year = {1993}, abstract = {\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.}, language = {en} } @misc{LangendorfPaetsch1993, author = {Langendorf, Jens and Paetsch, Olaf}, title = {GRAZIL - Beschreibung der Version 6.0 des Plotpaketes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4930}, number = {TR-93-01}, year = {1993}, abstract = {GRAZIL ist ein interaktives Programmpaket zur grafischen Darstellung von zwei-dimensionalen Kurvenverl{\"a}ufen. Dem Benutzer stehen zahlreiche Kommandos und ein grafisches User-Interface zum Gestalten des Layouts der Zeichnung zur Verf{\"u}gung. Die Eingabedaten m{\"u}ssen dem GRAZIL-Eingabe-Format gen{\"u}gen. Somit wird eine hohe Flexibilit{\"a}t und eine gro\"se Bandbreite der Einsatzm{\"o}glichkeiten erreicht. GRAZIL wurde mit der grafischen Grundsoftware GKS entwickelt. Dadurch kann ein breites Rechner- und Ausgabeger{\"a}tespektrum genutzt werden.}, language = {de} } @misc{Schuette1993, author = {Sch{\"u}tte, Christof}, title = {A quasiresonant smoothing algorithm for the fast analysis of selective vibrational excitation.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1066}, number = {SC-93-10}, year = {1993}, abstract = {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{\"o}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.}, language = {en} } @misc{ErdmannHoppeKornhuber1993, author = {Erdmann, Bodo and Hoppe, Ronald H. W. and Kornhuber, Ralf}, title = {Adaptive Multilevel-Methods for Obstacle Problems in Three Space Dimensions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1049}, number = {SC-93-08}, year = {1993}, abstract = {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.}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Design of Survivable Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1054}, number = {SC-93-09}, year = {1993}, language = {en} } @misc{WeismantelFerreiraMartin1993, author = {Weismantel, Robert and Ferreira, Carlos E. and Martin, Alexander}, title = {A Cutting Plane Based Algorithm for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1031}, number = {SC-93-07}, year = {1993}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelKlostermeieretal.1993, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus-Disposition: Ein Konzept zur Serviceverbesserung bei gleichzeitiger Kostensenkung.[nur hausintern]}, number = {TR-93-03}, year = {1993}, abstract = {"`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums f{\"u}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{\"o}glichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX}, language = {de} } @misc{Deuflhard1993, author = {Deuflhard, Peter}, title = {A Study of Lanczos-Type Iterations for Symmetric Indefinite Linear Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1029}, number = {SC-93-06}, year = {1993}, abstract = {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.}, language = {en} } @misc{RichterGebert1993, author = {Richter-Gebert, J{\"u}rgen}, title = {Mechanical Theorem Proving in Projective Geometry.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1013}, number = {SC-93-05}, year = {1993}, abstract = {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.}}, language = {en} } @misc{FerreiraMartinWeismantel1993, author = {Ferreira, Carlos E. and Martin, Alexander and Weismantel, Robert}, title = {Facets for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1007}, number = {SC-93-04}, year = {1993}, abstract = {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.}, language = {en} } @misc{Melenk1993, author = {Melenk, Herbert}, title = {Algebraic Solution of Nonlinear Equation Systems in REDUCE.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4944}, number = {TR-93-02}, year = {1993}, abstract = {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{\"o}bner techniques in a black box manner. In addition to polynomials equations with surds, trigonometric functions and separable transcendental functions are covered.}, language = {en} } @misc{FerreiraGroetschelKiefletal.1993, author = {Ferreira, Carlos E. and Gr{\"o}tschel, Martin and Kiefl, Stefan and Krispenz, Ludwig and Martin, Alexander and Weismantel, Robert}, title = {Some Integer Programs Arising in the Design of Main Frame Computers.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-957}, number = {SC-92-25}, year = {1993}, abstract = {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.}, language = {en} } @misc{GroetschelMonmaStoer1993, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-944}, number = {SC-92-24}, year = {1993}, abstract = {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\$}}, language = {en} } @misc{GatermannWerner1992, author = {Gatermann, Karin and Werner, Bodo}, title = {Group Theoretical Mode Interactions with Different Symmetries.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-994}, number = {SC-93-03}, year = {1992}, abstract = {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.}, language = {en} } @misc{OPUS4-492, title = {Handbuch zur Visualisierung am ZIB}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4920}, number = {TR-92-07}, year = {1992}, abstract = {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.}, language = {de} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in Grid Graphs by Cutting Planes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-967}, number = {SC-92-26}, year = {1992}, abstract = {{\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.}}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Further Facets.}, doi = {10.1006/eujc.1996.0004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-975}, number = {SC-93-01}, year = {1992}, abstract = {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.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Separation Algorithms.}, doi = {10.1137/S0895480193258716}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-984}, number = {SC-93-02}, year = {1992}, abstract = {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.}, language = {en} } @misc{GroetschelMonmaStoer1992, author = {Gr{\"o}tschel, Martin and Monma, Clyde and Stoer, Mechthild}, title = {A Polyhedral Approach to Network Connectivity Problems (Extended Abstract).}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-924}, number = {SC-92-22}, year = {1992}, abstract = {We present a polyhedral approach for the general problem of designing a minimum-cost network with specified connectivity requir}, language = {en} } @misc{Chu1992, author = {Chu, Nguyen Ngoc}, title = {An Algorithm for Optimizing a Linear Function over the Integer Efficient Set.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-930}, number = {SC-92-23}, year = {1992}, abstract = {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.}, language = {en} } @misc{GroetschelLueggerSperber1992, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim and Sperber, Wolfram}, title = {Elektronische Fachinformation im Bereich der Mathematik an Hochschulen und Statusbericht zum DMV-Projekt. "Fachinformation".}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4910}, number = {TR-92-06}, year = {1992}, abstract = {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{\"u}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{\"o}gerlich vonstatten. Die Gr{\"u}nde daf{\"u}r werden in einer vom Bundesminister f{\"u}r Forschung und Technologie (BMFT) initiierten Studie analysiert. Ein k{\"u}rzlich von der Deutschen Mathematiker - Vereinigung begonnenes und vom BMFT gef{\"o}rdertes Vorhaben hat die "Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online-Datenbanken und CD-ROM f{\"u}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{\"a}utern, mit denen den spezifischen Nutzungshemmnissen begegnet werden soll.}, language = {de} } @misc{Nowak1992, author = {Nowak, Ulrich}, title = {Dynamic Sparsing in Stiff Extrapolation Methods.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-911}, number = {SC-92-21}, year = {1992}, abstract = {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.}, language = {en} } @misc{Yang1992, author = {Yang, Shuli}, title = {Numerical Riemann solutions in multi-pieces for 2-D gas dynamics systems I. Contact discontinuities.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-903}, number = {SC-92-20}, year = {1992}, abstract = {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.}, language = {en} } @misc{Ziegler1992, author = {Ziegler, G{\"u}nter M.}, title = {Shellability of Chessboard Complexes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-890}, number = {SC-92-19}, year = {1992}, abstract = {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{\"o}rner \& Wachs.}, language = {en} } @misc{HohmannWulff1992, author = {Hohmann, Andreas and Wulff, Claudia}, title = {Modular Design of Extrapolation Codes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4909}, number = {TR-92-05}, year = {1992}, abstract = {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.}, language = {en} } @misc{Bornemann1992, author = {Bornemann, Folkmar A.}, title = {Adaptive Solution of One-Dimensional Scalar Conservation Laws with Convex Flux.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-880}, number = {SC-92-18}, year = {1992}, abstract = {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.}, language = {en} } @misc{Yang1992, author = {Yang, Shuli}, title = {MmB schemes on regular triangular meshes for 2-D conservation laws.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-873}, number = {SC-92-17}, year = {1992}, abstract = {In this paper, two classes of second order accurate high resolution schemes are presented on regular triangular meshes for initial value problem of two dimensional conservation laws. The first class are called Runge-Kutta-FVM MmB (locally Maximum- minimum Bounds preserving) schemes, which are first discretized by (FVM) finite volume method in space direction and modifying numerical fluxes, and then by Runge-Kutta methods in time direction; The second class, constructed by Taylor expansion in time, and then by FVM methods and making modifications to fluxes, are called Taylor- FVM MmB schemes. MmB properties of both schemes are proved for 2-D scalar conservation law. Numerical results are given for Riemann problems of 2-D scalar conservation law and 2-D gas dynamics systems and some comparisons are made between the two classes of the schemes. Key words and phrases: MmB schemes, 2-D, conservation laws, gas dynamics systems, Runge-Kutta-FVM, Taylor-FVM.}, language = {en} } @phdthesis{Weismantel1992, author = {Weismantel, Robert}, title = {Plazieren von Zellen: Theorie und L{\"o}sung eines quadratischen 0/1- Optimierungsproblems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4883}, number = {TR-92-03}, year = {1992}, abstract = {Die vorliegende Arbeit besch{\"a}ftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexit{\"a}tstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die L{\"o}sung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur L{\"o}sung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, besch{\"a}ftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gel{\"o}st werden k{\"o}nnen und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.}, language = {de} } @phdthesis{Martin1992, author = {Martin, Alexander}, title = {Packen von Steinerb{\"a}umen: Polyedrische Studien und Anwendung.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4894}, number = {TR-92-04}, year = {1992}, abstract = {Gegeben sei ein Graph \$G=(V,E)\$ mit positiven Kantenkapazit{\"a}ten \$c_e\$ und Knotenmengen \$T_1,\ldots,T_N\$. Das Steinerbaumpackungs-Problem besteht darin, Kantenmengen \$S_1,\ldots,S_N\$ zu finden, so da\ss\ jedes \$S_k\$ die Knoten aus \$T_k\$ verbindet und jede Kante \$e\$ in h{\"o}chstens \$c_e\$ Kantenmengen aus \$S_1,\ldots,S_N\$ vorkommt. Eine zul{\"a}ssige L{\"o}sung dieses Problems nennen wir eine Steinerbaumpackung. Ist zus{\"a}tzlich eine Gewichtung der Kanten gegeben und nach einer bez{\"u}glich dieser Gewichtung minimalen Steinerbaumpackung gesucht, so sprechen wir vom gewichteten Steinerbaumpackungs-Problem. Die Motivation zum Studium dieses Problems kommt aus dem Entwurf elektronischer Schaltungen. Ein dort auftretendes Teilproblem ist das sogenannte Verdrahtungsproblem, das im wesentlichen darin besteht, gegebene Punktmengen unter bestimmten Nebenbedingungen und Optimalit{\"a}tskriterien auf einer Grundfl{\"a}che zu verbinden. Wir studieren das Steinerbaumpackungs-Problem aus polyedrischer Sicht und definieren ein Polyeder, dessen Ecken genau den Steinerbaumpackungen entsprechen. Anschlie\ss end versuchen wir, dieses Polyeder durch gute'' beziehungsweise facetten-definierenden Ungleichungen zu beschreiben. Basierend auf diesen Ungleichungen entwickeln wir ein Schnittebenenverfahren. Die L{\"o}sung des Schnittebenenverfahrens liefert eine untere Schranke f{\"u}r die Optimall{\"o}sung und dient als Grundlage f{\"u}r die Entwicklung guter Primalheuristiken. Wir haben das von uns implementierte Schnittebenenverfahren an einem Spezialfall des Verdrahtungsproblems, dem sogenannten Switchbox-Verdrahtungsproblem, getestet und vielversprechende Ergebnisse erzielt.}, language = {de} } @misc{LeimkuhlerReich1992, author = {Leimkuhler, Benedict and Reich, Sebastian}, title = {The Numerical Solution of Constrained Hamiltonian Systems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-868}, number = {SC-92-16}, year = {1992}, abstract = {A Hamiltonian system subject to smooth constraints can typically be viewed as a Hamiltonian system on a manifold. Numerical computations, however, must be performed in \$ R^n\$. In this paper, canonical transformations from ``Hamiltonian differential--algebraic equations'' to ODEs in Euclidean space are considered. In \S2, canonical parameterizations or local charts are developed and it is shown how these can be computed in a practical framework. In \S3 we consider the construction of unconstrained Hamiltonian ODE systems in the space in which the constraint manifold is embedded which preserve the constraint manifold as an integral invariant and whose flow reduces to the flow of the constrained system along the manifold. It is shown that certain of these unconstrained Hamiltonian systems force Lyapunov stability of the constraint--invariants, while others lead to an unstable invariant. In \S4, we compare various projection techniques which might be incorporated to better insure preservation of the constraint--invariants in the context of numerical discretization. Numerical experiments illustrate the degree to which the constraint and symplectic invariants are maintained under discretization of various formulations. {\bf Keywords:} differential--algebraic equations, Hamiltonian systems, canonical discretization schemes. {\bf AMS(MOS):} subject classification 65L05.}, language = {en} } @misc{Moeller1992, author = {M{\"o}ller, H. Michael}, title = {On decomposing systems of polynomial equations with finitely many solutions.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-851}, number = {SC-92-15}, year = {1992}, abstract = {This paper deals with systems of \$m\$ polynomial equations in \$n\$ unknown, which have only finitely many solutions. A method is presented which decomposes the solution set into finitely many subsets, each of them given by a system of type \begin{displaymath} f_1(x_1)=0, f_2(x_1,x_2)=0,...,f_n(x_1,...,x_n)=0. \end{displaymath} The main tools for the decomposition are from ideal theory and use symbolical manipulations. For the ideal generated by the polynomials which describe the solution set, a lexicographical Gr{\"o}bner basis is required. A particular element of this basis allows the decomposition of the solution set. A recursive application of these decomposition techniques gives finally the triangular subsystems. The algorithm gives even for non-finite solution sets often also usable decompositions. {\bf Keywords:} Algebraic variety decomposition, Gr{\"o}bner bases, systems of nonlinear equations.}, language = {en} }