TY - GEN A1 - Huber, Birkett A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings N2 - In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos. T3 - ZIB-Report - SC-98-44 KW - Polyhedral subdivision KW - fiber polytope KW - mixed subdivision KW - lifting subdivision KW - Minkowski sum KW - Cayley Trick KW - Bohne-Dress Theorem Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3874 ER - TY - GEN A1 - Athanasiadis, Christos A. A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes II N2 - Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d < d' < n$. T3 - ZIB-Report - SC-98-43 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3862 ER - TY - GEN A1 - Decker, Ingmar T1 - A Picture-based Document Retrieval Service for the Electronic Visualization Library N2 - This report describes the development of an experimental service for picture-based document retrieval for the Electronic Visualization Library (EVlib). The EVlib is a digital library for scientific visualization, established at the Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB). The picture-based retrieval service allows users to look for documents by describing the pictures they contain. This query method was developed based on the assumption that (1) pictures often represent relevant parts of the contents of a document, and (2) pictures are often remembered well. A picture-based approach provides a new quality of accessing and exploring scientific literature. Motivation, concepts and realization of our service are outlined. Results of a user test are presented, too. The results indicate that this service can be used for searching and browsing the document collection in principle. On the other hand, problems were detected which can give fruitful hints for future work concerning document and image retrieval. T3 - ZIB-Report - TR-98-07 KW - information retrieval KW - image retrieval KW - digital library KW - picture memory KW - visualization KW - user interface Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5689 ER - TY - GEN A1 - Schütte, Christof A1 - Fischer, Alexander A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - A Direct Approach to Conformational Dynamics based on Hybrid Monte Carlo N2 - Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of $T$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted. T3 - ZIB-Report - SC-98-45 KW - conformation KW - conformational dynamics KW - hybrid Monte Carlo KW - reweighting KW - essential degrees of freedom KW - transition probabilities KW - Markov operator Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3889 ER - TY - GEN A1 - Wolf, Thomas T1 - A comparison of four approaches to the calculation of conservation laws N2 - The paper compares computational aspects of four approaches to compute conservation laws of single differential equations or systems of them, ODEs and PDEs. The only restriction, required by two of the four corresponding computer algebra programs, is that each DE has to be solvable for a leading derivative. Extra constraints may be given. Examples of new conservation laws include non-polynomial expressions, an explicit variable dependence and conservation laws involving arbitrary functions. Examples involve the following equations: Ito, Liouville, Burgers, Kadomtsev-Petviashvili, Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney. T3 - ZIB-Report - SC-99-01 Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3896 ER - TY - GEN A1 - Sokolov, Vladimir V. A1 - Wolf, Thomas T1 - A symmetry test for quasilinear coupled systems N2 - It is well known that the following class of systems of evolution equations \begin{eqnarray} \label{nsgen} \cases{ u_{t}=u_{xx}+F(u,v,u_x,v_x),\cr v_{t}=-v_{xx}+G(u,v,u_x,v_x),\cr} \end{eqnarray} is very rich in integrable cases. The complete classification problem is very difficult. Here we consider only the most interesting (from our opinion) subclass of systems (1). Namely, we consider equations linear in all derivatives of the form \begin{eqnarray} \label{kvazgen} \cases{ u_t = u_{xx} + A_{1}(u,v) u_x + A_{2}(u,v) v_x + A_{0}(u,v)\cr v_t = - v_{xx} + B_{1}(u,v) v_x + B_{2}(u,v) u_x + B_{0}(u,v). \cr} \end{eqnarray} without any restrictions on the functions $A_{i}(u,v), B_{i}(u,v)$. T3 - ZIB-Report - SC-99-02 Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3901 ER - TY - THES A1 - Friese, Tilmann T1 - Eine Mehrgitter-Methode zur Lösung des Eigenwertproblems der komplexen Helmholtzgleichung Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-1999000133 ER - TY - THES A1 - Borndörfer, Ralf T1 - Aspects of Set Packing, Partitioning, and Covering N2 - Diese Dissertation befaßt sich mit ganzzahligen Programmen mit 0/1 Systemen: SetPacking-, Partitioning- und Covering-Probleme. Die drei Teile der Dissertation behandeln polyedrische, algorithmische und angewandte Aspekte derartiger Modelle. Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10126 ER - TY - GEN A1 - Best, Christoph A1 - Hege, Hans-Christian T1 - Visualizing conformations in molecular dynamics N2 - The Monte Carlo simulation of the dynamics of complex molecules produces trajectories with a large number of different configurations to sample configuration space. It is expected that these configurations can be classified into a small number of conformations representing essential changes in the shape of the molecule. We present a method to visualize these conformations by point sets in the plane based on a geometrical distance measure between individual configurations. It turns out that different conformations appear as well-separated point sets. The method is further improved by performing a cluster analysis of the data set. The point-cluster representation is used to control a three-dimensional molecule viewer application to show individual configurations and conformational changes. The extraction of essential coordinates and visualization of molecular shape is discussed. T3 - ZIB-Report - SC-98-42 KW - Molecular Dynamics KW - Conformations KW - Visualization KW - Cluster Analysis Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3859 ER - TY - GEN A1 - Best, Christoph T1 - A simple C++ library for manipulating scientific data sets as structured data N2 - Representing scientific data sets efficiently on external storage usually involves converting them to a byte string representation using specialized reader/writer routines. The resulting storage files are frequently difficult to interpret without these specialized routines as they do not contain information about the logical structure of the data. Avoiding such problems usually involves heavy-weight data format libraries or data base systems. We present a simple C++ library that allows to create and access data files that store structured data. The structure of the data is described by a data type that can be built from elementary data types (integer and floating-point numbers, byte strings) and composite data types (arrays, structures, unions). An abstract data access class presents the data to the application. Different actual data file structures can be implemented under this layer. This method is particularly suited to applications that require complex data structures, e.g. molecular dynamics simulations. Extensions such as late type binding and object persistence are discussed. T3 - ZIB-Report - TR-98-06 KW - scientific file formats KW - structured data KW - object persistence Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5674 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Strubbe, Uwe A1 - Völker, Manfred T1 - Zielorientierte Dienstplanoptimierung N2 - Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im ÖPNV. Der Ansatz zielt auf die vollständige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Berücksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenwärtig in einem vom Bundesministerium für Bildung und Forschung ({\tt bmb+f}) geförderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum für Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben über eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten über den Stand der Entwicklung. T3 - ZIB-Report - SC-98-41 KW - Dienstplanung KW - Optimierung KW - Zielorientierte Planung Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3847 ER - TY - GEN A1 - Stalling, Detlev A1 - Zöckler, Malte A1 - Sander, Oliver A1 - Hege, Hans-Christian T1 - Weighted Labels for 3D Image Segmentation N2 - Segmentation tools in medical imaging are either based on editing geometric curves or on the assignment of region labels to image voxels. While the first approach is well suited to describe smooth contours at subvoxel accuracy, the second approach is conceptually more simple and guarantees a unique classification of image areas. However, contours extracted from labeled images typically exhibit strong staircase artifacts and are not well suited to represent smooth tissue boundaries. In this paper we describe how this drawback can be circumvented by supplementing region labels with additional weights. We integrated our approach into an interactive segmentation system providing a well-defined set of manual and semi-automatic editing tools. All tools update both region labels as well as the corresponding weights simultaneously, thus allowing one to define segmentation results at high resolution. We applied our techniques to generate 3D polygonal models of anatomical structures. T3 - ZIB-Report - SC-98-39 KW - image processing KW - segmentation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3828 ER - TY - THES A1 - Stalling, Detlev T1 - Fast Texture-Based Algorithms for Vector Field Visualization N2 - In this thesis we develop new methods for visualizing vector fields which specifically address three design goals: accuracy, performance, and cognition. Our methods will be general-purpose and can be applied to arbitrary vector fields in two- and three-dimensional space. The methodology behind our approach is {\em texture-based visualization}. Texture-based visualization methods imitate techniques known from experimental flow visualization, namely, the observation of randomly dispersed particles or dye injection patterns. Instead of depicting individual lines or symbols, a contiguous high-resolution image or texture is generated. This texture clearly reveals the directional structure of the field. In this way intuitive insight can be obtained and even small details of the field become visible. However, it remains unclear what kind of textures are best suited for our purpose. How do we generate them? Can we apply these methods in three-dimensional space? In particular, we focus on a technique known as {\em line integral convolution} or LIC. This method turns out to be quite versatile and well-suited for visualizing many interesting vector fields. LIC images display the integral curves or field lines of a vector field at high spatial resolution. Although conceptually quite simple, line integral convolution implies a number of interesting mathematical and algorithmic questions. T3 - ZIB-Report - SC-98-40 KW - computer graphics KW - line integral convolution KW - stream surfaces Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3838 ER - TY - GEN A1 - Kedziorski, Rafal A1 - Kehl, Detlef A1 - Paetsch, Olaf T1 - Client-Server-Anwendung zur Steuerung von Ausgabegeräten N2 - \\{\bf Zusammenfassung: }\noindent Die Steuerung von grafischen Ausgabegeräten erfordert oft mehr als ein oder zwei Optionen, wie man sie vom UNIX {\em lpr}-Kommando kennt. Hier bietet sich eine grafische Benutzungsschnittstelle zur übersichtlichen Einstellung aller möglichen Parameter und Optionen an. Wenn dieses Gerät zudem nur über eine besondere Treiber-Software zu bedienen ist und in einem heterogenen Intranet zur Verfügung gestellt werden soll, ist eine Steuerung mittels eines WWW-Servers naheliegend. Im Folgenden sollen Lösungsansätze diskutiert werden, die auf HTML/CGI- bzw. Java-Basis derartige Steuerung realisieren. {\small} It is often the case that graphical output devices need more than one or two control options like the UNIX {\em lpr}-command. A driver programme with a graphical user interface (GUI) can satisfy this requirement. If such a device shall be accessible in an heterogenous network a solution using a WWW-server can be used. Possible HTML/CGI resp. Java-based solutions are discussed in the following. T3 - ZIB-Report - TR-98-04 KW - Client-Server-Anwendungen KW - Ausgabegerätesteuerung KW - CGI KW - Java Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5658 ER - TY - GEN A1 - Stalling, Detlev A1 - Seebass, Martin A1 - Zachow, Stefan T1 - Mehrschichtige Oberflächenmodelle zur computergestützten Planung in der Chirurgie N2 - Polygonale Schädelmodelle bilden ein wichtiges Hilfsmittel für computergestützte Planungen im Bereich der plastischen Chirurgie. Wir beschreiben, wie derartige Modelle automatisch aus hochaufgelösten CT-Datensätzen erzeugt werden können. Durch einen lokal steuerbaren Simplifizierungsalgorithmus werden die Modelle so weit vereinfacht, daß auch auf kleineren Graphikcomputern interaktives Arbeiten möglich wird. Die Verwendung eines speziellen Transparenzmodells ermöglicht den ungehinderten Blick auf die bei der Planung relevanten Knochenstrukturen und läßt den Benutzer zugleich die Kopfumrisse des Patienten erkennen. T3 - ZIB-Report - TR-98-05 KW - Isoflächen KW - Simplifizierung KW - Transparenzen Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5661 ER - TY - GEN A1 - Schütte, Christof A1 - Nettesheim, Peter T1 - Non-Adiabatic Effects in Quantum-Classical Molecular Dynamics N2 - In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The article is concerned with the so-called QCMD model. This model describes most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of a wavefunction. We review the conditions under which the QCMD model is known to approximate the full quantum dynamical evolution of the system. In most quantum-classical simulations the {\em Born-Oppenheimer model} (BO) is used. In this model, the wavefunction is adiabatically coupled to the classical motion which leads to serious approximation deficiencies with respect to non-adiabatic effects in the fully quantum dynamical description of the system. In contrast to the BO model, the QCMD model does include non-adiabatic processes, e.g., transitions between the energy levels of the quantum system. It is demonstrated that, in mildly non-adiabatic scenarios, so-called {\em surface hopping} extensions of QCMD simulations yield good approximations of the non-adiabatic effects in full quantum dynamics. The algorithmic strategy of such extensions of QCMD is explained and the crucial steps of its realization are discussed with special emphasis on the numerical problems caused by highly oscillatory phase effects. T3 - ZIB-Report - SC-98-38 KW - quantum-classical molecular dynamics KW - non-adiabatic processes KW - Schrödinger equation KW - highly oscillatory phase KW - adiabatic limit KW - quantum adiabati Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3817 ER - TY - GEN A1 - Nettesheim, Peter T1 - Second Order Transitions in Quantum-Classical Molecular Dynamics N2 - Mixed quantum--classical models have attracted considerable interest due to the expectation that they correctly describe non--adiabatic processes of full quantum dynamics. One of these models, the so--called QCMD model, represents most degrees of freedom of the molecular system by the means of classical mechanics but an important, small portion of the system is modeled by a wavefunction: the wavefunction is nonlinearly coupled to the classical motion via a singularly perturbed Schrödinger equation. In extension to the analysis given by F.A.~Bornemann [{\em Homogenization in Time of Singularly Perturbed Mechanical Systems}, Lecture Notes in Mathematics, no.~1687, 1998, Springer, Berlin], the article presents an asymptotic expansion up to second order in the perturbation parameter. This result allows for the construction of new models and numerical integration schemes. T3 - ZIB-Report - SC-98-37 KW - quantum-classical molecular dynamics KW - mixed quantum-classical models KW - asymptotics KW - quantum populations Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3805 ER - TY - GEN A1 - Huisinga, Wilhelm A1 - Best, Christoph A1 - Cordes, Frank A1 - Roitzsch, Rainer A1 - Schütte, Christof T1 - From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods N2 - Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide. T3 - ZIB-Report - SC-98-36 KW - conformational ensemble KW - cluster method KW - structural and dynamical similarity KW - representative KW - conformation KW - essential degrees of freedom KW - transi Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3797 ER - TY - GEN A1 - Kuberek, Monika T1 - Bibliothekarische Inhalte und Zielsetzungen des KOBV N2 - Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wurde 1997 auf politische Initiative hin gegründet, um für die ressourcenreiche, aber elektronisch unzulänglich erschlossene Bibliotheksregion Berlin-Brandenburg eine moderne Informationsinfrastruktur zu schaffen. Auf der Basis eines Expertengutachtens wird sowohl in technischer als auch in organisatorischer Hinsicht ein neues Kooperationsmodell entwickelt, das auf den Prinzipien der Dezentralisierung, Deregulierung und Kooperation beruht. Der vorliegende Artikel ist das Ergebnis einer bibliothekarischen Arbeitsgruppe des KOBV, die von Dezember 1997 bis März 1998 das Modell des KOBV unter bibliothekarischen Gesichtspunkten diskutiert hat. Es werden erste Leitlinien festgelegt zu den Serviceleistungen des KOBV, zu den Prinzipien der Zusammenarbeit der Bibliotheken untereinander sowie zur Einbindung des Verbundes in das Bibliothekswesen der Bundesrepublik. Damit dient der Artikel zugleich der Positionsbestimmung des KOBV innerhalb des deutschen Bibliothekswesens. T3 - ZIB-Report - TR-98-03 KW - Bibliotheksverbund KW - KOBV KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg KW - Verbundkooperation KW - Verbundorganisation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5646 ER - TY - GEN A1 - Deuflhard, Peter A1 - Weiser, Martin A1 - Seebass, Martin T1 - A New Nonlinear Elliptic Multilevel FEM Applied to Regional Hyperthermia N2 - In the clinical cancer therapy of regional hyperthermia nonlinear perfusion effects inside and outside the tumor seem to play a not negligible role. A stationary model of such effects leads to a nonlinear Helmholtz term within an elliptic boundary value problem. The present paper reports about the application of a recently designed adaptive multilevel FEM to this problem. For several 3D virtual patients, nonlinear versus linear model is studied. Moreover, the numerical efficiency of the new algorithm is compared with a former application of an adaptive FEM to the corresponding instationary model PDE. T3 - ZIB-Report - SC-98-35 KW - hyperthermia KW - nonlinear elliptic KW - multilevel FEM Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3785 ER - TY - GEN A1 - Kühn, Wolfgang A1 - Korzen, Manfred A1 - Paetsch, Olaf T1 - Fast Data Assimilation in Fire Tests of Steel Members N2 - This report presents a fast data assimilation method to produce an interpolating time and space temperature distribution for steel members subject to fire testing. The method assimilates collected temperature data into the numerical integration of the heat equation. This physically based method also allows the computation of lateral and axial heat flux into and inside the member. T3 - ZIB-Report - SC-98-33 KW - data assimilation KW - heat equation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3766 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Krumke, Sven A1 - Rambau, Jörg T1 - The Online Transportation Problem: Competitive Scheduling of Elevators N2 - In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service. T3 - ZIB-Report - SC-98-34 KW - online optimization KW - competitive analysis KW - elevator Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3779 ER - TY - GEN A1 - Kühn, Wolfgang T1 - iTe 1.1 User's Guide N2 - iTe is an easy to use, interactive authoring tool for LaTeX and TeX documents. With iTe, it is possible to select arbitrary display fragments such as figures, equations, labels, captions, etc. These fragments can then be freely moved, rotated and scaled. T3 - ZIB-Report - TR-98-02 KW - TeX KW - Emacs KW - interactive editing Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5638 ER - TY - GEN A1 - Schmidt, Frank T1 - An Alternative Derivation of the Exact DtN-Map on a Circle N2 - The paper supplies an alternative derivation of the exact boundary conditions needed for the solution of time-harmonic acoustic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior domain problem as an initial value problem with initial data given on the boundary of a disc or sphere. The solution of the exterior domain problem is obtained via Laplace transformation techniques, where the asymptotic Sommerfeld radiation condition is reformulated accordingly. T3 - ZIB-Report - SC-98-32 KW - Helmholtz equation KW - Dirichlet-to-Neumann map KW - Sommerfeld radiation condition Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3752 ER - TY - GEN A1 - Schneider, Thomas A1 - Botta, Nicola A1 - Geratz, Karl Josef A1 - Klein, Rupert T1 - Extension of finite volume compressible flow solvers to multi-dimensional, variable density zero Mach number flow N2 - When attempting to compute unsteady, variable density flows at very small or zero Mach number using a standard finite volume compressible flow solver one faces at least the following difficulties: (i) Spatial pressure variations vanish as the Mach number $M \rightarrow 0$, but they do affect the velocity field at leading order; (ii) the resulting spatial homogeneity of the leading order pressure implies an elliptic divergence constraint for the energy flux; (iii) violation of this constraint would crucially affect the transport of mass, thereby disabling a code to properly advect even a constant density distribution. A previous companion paper derived the above observations from a single time - multiple length scale asymptotic analysis for $M \ll 1$, applied to the conservation form of the governing equations and assuming an ideal gas with constant specific heats. The paper then restricted to weakly compressible one-dimensional flows and introduced a semi-implicit extension of a compressible flow solver, designed to handle the interaction of long wavelength acoustics with small scale, large amplitude density fluctuations. In the present paper we concentrate on the limit of zero Mach number for multi-dimensional, variable density flows. The construction of numerical fluxes for all conserved quantities involves: An explicit upwind step (1) yielding predictions for the nonlinear convective flux components. This procedure still neglects the influence of pressure gradients on the convective fluxes during the time step. Suitable corrections are applied in step (2), which guarantees compliance of the convective fluxes with the divergence constraint. This step requires the solution of a Poisson-type equation to obtain the relevant pressure gradients. Step (3), which requires the solution of a second Poisson-type equation, yields the yet unknown (non-convective) pressure contribution to the total flux of momentum. The final, cell centered velocity field exactly satisfies a discrete divergence constraint consistent with the asymptotic limit. Notice that step (1) can be done by any standard finite volume compressible flow solver and that the input to steps (2) and (3) involves solely the fluxes from step (1), but is independent on how these were obtained. Thus, we claim that our approach allows any such solver to be extended to simulate incompressible flows. Extensions to the weakly compressible regime $0 < M \ll 1$, reactive flows and more complex equations of state will be addressed in follow-up publications. T3 - ZIB-Report - SC-98-31 KW - Incompressible variable density flows KW - conservation laws Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3749 ER - TY - GEN A1 - Deuflhard, Peter A1 - Seebass, Martin T1 - Adaptive Multilevel FEM as Decisive Tools in the Clinical Cancer Therapy Hyperthermia N2 - The paper surveys recent progress in a joint mathematical-medical project on cancer therapy planning. Within so-called regional hyperthermia the computational task is to tune a set of coupled radiofrequency antennas such that a carefully measured tumor is locally heated, but any outside hot spots are avoided. A mathematical model of the whole clinical system -- air, applicator with antennas, water bolus, individual patient body -- involves Maxwell's equations in inhomogeneous media and a parabolic bioheat transfer equation, which represents a simplified model of heat transfer in the human body (ignoring strong blood vessel heat transport). Both PDEs need to be computed fast and to medical reliability (!) on a workstation within a clinical environment. This requirement triggered a series of new algorithmic developments to be reported here, among which is an adaptive multilevel FEM for Maxwell's equations, which dominates the numerical simulation time. In total, however, the main bulk of computation time (see Table 3 in Section 4 below) still goes into segmentation -- a necessary preprocessing step in the construction a 3D virtual patient from the input of a stack of 2D computed tomograms (left out here). T3 - ZIB-Report - SC-98-30 KW - hyperthermia KW - Maxwell's equations KW - nonlinear heat transfer KW - finite elements Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3739 ER - TY - GEN A1 - Huisinga, Wilhelm A1 - Pesce, Lorenzo A1 - Kosloff, Ronnie A1 - Saalfrank, Peter T1 - Faber and Newton Polynomial Integrators for Open-System Density Matrix Propagation N2 - Two polynomial expansions of the time-evolution superoperator to directly integrate Markovian Liouville-von Neumann (LvN) equations for quantum open systems, namely the Newton interpolation and the Faber approximation, are presented and critically compared. Details on the numerical implementation including error control, and on the performance of either method are given. In a first physical application, a damped harmonic oscillator is considered. Then, the Faber approximation is applied to compute a condensed phase absorption spectrum, for which a semi--analytical expression is derived. Finally, even more general applications are discussed. In all applications considered here it is found that both the Newton and Faber integrators are fast, general, stable, and accurate. T3 - ZIB-Report - SC-98-29 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3725 ER - TY - GEN A1 - Bruns, Winfried A1 - Gubeladze, Joseph A1 - Henk, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - A counterexample to an integer analogue of Caratheodorys theorem N2 - For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed. T3 - ZIB-Report - SC-98-28 KW - Integral pointed cones KW - Hilbert basis KW - integral Carathéodory property Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3718 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs N2 - The paper presents a new algorithmic approach for multistage stochastic programs which are seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within a primal-dual interior point method. Convergence is drastically enhanced by a successive refinement technique providing both primal and dual initial estimates. Test runs on a multistage portfolio selection problem demonstrate the performance of the method. T3 - ZIB-Report - SC-98-27 KW - Multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - successive refinement Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3706 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Scientific Information Systems and Metadata N2 - This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} . T3 - ZIB-Report - SC-98-26 KW - elektronisches Publizieren KW - Metadaten KW - Dublin Core KW - Klassifikation KW - Math-Net Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3698 ER - TY - GEN A1 - Grötschel, Martin A1 - Dalitz, Wolfgang A1 - Winczewski, Vincent T1 - Math-Net: Ein Informationssystem der Mathematik N2 - In diesem Artikel geben wir einen Überblick über das Math-Net-Projekt. Wir berichten über die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems für die Mathematik in Deutschland. T3 - ZIB-Report - SC-98-25 KW - Information System KW - Math-Net KW - Math-Net-Links KW - Dublin Core KW - Harvest Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3680 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering N2 - Multistage stochastic programs can be seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm. T3 - ZIB-Report - SC-98-23 KW - multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - finance Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3661 ER - TY - GEN A1 - Lourenco, Maria José A1 - Rosa, Samuel Costa S. A1 - Castro, Carlos Alberto Nieto de A1 - Albuquerque, C. A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Roitzsch, Rainer T1 - Simulation of the Transient Heating in an Unsymmetrical Coated Hot--Strip Sensor with a Self--Adaptive Finite Element Method N2 - The transient heating in an unsymmetrical coated hot--strip sensor was simulated with a self--adaptive finite element method. The first tests of this model show that it can determine with a small error the thermal conductivity of liquids, from the transient temperature rise in the hot--strip, deposited in a substrate and coated by an alumina spray. T3 - ZIB-Report - SC-98-22 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3656 ER - TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - On a Two-Queue Priority System with Impatience and its Application to a Call Center N2 - We consider a $s$-server system with two FCFS queues, where the arrival rates at the queues and the service rate may depend on the number $n$ of customers being in service or in the first queue, but the service rate is assumed to be constant for $n>s$. The customers in the first queue are impatient. If the offered waiting time exceeds a random maximal waiting time $I$, then the customer leaves the first queue after time $I$. If $I$ is less than a given deterministic time then he leaves the system else he transits to the end of the second queue. The customers in the first queue have priority. The service of a customer from the second queue will be started if the first queue is empty and more than a given number of servers become idle. For the model being a generalization of the $M(n)/M(n)/s\!+\!GI$ system balance conditions for the density of the stationary state process are derived yielding the stability conditions and the probabilities that precisely $n$ customers are in service or in the first queue. For obtaining performance measures for the second queue a system approximation basing on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server. For an important special case a stochastic decomposition is derived illuminating the connection to the dynamics of the $M(n)/M(n)/s\!+\!GI$ system. T3 - ZIB-Report - SC-98-21 KW - two queues KW - many server KW - server reservation KW - impatience KW - occupancy distribution KW - waiting time distribution KW - approximate system KW - $M(n)/M(n)/s+GI Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3641 ER - TY - GEN A1 - Bley, Andreas T1 - On the Complexity of Vertex-Disjoint Length-Restricted Path Problems N2 - Let $G=(V,E)$ be a simple graph and $s$ and $t$ be two distinct vertices of $G$. A path in $G$ is called $\ell$-bounded for some $\ell\in\mathbb{N}$, if it does not contain more than $\ell$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint $\ell$-bounded $s,t$-paths in $G$. First, we show that computing the maximum number of vertex-disjoint $\ell$-bounded $s,t$-paths is $\mathcal{AP\kern-1pt X}$--complete for any fixed length bound $\ell\geq 5$. Second, for a given number $k\in\mathbb{N}$, $1\leq k \leq |V|-1$, and non-negative weights on the edges of $G$, the problem of finding $k$ vertex-disjoint $\ell$-bounded $s,t$-paths with minimal total weight is proven to be $\mathcal{NPO}$--complete for any length bound $\ell\geq 5$. Furthermore, we show that, even if $G$ is complete, it is $\mathcal{NP}$--complete to approximate the optimal solution value of this problem within a factor of $2^{\langle\phi\rangle^\epsilon}$ for any constant $0<\epsilon<1$, where $\langle\phi\rangle$ denotes the encoding size of the given problem instance $\phi$. We prove that these results are tight in the sense that for lengths $\ell\leq 4$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to $\ell$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results. T3 - ZIB-Report - SC-98-20 KW - disjoint paths KW - length bounded paths KW - approximation KW - reducibility KW - completeness Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3639 ER - TY - THES A1 - Reich, Sebastian T1 - Dynamical Systems, Numerical Integration, and Exponentially Small Estimates N2 - Dynamical systems with two well-separated time-scales are investigated using normal form theory. Exponential estimates for the normal form truncation error are derived and applied to the numerical integration of differential equations (backward error analysis) and the reduction of highly oscillatory Hamiltonian systems (constrained dynamics and correcting potentials). The theoretical results are used to formulate new algorithms for the time integration of conservative Hamiltonian systems (projected multiple time stepping, soft constraints, rigid bodies, symplectic variable step-size methods). T3 - ZIB-Report - SC-98-19 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3622 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Conjunctive Cuts for Integer Programs N2 - This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view. T3 - ZIB-Report - SC-98-18 KW - Polyhedral Combinatorics KW - Integer Programming KW - Separation Algorithm Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3618 ER - TY - GEN A1 - Holder, Thomas A1 - Leimkuhler, Benedict A1 - Reich, Sebastian T1 - Explicit Variable Step-Size and Time-Reversible Integration N2 - A variable step-size, semi-explicit variant of the explicit Störmer-Verlet method has been proposed for the time-reversible integration of Newton's equations of motion by Huang & Leimkuhler. Here we propose a fully explicit version of this approach applicable to explicit and symmetric integration methods for general time-reversible differential equations. As applications, we discuss the variable step-size, time-reversible, and fully explicit integration of rigid body motion and reversible Nos\'e-Hoover dynamics. T3 - ZIB-Report - SC-98-17 KW - reversible differential equations KW - time integration KW - adaptive methods Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3607 ER - TY - GEN A1 - Lang, Jens T1 - Adaptive Incompressible Flow Computations with Linearly Implicit Time Discretization and Stabilized Finite Elements N2 - Fully adaptive solutions of imcompressible flow problems employing the discretization sequence first in time then in space are presented. The time discretization is done by linearly implicit one--step methods possibly of high order with automatic step size control. A posteriori error estimates for the stabilized finite element discretization in space are obtained by solving local Dirichlet problems with higher accuracy. Once those estimates have been computed, we are able to control time and space grids with respect to required tolerances and necessary computational work. The devised method is applied to two benchmark problems in 2D. T3 - ZIB-Report - SC-98-16 KW - Incompressible Flow KW - Adaptive Stabilized Finite Element KW - Linearly Implicit Time Discretization Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3599 ER - TY - GEN T1 - Jahresbericht 1997 T3 - Jahresbericht - 1997 KW - Annual Report Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9722 SN - 0934-5892 ER - TY - GEN A1 - Roitzsch, Rainer A1 - Erdmann, Bodo A1 - Lang, Jens T1 - The Benefits of Modularization: from KASKADE to KARDOS N2 - KARDOS solves nonlinear evolution problems in 1, 2, and 3D. An adaptive multilevel finite element algorithm is used to solve the spatial problems arising from linearly implicit discretization methods in time. Local refinement and derefinement techniques are used to handle the development of the mesh over time. The software engineering techniques used to implement the modules of the KASKADE toolbox are reviewed and their application to the extended problem class is described. A notification system and dynamic construction of records are discussed and their values for the implementation of a mesh transfer operation are shown. The need for low-level and high--level interface elements of a module is discussed for the assembling procedure of KARDOS. At the end we will summarize our experiences. T3 - ZIB-Report - SC-98-15 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3586 ER - TY - GEN A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes I. N2 - The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve. T3 - ZIB-Report - SC-98-14 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations KW - Flip Defici Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3579 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - The Orientation Model for Frequency Assignment Problems N2 - Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem. T3 - ZIB-Report - TR-98-01 KW - Minimum-Cost Flow Problems KW - Cellular Radio Telephone Systems KW - Frequency Assignment Problem KW - Integer Programming Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5627 ER - TY - GEN A1 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Design of Broadband Virtual Private Networks: Model and Heuristics for the B–WiN N2 - We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data. T3 - ZIB-Report - SC-98-13 KW - Telecommunication Network Design KW - Survivable Networks KW - Network Capacity Planning KW - OSPF Routing KW - Shortest Path Routing KW - Heuristics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3565 ER - TY - GEN A1 - Caröe, Claus C. A1 - Schultz, Rüdiger T1 - A Two-Stage Stochastic Program for Unit Commitment Under Uncertainty in a Hydro-Thermal Power System N2 - We develop a two-stage stochastic programming model with integer first-stage and mixed-integer recourse for solving the unit commitment problem in power generation in the presence of uncertainty of load profiles. The solution methodology rests on a novel scenario decomposition method for stochastic integer programming. This method combines Lagrangian relaxation of non-anticipativity constraints with branch-and-bound. It can be seen as a decomposition algorithm for large-scale mixed-integer linear programs with block-angular structure. With realistic data from a German utility we validate our model and carry out test runs. Sizes of these problems go up to 20.000 integer and 150.000 continuous variables together with up to 180.000 constraints. T3 - ZIB-Report - SC-98-11 KW - Programming KW - stochastic:Scenario Decomposition if mixed-integer programs KW - Natural resourses KW - energy:Unit commitment under uncertainty Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3543 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Haus, Utz-Uwe A1 - Henk, Martin T1 - On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities N2 - \noindent An immediate generalization of the classical McKay correspondence for Gorenstein quotient spaces $\Bbb{C}^{r}/G$ in dimensions $r\geq 4$ would primarily demand the existence of projective, crepant, full desingularizations. Since this is not always possible, it is natural to ask about special classes of such quotient spaces which would satisfy the above property. In this paper we give explicit necessary and sufficient conditions under which 2-parameter series of Gorenstein cyclic quotient singularities have torus-equivariant resolutions of this specific sort in all dimensions. T3 - ZIB-Report - SC-98-12 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3559 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Monotone Iterations for Elliptic Variational Inequalities N2 - A wide range of free boundary problems occurring in engineering andindustry can be rewritten as a minimization problem for astrictly convex, piecewise smooth but non--differentiable energy functional.The fast solution of related discretized problemsis a very delicate question, because usual Newton techniquescannot be applied. We propose a new approach based on convex minimization and constrained Newton type linearization. While convex minimization provides global convergence of the overall iteration, the subsequent constrained Newton type linearization is intended to accelerate the convergence speed. We present a general convergence theory and discuss several applications. T3 - ZIB-Report - SC-98-10 KW - finite elements KW - multigrid methods KW - variational inequalities Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3539 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Optimization of Transportation Systems N2 - The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far. T3 - ZIB-Report - SC-98-09 KW - Transportation Systems KW - Optimization KW - Discrete Mathematics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3529 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin T1 - Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs N2 - We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems. T3 - ZIB-Report - SC-98-08 KW - Traveling Salesman Problem KW - Online-Algorithm KW - Automatic Storage System Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3519 ER - TY - GEN A1 - Foupouagnigni, Mama A1 - Ronveaux, Andre A1 - Koepf, Wolfram T1 - Fourth-Order q-Difference Equation for the First Associated of the q-Classical Orthogonal Polynomials N2 - We derive the fourth order $q$-difference equation satisfied by the first associated of the $q$-classical orthogonal polynomials. The coefficients of this equation are given in terms of the polynomials $\; \sigma\;$ and $\;\tau\;$ which appear in the $q$-Pearson difference equation $\;\; D_q(\sigma\,\rho)=\tau\,\rho\;$ defining the weight $\rho$ of the $q$-classical orthogonal polynomials inside the $q$-Hahn tableau. T3 - ZIB-Report - SC-98-06 KW - q-Orthogonal polynomials KW - Fourth order q-difference equation Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3490 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Kamin, Nicola A1 - Rambau, Jörg T1 - Combinatorial Online Optimization in Practice N2 - This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems. T3 - ZIB-Report - SC-98-07 KW - Online optimization KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3508 ER - TY - GEN A1 - Wolters, Christof T1 - GOS Thesaurus--Handbuch zum Projekt: Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern N2 - Das GOS Thesaurus--Handbuch wurde für die Teilnehmer des von der Robert Bosch Stiftung geförderten Projekts zum Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern geschrieben. Es basiert auf verschiedenen vom Institut für Museumskunde gemeinsam mit dem ZIB durchgeführten Projekten und beschreibt mit zahlreichen Beispielen Struktur und Aufbau eines Thesaurus. T3 - ZIB-Report - TR-97-19 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5616 ER - TY - GEN A1 - Saro, Carlos A1 - Schröder, Beate A1 - Volkmann, Katrin T1 - GOS Benutzer--Handbuch. Anleitung zum Projekt: Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern N2 - Das Handbuch enthält eine ausführliche Einführung in das am ZIB für den Einsatz in der Museumsdokumentation entwickelte Datenbanksystem GOS. T3 - ZIB-Report - TR-97-16 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5584 ER - TY - GEN A1 - Clemens, Hans-H. A1 - Saro, Carlos T1 - Abschlussbericht für das Projekt: Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern N2 - Von Januar 1995 bis Februar 1997 wurde am ZIB ein von der Robert Bosch Stiftung gefördertes Projekt zum Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern durchgeführt. In dem vorliegenden Abschlußbericht werden die Ziele, die Strategie, die Durchführung und die Ergebnisse des Projekts beschrieben. T3 - ZIB-Report - TR-97-17 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5595 ER - TY - GEN A1 - Clemens, Hans-H. T1 - Systemanalyse und Datenkatalog zum Projekt: Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern N2 - Von Januar 1995 bis Februar 1997 wurde am ZIB ein von der Robert Bosch Stiftung gefördertes Projekt zum Sammlungsmanagement für kulturgeschichtliche Museen in den neuen Bundesländern durchgeführt. Die vorliegende Systemanalyse beschreibt exemplarisch die Voraussetzungen und die notwendigen Arbeitsschritte für den Aufbau einer Dokumentation in einem Museum. Ein im Anhang wiedergegebener Datenfeldkatalog hilft beim "`sanften"' Übergang von einer papiergestützten zu einer computergestützten Dokumentation. T3 - ZIB-Report - TR-97-18 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5603 ER - TY - GEN A1 - Wolf, Thomas A1 - Brandt, Andreas A1 - Mohammadzadeh, Majid T1 - Computer algebra algorithms and routines for the computation of conservation laws and fixing of gauge in differential expressions N2 - Three different approaches for the determination of conservation laws of differential equations are presented. For three corresponding REDUCE computer algebra programs CONLAW1/2/3 the necessary subroutines are discribed. One of them simplifies general solutions of overdetermined PDE systems so that all remaining free functions and constants correspond to independent conservation laws. It determines redundant functions and constants in differential expressions and is equally useful for the determination of symmetries or the fixing of gauge freedom in differential expressions. T3 - ZIB-Report - SC-98-05 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3482 ER - TY - GEN A1 - Hege, Hans-Christian A1 - Stalling, Detlev T1 - Fast LIC with Higher Order Filter Kernels N2 - Line integral convolution (LIC) has become a well-known and popular method for visualizing vector fields. The method works by convolving a random input texture along the integral curves of the vector field. In order to accelerate image synthesis significantly, an efficient algorithm has been proposed that utilizes pixel coherence in field line direction. This algorithm, called ``fast LIC'', originally was restricted to simple box-type filter kernels. Here we describe a generalization of fast LIC for piecewise polynomial filter kernels. Expanding the filter kernels in terms of truncated power functions allows us to exploit a certain convolution theorem. The convolution integral is expressed as a linear combination of repeated integrals (or repeated sums in the discrete case). Compared to the original algorithm the additional expense for using higher order filter kernels, e.g.\ of B-spline type, is very low. Such filter kernels produce smoother, less noisier results than a box filter. This is evident from visual investigation, as well as from analysis of pixel correlations. Thus, our method represents a useful extension of the fast LIC algorithm for the creation of high-quality LIC images. T3 - ZIB-Report - SC-97-74 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3439 ER - TY - GEN A1 - Lügger, Joachim T1 - Wo ist der Opac der virtuellen Bibliothek?- Strukturen des Kooperativen Bibliotheksverbundes N2 - Als neue Herausforderung für die Bibliotheken stellen sich heute die vielfältigen Publikationsmöglichkeiten, die den Wissenschaften durch das Internet zur Verfügung stehen. Die neuen Arten der wissenschaftlichen Information zu erschließen, wird für die Bibliotheken zu den neuen Aufgaben gehören. Der Artikel diskutiert zunächst die Frage, inwieweit dabei die traditionell hohen Maßstäbe bei der bibliographischen Beschreibung und sachlichen Erschließung noch aufrechterhalten werden können. Der Autor plädiert in diesem Zusammenhang für ein reduziertes Erfassungsschema im Sinne des Dublin Core, da dieses gleichzeitig eine Arbeitsteilung zwischen Wissenschaftlern, die zu ihren eigenen Arbeiten Metadaten erstellen, und Bibliotheksmitarbeitern, die solche einfachen Beschreibungen nach professionellen Maßstäben weiterentwickeln, ermöglicht. Der zweite Teil der Arbeit stellt eine technische Interpretation des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) vor, den eine Expertengruppe als neue Informationsstruktur für diese Region vorgesehen hat. Das Modell des Kooperativen Bibliotheksverbundes sieht im Prinzip eine dezentrale Datenhaltung vor, bei der die Bibliotheken in lokale Bibliothekssysteme katalogisieren. Im Gegensatz zu traditionellen Verbünden verzichtet der KOBV auf einen Zentralkatalog. Die in den lokalen Systemen vorliegende Information hingegen wird den Nutzern über eine Suchmaschine erschlossen und zur Verfügung gestellt. Dabei wird vorausgesetzt, daß die Zielsysteme über offene Schnittstellen (Z39.50 und WWW) angesprochen werden können. Zur Optimierung der bibliothekarischen Arbeit im Sinne von Copy Cataloging und Copy Acquisition steht vor allem den KOBV-Partnern ein zentrales Fremddatenangebot sowie die in Deutschland verbreiteten Normdaten zur Verfügung. Mit der Kommunikation über das standardisierte Protokoll Z39.50 sind dabei sowohl der KOBV selbst als auch das Fremddatengebot virtuell skalierbar. Im Unterschied zu einem zentralistisch organisierten Bibliotheksverbund eröffnet der auf dezentralen Strukturen aufbauende Kooperative Bibliotheksverbunds auch die Möglichkeit, virtuelle Fachverbünde zu beispielsweise einer Disziplin zu bilden. T3 - ZIB-Report - TR-97-10 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5524 ER - TY - GEN A1 - Kuberek, Monika A1 - Lohrum, Stefan T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg - Schnittstelle Lokalsysteme-Suchmaschine, Spezifikation der Anforderungen N2 - Die Kommunikation zwischen der Suchmaschine und den Lokalsystemen findet über eine offene Schnittstelle statt. Als Standardschnittstelle dient Z39.50-1995 (auch als Z39.50, Level 3 bekannt). Grundsätzlich können auch Lokalsysteme angesprochen werden, die nur über eine WWW-Schnittstelle verfügen. Dieses Papier spezifiziert die Anforderungen, die seitens der KOBV-Suchmaschine an ein Lokalsystem gestellt werden. T3 - ZIB-Report - TR-97-11 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5538 ER - TY - GEN A1 - Kuberek, Monika T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg - Normdaten im KOBV N2 - Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wird sich aktiv am Aufbau der deutschen Normdateien Gemeinsame Körperschaftsdatei (GKD), Schlagwortnormdatei (SWD) und Personennamendatei (PND) beteiligen, die in Gemeinschaftsarbeit der deutschen Bibliotheksverbünde erstellt werden. Nach der Konzeption liegen die Normdateien auf dem zentralen KOBV-Server auf und stehen über die Suchmaschine allen angeschlossenen Bibliotheken zur Verfügung. Lokal befinden sich nur die Normdatensätze, die mit Titeln verknüpft sind. Das Update der Normdaten geschieht zentral. Es werden Lösungen aufgezeigt, wie die Normdaten von den KOBV-Bibliotheken mittels offener Schnittstellen (Z39.50) genutzt und erstellt werden können und auf welche Weise der KOBV mit den Redaktionen der Normdateien zusammenarbeiten kann. Neben den technischen werden auch die organisatorischen Fragen erörtert, die mit dem neuartigen KOBV-Konzept der dezentralen Nutzung der Normdaten in den lokalen Bibliothekssystemen zusammenhängen. Weitere Themen sind die regionale Zusammenarbeit der Bibliotheken und der KOBV-Zentrale mit der Zeitschriftendatenbank (ZDB) sowie die Einbindung zusätzlicher Normdaten, wie Universal- bzw. Fachklassifikationen und Thesauri. T3 - ZIB-Report - TR-97-12 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5548 ER - TY - GEN A1 - Willenborg, Josef T1 - Die Suchmaschine des KOBV - Spezifikation der Anforderungen N2 - Das vorliegende Papier spezifiziert die Anforderungen an die Suchmaschine im Kooperativen Biblotheksverbund Berlin- Brandenburg (KOBV). Die Suchmaschine realisiert einen virtuellen Union Catalog, der auch als virtueller OPAC im Netz ansprechbar ist. Die zentrale Suchmaschine fungiert als Gateway zwischen der WWW- und der Z39.50-Welt des Internet. Mit Hilfe der Suchmaschine wird der Zugriff auf die Bibliotheken des KOBV, auf Normdaten und Fremddaten sowie auf weitere Informationsanbieter außerhalb des KOBV (über Internet und andere Netze) ermöglicht. Auf die Suchmaschine greifen sowohl Bibliotheksmitarbeiter/innen als auch Endnutzer zu, d.h. sie muß unterschiedlichen Anwenderbedürfnissen gerecht werden. T3 - ZIB-Report - TR-97-13 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5552 ER - TY - GEN A1 - Lügger(Red.), Joachim T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg - Lokale Konzepte und technische Schnittstellen N2 - Dieser Artikel faßt die Ergebnisse einer Arbeitsgruppe bestehend aus Bibliothekaren und Informatikern der Universitäts- und Hochschulbibliotheken aus Berlin und Brandenburg zusammen, welche sich im Frühjahr 1997 zusammengefunden hatte, um die Anforderungen an den Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) aus Sicht der betroffenen Institutionen zu diskutieren. Dieser Verbund verzichtet zugunsten einer verteilten Datenhaltung in den jeweiligen lokalen Bibliothekssystemen auf einen Zentralkatalog und realisiert statt dessen mittels einer Suchmaschine einen virtuellen Union-Katalog, der auch als OPAC im Internet zur Verfügung steht. Zusätzlich soll zur Unterstützung der Erwerbungs- und Katalogisierungsarbeit der wissenschaftlichen Bibliotheken ein Fremd- und Normdatenserver errichtet werden. Beschrieben werden neben den erforderlichen Internet-Schnittstellen (WWW, Z39.50), das Fremd- und Normdatenangebot als auch konkrete Anforderungen an die Suchmaschine. Dabei wird die Sicht der Bibliotheksmitarbeiter ebenso wie die der Bibliotheksbenutzer berücksichtigt. T3 - ZIB-Report - TR-97-14 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5566 ER - TY - GEN A1 - Rusch, Beate T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg - Strategien zur Nutzung von Fremddaten N2 - Ausgehend von einer Analyse der Fremddatenbedarfs in der Bibliotheksregion Berlin-Brandenburg wird überlegt, welche Fremddaten im neuen Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) in Zukunft an welchem Ort vorliegen sollten. Dabei wird konzeptionell eine Balance versucht zwischen den Daten, die zentral für die Region angeboten werden, den Daten, die die Bibliotheken (langfristig) über Z39.50 aus (verbund-) fremden Bibliotheken abrufen, und denjenigen Datenbeständen, die ausschließlich zur lokalen Nutzung vorliegen. T3 - ZIB-Report - TR-97-15 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5579 ER - TY - GEN A1 - Deuflhard, Peter A1 - Huisinga, Wilhelm A1 - Fischer, Alexander A1 - Schütte, Christof T1 - Identification of Almost Invariant Aggregates in Reversible Nearly Uncoupled Markov Chains N2 - The topic of the present paper bas been motivated by a recent computational approach to identify chemical conformations and conformational changes within molecular systems. After proper discretization, the conformations show up as almost invariant aggregates in reversible nearly uncoupled Markov chains. Most of the former work on this subject treated the direct problem: given the aggregates, analyze the loose coupling in connection with the computation of the stationary distribution (aggregation/disaggregation techniques). In contrast to that the present paper focuses on the inverse problem: given the system as a whole, identify the almost invariant aggregates together with the associated transition probabilites. A rather simple and robust algorithm is suggested and illustrated by its application to the n-pentane molecule. T3 - ZIB-Report - SC-98-03 KW - essential molecular dynamics KW - nearly reducible KW - nearly completely decomposable KW - nearly uncoupled Markov chain KW - almost invariant aggregates KW - trans Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3469 ER - TY - GEN A1 - Schütte, Christof A1 - Fischer, Alexander A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - A Hybrid Monte Carlo Method for Essential Molecular Dynamics N2 - Recently, a novel concept for the computation of essential features of Hamiltonian systems (such as those arising in molecular dynamics) has been proposed. The realization of that concept was based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept based on statistical mechanics, which allows to attack realistic molecular systems. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via hybrid Monte Carlo techniques (based on short term subtrajectories only) is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable (to be presented elsewhere). Numerical results for the n-pentane molecule are given and interpreted. T3 - ZIB-Report - SC-98-04 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3474 ER - TY - GEN A1 - Wolf, Thomas T1 - A Study of Genetic Algorithms solving a combinatorial Puzzle N2 - The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings. T3 - ZIB-Report - SC-98-01 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3445 ER - TY - GEN A1 - Böing, Harald A1 - Koepf, Wolfram T1 - Algorithms for q-hypergeometric Summation in Computer Algebra N2 - In this paper we present a short description of $q$-analogues of Gosper's, Zeilberger's, Petkov\v{s}ek's and related algorithms. Furthermore we introduce our corresponding MAPLE implementations and show how they can be applied to prove or even derive identities associated with $q$-series. T3 - ZIB-Report - SC-98-02 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3453 ER - TY - GEN A1 - Lang, Jens A1 - Erdmann, Bodo A1 - Seebass, Martin T1 - Impact of Nonlinear Heat Transfer on Temperature Control in Regional Hyperthermia N2 - We describe an optimization process specially designed for regional hyperthermia of deep seated tumors in order to achieve desired steady--state temperature distributions. A nonlinear three--dimensional heat transfer model based on temperature--dependent blood perfusion is applied to predict the temperature. Using linearly implicit methods in time and adaptive multilevel finite elements in space, we are able to integrate efficiently the instationary nonlinear heat equation with high accuracy. Optimal heating is obtained by minimizing an integral object function which measures the distance between desired and model predicted temperatures. A sequence of minima is calculated from successively improved constant--rate perfusion models employing a damped Newton method in an inner iteration. We compare temperature distributions for two individual patients calculated on coarse and fine spatial grids and present numerical results of optimizations for a Sigma 60 Applicator of the BSD 2000 Hyperthermia System. T3 - ZIB-Report - SC-97-73 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3426 ER - TY - GEN A1 - Foupouagnigni, Mama A1 - Ronveaux, Andre A1 - Hounkonnou, Mahouton Norbert T1 - The Fourth-Order Difference Equation Satisfied by the Associated Orthogonal Polynomials of the Delta-Laguerre-HahnClass N2 - Starting from the $ D_{ \omega}$-Riccati Difference equation satisfied by the Stieltjes function of a linear functional, we work out an algorithm which enables us to write the unique fourth-order difference equation satisfied by the associated of any integer order of orthogonal polynomials of the $ \Delta$-Laguerre-Hahn class. Moreover, in classical situations (Meixner, Charlier, Kravtchouk and Hahn), we give explicitely these difference equations; and from Hahn difference equation, we recover by limit process the difference equations satisfied by the associated of classical discrete orthogonal polynomials and differential equations satisfied by the associated of classical continuous orthogonal polynomials. T3 - ZIB-Report - SC-97-71 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3409 ER - TY - GEN A1 - Foupouagnigni, Mama A1 - Koepf, Wolfram A1 - Ronveaux, Andre T1 - Fourth Order Difference Equation for the Associated Classical Discrete Orthogonal Polynomials N2 - We derive the fourth order difference equation satisfied by the associated of order $\;r\;$ of the classical orthogonal polynomials of a discrete variable.\\The coefficients of this equation are given in terms of the polynomials $\; \sigma\;$ and $\;\tau\;$ which appear in the discrete Pearson equation $\;\;\Delta(\sigma\;\rho)=\tau\;\rho\;\;$ defining the weight $\;\rho(x)\;$ of the classical discrete orthogonal polynomials. T3 - ZIB-Report - SC-97-72 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3419 ER - TY - THES A1 - Löbel, Andreas T1 - Optimal Vehicle Scheduling in Public Transit N2 - Die vorliegende Dissertation beschäftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im öffentlichen Personennahverkehr. Dieses Problem ist für die meisten praxisrelevanten Fälle schwierig (Ar'P-schwer). In dieser Arbeit präsentieren wir Methoden der ganzzahligen linearen Programmierung zur Lösung dieses Planungsproblems. "Vernünftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrgüterfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir beschäftigen uns mit beiden Ansätzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrgüterfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen führen zu riesigen LPs mit einigen Millionen ganzzahligen Variablen. Die Behandlung solcher LPs erfordert Spalten-Erzeugungs- Verfahren (auch Column-Generation-Verfahren genannt). Basierend auf Lagrange-Relaxationen entwickeln wir hierzu neue Verfahren zur Auswahl der zu erzeugenden Spalten, die wir Lagrange-Pricing nennen. Lagrange-Pricing-Techniken haben es erstmalig ermöglicht, LPs dieser Art mit rund 70 Millionen Variablen zu lösen. Für den bogenorientierten (Mehrgüter)Fluß-Zugang beschreiben wir ausführlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gelöst werden. Zusätzlich schlagen wir eine Heuristik vor, die schnell gute Lösungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der Lösung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrgüterfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell überführt werden kann. Der zweite Teil dieser Arbeit präsentiert die Rechenergebnisse zu den von uns entwickelten und implementierten Verfahren. Diese Untersuchungen basieren auf realen Testdaten von drei großen deutschen Nahverkehrsunternehmen. Die implementierten Codes arbeiten zuverlässig und stabil. Die mit diesen Verfahren durchgeführten Testläufe lieferten hervorragende Ergebnisse: Bis auf ein Problem können alle Beispiele optimal gelöst werden. Die Lösungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenwärtig eingesetzten Verfahren verglichen: Wir konnten zusätzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 % aufzeigen. Der mögliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und jährlich Einsparungen in Höhe von rund 100 Millionen Mark erzielen zu können, siehe den Artikel Auf Sparkurs zum Ziel im Rheinischer Merkur, Nummer 39, von Schmidt [1997] Teile der vorgestellten Methoden wurden bereits in die Planungssysteme BERTA (der Berliner Verkehrsbetriebe (BVG)) und MICROBUS II (der IVU Gesellschaft für Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Darüber hinaus hat auch die Forschungsabteilung der SIEMENS AG in München dieses System erworben. Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10169 ER - TY - GEN A1 - Nowak, Ulrich A1 - Gebauer, Susanna T1 - A New Test Frame for Ordinary Differential Equation Solvers N2 - Benchmarking of ODE methods has a long tradition. Several sets of test problems have been developed and new problems are still collected. So, a whole variety of problems can be used to check the efficiency of a method under investigation. In general, efficiency is measured by the amount of work whi ch is necessary to get a reliable solution for a prescribed accura cy. In order to quantify the term ``amount of work'' usually not only the computing time is measured but also the number of calls of functional units. To quantify the term ``quality of a numerical solution'' usually the $l_2$--norm of the true error at the final point of the integration interval is used. In our contribution we first discuss some general aspects of benchmarking. Then we present a new test frame which allows to solve typical benchmark problems with some of the state of the art integrators within a unified framework. Finally we show some results of our benchmark tests. Part of the test frame can be used interactively in the World Wide Web. T3 - ZIB-Report - SC-97-68 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3370 ER - TY - GEN A1 - Nowak, Ulrich A1 - Ehrig, Rainald A1 - Oeverdieck, Lars T1 - Parallel Extrapolation Methods and Their Application in Chemical Engineering N2 - We study the parallelization of linearly--implicit extrapolation methods for the solution of large scale systems of differential algebraic equations arising in a method of lines (MOL ) treatment of partial differential equations. In our approach we combine a slightly overlapping domain decomposi tion together with a polynomial block Neumann preconditioner. Through the explicit computation of the matrix products of the pre conditioner and the system matrix a significant gain in overall efficiency is achieved for medium--sized problems. The parallel algorithm exhibits a good scalability up to 32 proces sors on a Cray T3E. Preliminary results for computations on a workstation cluster are reported. T3 - ZIB-Report - SC-97-69 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3387 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints N2 - In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time. T3 - ZIB-Report - SC-97-70 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3391 ER - TY - GEN A1 - Beck, Rudolf A1 - Deuflhard, Peter A1 - Hiptmair, Ralf A1 - Hoppe, Ronald H. W. A1 - Wohlmuth, Barbara T1 - Adaptive Multilevel Methods for Edge Element Discretizations of Maxwell's Equations N2 - The focus of this paper is on the efficient solution of boundary value problems involving the double-- curl operator. Those arise in the computation of electromagnetic fields in various settings, for instance when solving the electric or magnetic wave equation with implicit timestepping, when tackling time--harmonic problems or in the context of eddy--current computations. Their discretization is based on on N\'ed\'elec's {\bf H(curl}; $\Omega$)--conforming edge elements on unstructured grids. In order to capture local effects and to guarantee a prescribed accuracy of the approximate solution adaptive refinement of the grid controlled by a posteriori error estimators is employed. The hierarchy of meshes created through adaptive refinement forms the foundation for the fast iterative solution of the resulting linear systems by a multigrid method. The guiding principle underlying the design of both the error estimators and the multigrid method is the separate treatment of the kernel of the curl--operator and its orthogonal complement. Only on the latter we have proper ellipticity of the problem. Yet, exploiting the existence of computationally available discrete potentials for edge element spaces, we can switch to an elliptic problem in potential space to deal with nullspace of curl. Thus both cases become amenable to strategies of error estimation and multigrid solution developed for second order elliptic problems. The efficacy of the approach is confirmed by numerical experiments which cover several model problems and an application to waveguide simulation. T3 - ZIB-Report - SC-97-66 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3356 ER - TY - GEN A1 - Fischer, Alexander A1 - Cordes, Frank A1 - Schütte, Christof T1 - Hybrid Monte Carlo with Adaptive Temperature in a Mixed-Canonical Ensemble: Efficient Conformational Analysis of RNA N2 - A hybrid Monte Carlo method with adaptive temperature choice is presented, which exactly generates the distribution of a mixed-canonical ensemble composed of two canonical ensembles at low and high temperature. The analysis of resulting Markov chains with the reweighting technique shows an efficient sampling of the canonical distribution at low temperature, whereas the high temperature component facilitates conformational transitions, which allows shorter simulation times. \\The algorithm was tested by comparing analytical and numerical results for the small n-butane molecule before simulations were performed for a triribonucleotide. Sampling the complex multi-minima energy landscape of these small RNA segments, we observed enforced crossing of energy barriers. T3 - ZIB-Report - SC-97-67 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3364 ER - TY - GEN A1 - Bornemann, Folkmar A. T1 - Homogenization in Time II: Mechanical Systems Subject to Friction and Gyroscopic Forces N2 - In our previous work [Preprint SC 97-48] we have studied natural mechanical systems on Riemannian manifolds with a strong constraining potential. These systems establish fast nonlinear oscillations around some equilibrium manifold. Important in applications, the problem of elimination of the fast degrees of freedom, or {\em homogenization in time}, leads to determine the singular limit of infinite strength of the constraining potential. In the present paper we extend this study to systems which are subject to external forces that are non-potential, depending in a mixed way on positions {\em and}\/ velocities. We will argue that the method of weak convergence used in [1997] covers such forces if and only if they result from viscous friction and gyroscopic terms. All the results of [1997] directly extend if there is no friction transversal to the equilibrium manifold; elsewise we show that instructive modifications apply. T3 - ZIB-Report - SC-97-65 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3348 ER - TY - GEN A1 - Schmidt, Frank T1 - Computation of Discrete Transparent Boundary Conditions for the 2D Helmholtz Equation N2 - We present a family of nonlocal transparent boundary conditions for the 2D Helmholtz equation. The whole domain, on which the Helmholtz equation is defined, is decomposed into an interior and an exterior domain. The corresponding interior Helmholtz problem is formulated as a variational problem in standard manner, representing a boundary value problem, whereas the exterior problem is posed as an initial value problem in the radial variable. This problem is then solved approximately by means of the Laplace transformation. The derived boundary conditions are asymptotically correct, model inhomogeneous exterior domains and are simple to implement. T3 - ZIB-Report - SC-97-64 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3330 ER - TY - GEN A1 - Ehrig, Rainald A1 - Deuflhard, Peter T1 - GMERR - an Error Minimizing Variant of GMRES N2 - The paper analyzes a recently proposed iterative error minimizing method for the solution of linear systems. Sufficient and necessary conditions for convergence are studied, which show that the method essentially requires normal matrices. An efficient implementation similar to GMRES has been worked out in detail. Numerical tests on general non--normal matrices, of course, indicate that this approach is not competitive with GMRES. Summarizing, if error minimizing is important, one should rather choose CGNE. A computational niche for GMERR might be problems, where normal but non--symmetric matrices occur, like dissipative quantum mechanics. T3 - ZIB-Report - SC-97-63 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3323 ER - TY - GEN A1 - Wolf, Thomas T1 - Structural equations for Killing tensors of arbitrary rank N2 - An algorithm is given for bringing the equations of monomial first integrals of arbitrary degree of the geodesic motion in a Riemannian space $V_n$ into the form $(F_A)_{;k} = \sum_B \Gamma_{kAB} F_B$. The $F_A$ are the components of a Killing tensor $K_{i_1\ldots i_r}$ of arbitrary rank $r$ and its symmetrized covariant derivatives. Explicit formulas are given for rank 1,2 and 3. %The maximal number of Killing tensors %(reducible + non-reducible) is found to be %$\frac{1}{r+1}\left( ^{n + r - 1}_{\;\;\;\;\,r} \right) % \left( ^{ n+r}_{\;\;\,r} \right)$. Killing tensor equations in structural form allow the formulation of algebraic integrability conditions and are supposed to be well suited for integration as it is demonstrated in the case of flat space. An alternative proof of the reducibility of these Killing tensors is given which shows the correspondence to structural equations for rank 2 Killing tensors as formulated by Hauser & Malhiot. They used tensors with different symmetry properties. T3 - ZIB-Report - SC-97-62 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3310 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Intersection of Knapsack Polyhedra and Extensions N2 - This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported. T3 - ZIB-Report - SC-97-61 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3300 ER - TY - GEN A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Seebass, Martin T1 - Optimization of Temperature Distributions for Regional Hyperthermia Based on a Nonlinear Heat Transfer Model N2 - We describe an optimization process specially designed for regional hyperthermia of deap seated tumors in order to achieve desired steady--state temperature distributions. A nonlinear three--dimensional heat--transfer model based on temperature--dependent blood perfusion is applied to predict the temperature. Optimal heating is obtained by minimizing an integral object function which measures the distance between desired and model predicted temperatures. Sequential minima are calculated from successively improved constant--rate perfusion models employing a damped Newton method in an inner iteration. Numerical results for a Sigma 60 applicator are presented. This work has been supported by Deutsche Forschungsgemeinschaft (DFG) within the Sonderforschungsbereich 273 \glqq Hyperthermie: Methodik und Klinik \grqq . T3 - ZIB-Report - SC-97-59 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3283 ER - TY - GEN A1 - Schmidt, Frank T1 - Construction of Discrete Transparent Boundary Conditions for Schrödinger-Type Equations N2 - We present a general technique for constructing nonlocal transparent boundary conditions for time-discretized one-dimensional Schrödinger type equations. The main tool of construction is the discrete counterpart to Mikusi\'nski's continuous algebraic operator approach. Existing techniques are simplified and generalized. Both adaptive time-steps and time-dependent exterior potentials are taken into account. T3 - ZIB-Report - SC-97-60 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3292 ER - TY - GEN A1 - Wolf, Thomas T1 - Killing Pairs in Flat Space N2 - In this paper the integrability conditions for Killing pairs in flat spaces are investigated and it is shown that only trivial Killing pairs exist. T3 - ZIB-Report - SC-97-58 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3275 ER - TY - GEN A1 - Friese, Tilmann T1 - On the Computation of Eigenmodes of Integrated Optical Components N2 - The paper deals with the solution of the eigenvalue problem of the complex Helmholtz equation. We concentrate on multigrid methods for solving the algebraic eigenproblems arising from discretization with finite elements by using adaptive generated meshes. An illustrative numerical example, the simulation of a waveguide structure from integrated optics, is included. T3 - ZIB-Report - SC-97-57 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3268 ER - TY - GEN A1 - Nettesheim, Peter A1 - Reich, Sebastian T1 - Symplectic Multiple-Time-Stepping Integrators for Quantum-Classical Molecular Dynamics N2 - The overall Hamiltonian structure of the Quantum-Classical Molecular Dynamics model makes - analogously to classical molecular dynamics - symplectic integration schemes the methods of choice for long-term simulations. This has already been demonstrated by the symplectic PICKABACK method. However, this method requires a relatively small step-size due to the high-frequency quantum modes. Therefore, following related ideas from classical molecular dynamics, we investigate symplectic multiple-time-stepping methods and indicate various possibilities to overcome the step-size limitation of PICKABACK. T3 - ZIB-Report - SC-97-56 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3250 ER - TY - GEN A1 - Deuflhard, Peter A1 - Friese, Tilmann A1 - Schmidt, Frank T1 - A Nonlinear Multigrid Eigenproblem Solver for the Complex Helmholtz Equation N2 - The paper is motivated by the need for a fast robust adaptive multigrid method to solve complex Helmholtz eigenvalue problems arising from the design of optical chips. A nonlinear multigrid method is developed, which can be regarded as an extension of a previous adaptive Rayleigh quotient minimization method for selfadjoint Helmholtz eigenproblems. Since the complex Helmholtz operator is just a compact nonselfadjoint perturbation of a selfadjoint operator, linear algebra techniques like Schur decomposition can be extended from the finite dimensional case. The efficiency of the derived adaptive nonlinear multigrid method is illustrated by computations for a technologically relevant integrated optics component containing Multi Quantum Well Layers. T3 - ZIB-Report - SC-97-55 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3240 ER - TY - GEN A1 - Müller, Peter A1 - Decker, Ingmar T1 - The Electronic Visualization Library N2 - Scientific visualization is a rapidly growing research field with a need for information dissemination. This report describes the Electronic Visualization Library (EVlib), a digital library for scientific visualization. Main design goals of EVlib were an attractive user interface providing various kind of access mechanisms as well as an open interface to other already established information systems. EVlib stores fulltext versions of documents where they are available. We also provide access to BibTeX entries for every stored document. All available BibTeX entries are combined in BibTeX bibliographies which are registered with the ``Collection of Computer Science Bibliographies'' at University of Karlsruhe. Additionally, we have defined a mapping from BibTeX attributes to the Dublin Core attribute set. This mapping is used to provide a gatherer interface for the Harvest information system. This way, existing Harvest installations can immediately use EVlib as an information resource. T3 - ZIB-Report - TR-97-09 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5517 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs N2 - This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code. T3 - ZIB-Report - SC-97-54 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3230 ER - TY - GEN A1 - Reich, Sebastian T1 - Modified potential energy functions for constrained molecular dynamics N2 - In molecular dynamics the highly oscillatory vibrations in the chemical bonds are often replaced by holonomic constraints that freeze the bond length/angle to its equilibrium value. In some cases this approach can be justified if the force constants of the bond vibrations are sufficiently large. However, for moderate values of the force constant, the constrained system might lead to a dynamical behavior that is too ``rigid'' compared to the flexible model. To compensate for this effect, the concept of soft constraints was introduced [Reich 1997, Reich 1995, Reich 1996]. However, its implementation is rather expensive. In this paper, we suggest an alternative approach that modifies the force field instead of the constraint functions. This leads to a more efficient method that avoids the resonance induced instabilities of multiple-time-stepping [Bishop 1996] and the above described effect of standard constrained dynamics. T3 - ZIB-Report - SC-97-49 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3189 ER - TY - GEN A1 - Ascher, Uri A1 - Reich, Sebastian T1 - On some difficulties in integrating highly oscillatory Hamiltonian systems N2 - The numerical integration of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or Hamiltonian partial differential equations, is a challenging task. Various methods have been suggested to overcome the step-size restrictions of explicit methods such as the Verlet method. Among these are multiple-time-stepping, constrained dynamics, and implicit methods. In this paper, we investigate the suitability of time-reversible, semi-implicit methods. Here semi-implicit means that only the highly oscillatory part is integrated by an implicit method such as the midpoint method or an energy-conserving variant of it. The hope is that such methods will allow one to use a step-size $k$ which is much larger than the period $\varepsilon$ of the fast oscillations. However, our results are discouraging. Even in the absence of resonance-type instabilities, we show that in general one must require that $k^2/\varepsilon$ be small enough. Otherwise the method might become unstable and/or it might lead to a wrong approximation of the slowly varying solution components. The latter situation might, in some cases, even require that $k/\varepsilon$ be small in order to avoid this danger. While certain (semi-implicit) energy conserving methods prove to be robust for some model problems, they may also yield deceptively-looking, wrong solutions for other simple model problems, in circumstances where the corresponding constrained dynamics formulation may not be easily derived and used. T3 - ZIB-Report - SC-97-50 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3193 ER - TY - GEN A1 - Ascher, Uri A1 - Reich, Sebastian T1 - The midpoint scheme and variants for Hamiltonian systems: advantages and pitfalls N2 - The (implicit) midpoint scheme, like higher order Gauss-collocation schemes, is algebraically stable and symplectic, and it preserves quadratic integral invariants. It may appear particularly suitable for the numerical solution of highly oscillatory Hamiltonian systems, such as those arising in molecular dynamics or structural mechanics, because there is no stability restriction when it is applied to a simple harmonic oscillator. Although it is well-known that the midpoint scheme may also exhibit instabilities in various stiff situations, one might still hope for good results when resonance-type instabilities are avoided. In this paper we investigate the suitability of the midpoint scheme for highly oscillatory, frictionless mechanical systems, where the step-size $k$ is much larger than the system's small parameter $\varepsilon$, in case that the solution remains bounded as $\varepsilon \rightarrow 0$. We show that in general one must require that $k^2/\varepsilon$ be small enough, or else, even the errors in slowly varying quantities like the energy may grow undesirably (especially when fast and slow modes are tightly coupled) or, worse, the computation may yield misleading information. In some cases this may already happen when $k = O(\varepsilon )$. The same holds for higher order collocation at Gaussian points. The encountered restrictions on $k$ are still better than the corresponding ones for explicit schemes. T3 - ZIB-Report - SC-97-51 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3201 ER - TY - GEN A1 - Reich, Sebastian T1 - Preservation of Adiabatic Invariants under Symplectic Discretization N2 - Symplectic methods, like the Verlet method, are a standard tool for the long term integration of Hamiltonian systems as they arise, for example, in molecular dynamics. One of the reasons for the popularity of symplectic methods is the conservation of energy over very long periods of time up to small fluctuations that scale with the order of the method. In this paper, we discuss a qualitative feature of Hamiltonian systems with separated time scales that is also preserved under symplectic discretization. Specifically, highly oscillatory degrees of freedom often lead to almost preserved quantities (adiabatic invariants). Using recent results from backward error analysis and normal form theory, we show that a symplectic method, like the Verlet method, preserves those adiabatic invariants. We also discuss step-size restrictions necessary to maintain adiabatic invariants in practical computations. T3 - ZIB-Report - SC-97-52 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3210 ER - TY - GEN A1 - Barth, Eric A1 - Leimkuhler, Benedict A1 - Reich, Sebastian T1 - A Time-Reversible Variable-Stepsize Integrator for Constrained Dynamics N2 - This article considers the design and implementation of variable-timestep methods for simulating holonomically constrained mechanical systems. Symplectic variable stepsizes are briefly discussed, we then consider time-reparameterization techniques employing a time-reversible (symmetric) integration method to solve the equations of motion. We give several numerical examples, including a simulation of an elastic (inextensible, unshearable) rod undergoing large deformations and collisions with the sides of a bounding box. Numerical experiments indicate that adaptive stepping can significantly smooth the numerical energy and improve the overall efficiency of the simulation. T3 - ZIB-Report - SC-97-53 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3220 ER - TY - GEN A1 - Lang, Jens A1 - Merz, Wilhelm T1 - Numerical Simulation of Single Species Dopant Diffusion in Silicon under Extrinsic Conditions N2 - In this article we consider a general model for phosphorus diffusion in silicon under extrinsic doping conditions. At such high concentrations we have to include the charged species and the internal electric field of the crystal, both of which can have profound effects on diffusion. In principle, this leads to a very large number of drift--diffusion--reaction equations: one for each charge state of every species, plus one Poisson equation to describe the internal electric field (in terms of the electron/hole concentration). The number of equations can be reduced substantially by making additional assumptions on the distribution of charge states and local equilibrium assumptions concerning the reaction terms. The resulting model turns out to be very interesting for numerical investigation. We solve the problem numerically in two space dimensions with the adaptive finite element program KARDOS and describe the numerical method used here to treat the resulting drift--diffusion--reaction problem. T3 - ZIB-Report - SC-97-47 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3163 ER - TY - THES A1 - Bornemann, Folkmar A. T1 - Homogenization in Time of Singularly Perturbed Conservative Mechanical Systems N2 - We present a particular method for the explicit elimination of rapidly oscillating micro-scales in certain singularly perturbed conservative mechanical systems. Non-linear effects call for a non-trivial averaging procedure that we call {\em homogenization in time.} This method is based on energy principles and weak convergence techniques. Since non-linear functionals are in general {\em not} weakly sequentially continuous, we have to study {\em simultaneously} the weak limits of all those non-linear quantities of the rapidly oscillating components which are of importance for the underlying problem. Using the physically motivated concepts of {\em virial theorems}, {\em adiabatic invariants}, and {\em resonances}, we will be able to establish sufficiently many relations between all these weak limits, allowing to calculate them explicitly. Our approach will be {\em paradigmatical} rather than aiming at the largest possible generality. This way, we can show most clearly how concepts and notions from the physical background of the underlying mathematical problem enter and help to determine relations between weak limit quantities. In detail we will discuss natural mechanical systems with a strong constraining potential on Riemannian manifolds, the questions of realization of holonomic constraints, and singular limits of mixed quantum-classical coupling models. This latter class of problems also leads to a new proof for the adiabatic theorem of quantum mechanics. The strength of our methodology will be illustrated by applications to problems from plasma physics, molecular dynamics and quantum chemistry. T3 - ZIB-Report - SC-97-48 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3170 ER - TY - GEN A1 - Wagler, Annegret T1 - Critical Edges in Perfect Graphs and Some Polyhedral Consequences N2 - An edge $e$ of a perfect graph $G$ is called critical if $G-e$ is imperfect. For certain graphs $G-e$ of this type, we determine all minimally imperfect subgraphs. We use this knowledge to describe inequalities inducing facets of the stable set polytope associated with $G-e$.\\ T3 - ZIB-Report - SC-97-46 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3153 ER - TY - GEN A1 - Kornhuber, Ralf T1 - Globally Convergent Multigrid Methods for Porous Medium Type Problems N2 - We consider the fast solution of large, piecewise smooth minimization problems as typically arising from the finite element discretization of porous media flow. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with {\em constrained} Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give logarithmic upper bounds for the asymptotic convergence rates. T3 - ZIB-Report - SC-97-45 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3142 ER - TY - GEN A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Seebass, Martin T1 - Adaptive Solutions of Nonlinear Parabolic Equations with Application to Hyperthermia Treatments N2 - We present a self-adaptive finite element method to solve nonlinear evolution problems in 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. The proposed method is applied to hyperthermia treatments to demonstrate its potential for the solving of complicated problems. T3 - ZIB-Report - SC-97-44 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3130 ER - TY - GEN A1 - Schulz, Sandra A1 - Busch, Hubert T1 - Schlussbericht des Berliner Regionalen Testbed (BRTB) Projektes N2 - Im März 1993 wurde das Projekt ,Regionales Testbed - RTB" in den DFN-Mitteilungen bundesweit mit folgenden Zielen ausgeschrieben und festgelegt: Einführung bzw. Pilotnutzung fortgeschrittener Netztechniken, Entwicklung von Anwendungsumgebungen mit Bedarf für hohe Übertragungsraten und Einsatz von Anwendungsumgebungen durch nachgewiesene Anwendergruppen. Die Ziele sollten durch die Vernetzung einer beschränkten Anzahl von Institutionen (Universitäten, Fachhochschulen und Forschungseinrichtungen) der jeweiligen Region, die sowieso schon einen hohen Kommunikationsbedarf untereinander hatten, erreicht werden. Die Berliner Universitäten, das HMI, das ISST und das LIT führten unter Federführung des ZIB für die Region Berlin ein regionales Testbed durch; dessen Projektlaufzeit lag im wesentlichen zwischen dem 1. Oktober 1994 und dem 30. September 1996. An diesem BRTB waren fünf Anwendungen beteiligt: \begin{itemize} \item Einheitliche Datenumgebung auf heterogenen Rechnersystemen \item Ein Hotline und Consulting System \item Medizinische Bildverarbeitung \item Hypermedia-Lehreinheiten in der Studentenausbildung \item Visualisierung wissenschaftlicher Daten \end{itemize} Das wesentliche Ziel, der Aufbau von finanzierbaren regionalen Breitbandnetzen als Voraussetzung für ein deutschland-weites Breitband-Wissenschaftsnetz, ist erreicht worden. Wir danken dem DFN-Verein und dem BMBF für die Förderung dieses Projektes und allen, die zu seinem Gelingen beigetragen haben. T3 - ZIB-Report - TR-97-07 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5496 ER -