@misc{HuberRambauSantos1999, author = {Huber, Birkett and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3874}, number = {SC-98-44}, year = {1999}, abstract = {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.}, language = {en} } @misc{AthanasiadisRambauSantos1999, author = {Athanasiadis, Christos A. and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Generalized Baues Problem for Cyclic Polytopes II}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3862}, number = {SC-98-43}, year = {1999}, abstract = {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\$.}, language = {en} } @misc{Decker1999, author = {Decker, Ingmar}, title = {A Picture-based Document Retrieval Service for the Electronic Visualization Library}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5689}, number = {TR-98-07}, year = {1999}, abstract = {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{\"u}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.}, language = {en} } @misc{SchuetteFischerHuisingaetal.1999, author = {Sch{\"u}tte, Christof and Fischer, Alexander and Huisinga, Wilhelm and Deuflhard, Peter}, title = {A Direct Approach to Conformational Dynamics based on Hybrid Monte Carlo}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3889}, number = {SC-98-45}, year = {1999}, abstract = {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.}, language = {en} } @misc{Wolf1999, author = {Wolf, Thomas}, title = {A comparison of four approaches to the calculation of conservation laws}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3896}, number = {SC-99-01}, year = {1999}, abstract = {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.}, language = {en} } @misc{SokolovWolf1999, author = {Sokolov, Vladimir V. and Wolf, Thomas}, title = {A symmetry test for quasilinear coupled systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3901}, number = {SC-99-02}, year = {1999}, abstract = {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)\$.}, language = {en} } @phdthesis{Friese1998, author = {Friese, Tilmann}, title = {Eine Mehrgitter-Methode zur L{\"o}sung des Eigenwertproblems der komplexen Helmholtzgleichung}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:188-1999000133}, year = {1998}, language = {en} } @phdthesis{Borndoerfer1998, author = {Bornd{\"o}rfer, Ralf}, title = {Aspects of Set Packing, Partitioning, and Covering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10126}, year = {1998}, abstract = {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.}, language = {en} } @misc{BestHege1998, author = {Best, Christoph and Hege, Hans-Christian}, title = {Visualizing conformations in molecular dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3859}, number = {SC-98-42}, year = {1998}, abstract = {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.}, language = {en} } @misc{Best1998, author = {Best, Christoph}, title = {A simple C++ library for manipulating scientific data sets as structured data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5674}, number = {TR-98-06}, year = {1998}, abstract = {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.}, language = {en} } @misc{BorndoerferLoebelStrubbeetal.1998, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Strubbe, Uwe and V{\"o}lker, Manfred}, title = {Zielorientierte Dienstplanoptimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3847}, number = {SC-98-41}, year = {1998}, abstract = {Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im {\"O}PNV. Der Ansatz zielt auf die vollst{\"a}ndige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Ber{\"u}cksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenw{\"a}rtig in einem vom Bundesministerium f{\"u}r Bildung und Forschung ({\tt bmb+f}) gef{\"o}rderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum f{\"u}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 {\"u}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 {\"u}ber den Stand der Entwicklung.}, language = {de} } @misc{StallingZoecklerSanderetal.1998, author = {Stalling, Detlev and Z{\"o}ckler, Malte and Sander, Oliver and Hege, Hans-Christian}, title = {Weighted Labels for 3D Image Segmentation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3828}, number = {SC-98-39}, year = {1998}, abstract = {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.}, language = {en} } @phdthesis{Stalling1998, author = {Stalling, Detlev}, title = {Fast Texture-Based Algorithms for Vector Field Visualization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3838}, number = {SC-98-40}, year = {1998}, abstract = {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.}, language = {en} } @misc{KedziorskiKehlPaetsch1998, author = {Kedziorski, Rafal and Kehl, Detlef and Paetsch, Olaf}, title = {Client-Server-Anwendung zur Steuerung von Ausgabeger{\"a}ten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5658}, number = {TR-98-04}, year = {1998}, abstract = {\\{\bf Zusammenfassung: }\noindent Die Steuerung von grafischen Ausgabeger{\"a}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 {\"u}bersichtlichen Einstellung aller m{\"o}glichen Parameter und Optionen an. Wenn dieses Ger{\"a}t zudem nur {\"u}ber eine besondere Treiber-Software zu bedienen ist und in einem heterogenen Intranet zur Verf{\"u}gung gestellt werden soll, ist eine Steuerung mittels eines WWW-Servers naheliegend. Im Folgenden sollen L{\"o}sungsans{\"a}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.}, language = {de} } @misc{StallingSeebassZachow1998, author = {Stalling, Detlev and Seebass, Martin and Zachow, Stefan}, title = {Mehrschichtige Oberfl{\"a}chenmodelle zur computergest{\"u}tzten Planung in der Chirurgie}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5661}, number = {TR-98-05}, year = {1998}, abstract = {Polygonale Sch{\"a}delmodelle bilden ein wichtiges Hilfsmittel f{\"u}r computergest{\"u}tzte Planungen im Bereich der plastischen Chirurgie. Wir beschreiben, wie derartige Modelle automatisch aus hochaufgel{\"o}sten CT-Datens{\"a}tzen erzeugt werden k{\"o}nnen. Durch einen lokal steuerbaren Simplifizierungsalgorithmus werden die Modelle so weit vereinfacht, daß auch auf kleineren Graphikcomputern interaktives Arbeiten m{\"o}glich wird. Die Verwendung eines speziellen Transparenzmodells erm{\"o}glicht den ungehinderten Blick auf die bei der Planung relevanten Knochenstrukturen und l{\"a}ßt den Benutzer zugleich die Kopfumrisse des Patienten erkennen.}, language = {de} } @misc{SchuetteNettesheim1998, author = {Sch{\"u}tte, Christof and Nettesheim, Peter}, title = {Non-Adiabatic Effects in Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3817}, number = {SC-98-38}, year = {1998}, abstract = {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.}, language = {en} } @misc{Nettesheim1998, author = {Nettesheim, Peter}, title = {Second Order Transitions in Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3805}, number = {SC-98-37}, year = {1998}, abstract = {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{\"o}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.}, language = {en} } @misc{HuisingaBestCordesetal.1998, author = {Huisinga, Wilhelm and Best, Christoph and Cordes, Frank and Roitzsch, Rainer and Sch{\"u}tte, Christof}, title = {From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3797}, number = {SC-98-36}, year = {1998}, abstract = {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.}, language = {en} } @misc{Kuberek1998, author = {Kuberek, Monika}, title = {Bibliothekarische Inhalte und Zielsetzungen des KOBV}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5646}, number = {TR-98-03}, year = {1998}, abstract = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wurde 1997 auf politische Initiative hin gegr{\"u}ndet, um f{\"u}r die ressourcenreiche, aber elektronisch unzul{\"a}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{\"a}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.}, language = {de} } @misc{DeuflhardWeiserSeebass1998, author = {Deuflhard, Peter and Weiser, Martin and Seebass, Martin}, title = {A New Nonlinear Elliptic Multilevel FEM Applied to Regional Hyperthermia}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3785}, number = {SC-98-35}, year = {1998}, abstract = {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.}, language = {en} } @misc{KuehnKorzenPaetsch1998, author = {K{\"u}hn, Wolfgang and Korzen, Manfred and Paetsch, Olaf}, title = {Fast Data Assimilation in Fire Tests of Steel Members}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3766}, number = {SC-98-33}, year = {1998}, abstract = {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.}, language = {en} } @misc{AscheuerKrumkeRambau1998, author = {Ascheuer, Norbert and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Transportation Problem: Competitive Scheduling of Elevators}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3779}, number = {SC-98-34}, year = {1998}, abstract = {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.}, language = {en} } @misc{Kuehn1998, author = {K{\"u}hn, Wolfgang}, title = {iTe 1.1 User's Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5638}, number = {TR-98-02}, year = {1998}, abstract = {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.}, language = {en} } @misc{Schmidt1998, author = {Schmidt, Frank}, title = {An Alternative Derivation of the Exact DtN-Map on a Circle}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3752}, number = {SC-98-32}, year = {1998}, abstract = {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.}, language = {en} } @misc{SchneiderBottaGeratzetal.1998, author = {Schneider, Thomas and Botta, Nicola and Geratz, Karl Josef and Klein, Rupert}, title = {Extension of finite volume compressible flow solvers to multi-dimensional, variable density zero Mach number flow}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3749}, number = {SC-98-31}, year = {1998}, abstract = {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.}, language = {en} } @misc{DeuflhardSeebass1998, author = {Deuflhard, Peter and Seebass, Martin}, title = {Adaptive Multilevel FEM as Decisive Tools in the Clinical Cancer Therapy Hyperthermia}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3739}, number = {SC-98-30}, year = {1998}, abstract = {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).}, language = {en} } @misc{HuisingaPesceKosloffetal.1998, author = {Huisinga, Wilhelm and Pesce, Lorenzo and Kosloff, Ronnie and Saalfrank, Peter}, title = {Faber and Newton Polynomial Integrators for Open-System Density Matrix Propagation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3725}, number = {SC-98-29}, year = {1998}, abstract = {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.}, language = {en} } @misc{BrunsGubeladzeHenketal.1998, author = {Bruns, Winfried and Gubeladze, Joseph and Henk, Martin and Martin, Alexander and Weismantel, Robert}, title = {A counterexample to an integer analogue of Caratheodorys theorem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3718}, number = {SC-98-28}, year = {1998}, abstract = {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.}, language = {en} } @misc{Steinbach1998, author = {Steinbach, Marc}, title = {Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3706}, number = {SC-98-27}, year = {1998}, abstract = {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.}, language = {en} } @misc{GroetschelLuegger1998, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Scientific Information Systems and Metadata}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3698}, number = {SC-98-26}, year = {1998}, abstract = {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} .}, language = {en} } @misc{GroetschelDalitzWinczewski1998, author = {Gr{\"o}tschel, Martin and Dalitz, Wolfgang and Winczewski, Vincent}, title = {Math-Net: Ein Informationssystem der Mathematik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3680}, number = {SC-98-25}, year = {1998}, abstract = {In diesem Artikel geben wir einen {\"U}berblick {\"u}ber das Math-Net-Projekt. Wir berichten {\"u}ber die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems f{\"u}r die Mathematik in Deutschland.}, language = {de} } @misc{AscheuerGroetschelKrumkeetal.1998, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3674}, number = {SC-98-24}, year = {1998}, abstract = {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.}, language = {en} } @misc{Steinbach1998, author = {Steinbach, Marc}, title = {Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3661}, number = {SC-98-23}, year = {1998}, abstract = {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.}, language = {en} } @misc{LourencoRosaCastroetal.1998, author = {Lourenco, Maria Jos{\´e} and Rosa, Samuel Costa S. and Castro, Carlos Alberto Nieto de and Albuquerque, C. and Erdmann, Bodo and Lang, Jens and Roitzsch, Rainer}, title = {Simulation of the Transient Heating in an Unsymmetrical Coated Hot--Strip Sensor with a Self--Adaptive Finite Element Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3656}, number = {SC-98-22}, year = {1998}, abstract = {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.}, language = {en} } @misc{BrandtBrandt1998, author = {Brandt, Andreas and Brandt, Manfred}, title = {On a Two-Queue Priority System with Impatience and its Application to a Call Center}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3641}, number = {SC-98-21}, year = {1998}, abstract = {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.}, language = {en} } @misc{Bley1998, author = {Bley, Andreas}, title = {On the Complexity of Vertex-Disjoint Length-Restricted Path Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3639}, number = {SC-98-20}, year = {1998}, abstract = {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.}, language = {en} } @phdthesis{Reich1998, author = {Reich, Sebastian}, title = {Dynamical Systems, Numerical Integration, and Exponentially Small Estimates}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3622}, number = {SC-98-19}, year = {1998}, abstract = {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).}, language = {en} } @misc{MartinWeismantel1998, author = {Martin, Alexander and Weismantel, Robert}, title = {Conjunctive Cuts for Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3618}, number = {SC-98-18}, year = {1998}, abstract = {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.}, language = {en} } @misc{HolderLeimkuhlerReich1998, author = {Holder, Thomas and Leimkuhler, Benedict and Reich, Sebastian}, title = {Explicit Variable Step-Size and Time-Reversible Integration}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3607}, number = {SC-98-17}, year = {1998}, abstract = {A variable step-size, semi-explicit variant of the explicit St{\"o}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.}, language = {en} } @misc{Lang1998, author = {Lang, Jens}, title = {Adaptive Incompressible Flow Computations with Linearly Implicit Time Discretization and Stabilized Finite Elements}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3599}, number = {SC-98-16}, year = {1998}, abstract = {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.}, language = {en} } @misc{OPUS4-972, title = {Jahresbericht 1997}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9722}, number = {1997}, year = {1998}, language = {de} } @misc{RoitzschErdmannLang1998, author = {Roitzsch, Rainer and Erdmann, Bodo and Lang, Jens}, title = {The Benefits of Modularization: from KASKADE to KARDOS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3586}, number = {SC-98-15}, year = {1998}, abstract = {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.}, language = {en} } @misc{RambauSantos1998, author = {Rambau, J{\"o}rg and Santos, Francisco}, title = {The Generalized Baues Problem for Cyclic Polytopes I.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3579}, number = {SC-98-14}, year = {1998}, abstract = {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.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, year = {1998}, abstract = {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.}, language = {en} } @misc{BleyGroetschelWessaely1998, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3565}, number = {SC-98-13}, year = {1998}, abstract = {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.}, language = {en} } @misc{CaroeeSchultz1998, author = {Car{\"o}e, Claus C. and Schultz, R{\"u}diger}, title = {A Two-Stage Stochastic Program for Unit Commitment Under Uncertainty in a Hydro-Thermal Power System}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3543}, number = {SC-98-11}, year = {1998}, abstract = {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.}, language = {en} } @misc{DaisHausHenk1998, author = {Dais, Dimitrios I. and Haus, Utz-Uwe and Henk, Martin}, title = {On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3559}, number = {SC-98-12}, year = {1998}, abstract = {\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.}, language = {en} } @misc{Kornhuber1998, author = {Kornhuber, Ralf}, title = {Monotone Iterations for Elliptic Variational Inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3539}, number = {SC-98-10}, year = {1998}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelLoebel1998, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Optimization of Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3529}, number = {SC-98-09}, year = {1998}, abstract = {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.}, language = {en} } @misc{AbdelHamidAscheuerGroetschel1998, author = {Abdel-Hamid, Atef Abdel-Aziz and Ascheuer, Norbert and Gr{\"o}tschel, Martin}, title = {Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3519}, number = {SC-98-08}, year = {1998}, abstract = {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.}, language = {en} } @misc{FoupouagnigniRonveauxKoepf1998, author = {Foupouagnigni, Mama and Ronveaux, Andre and Koepf, Wolfram}, title = {Fourth-Order q-Difference Equation for the First Associated of the q-Classical Orthogonal Polynomials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3490}, number = {SC-98-06}, year = {1998}, abstract = {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.}, language = {en} } @misc{AscheuerGroetschelKaminetal.1998, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Kamin, Nicola and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization in Practice}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3508}, number = {SC-98-07}, year = {1998}, abstract = {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.}, language = {en} } @misc{Wolters1998, author = {Wolters, Christof}, title = {GOS Thesaurus--Handbuch zum Projekt: Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5616}, number = {TR-97-19}, year = {1998}, abstract = {Das GOS Thesaurus--Handbuch wurde f{\"u}r die Teilnehmer des von der Robert Bosch Stiftung gef{\"o}rderten Projekts zum Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern geschrieben. Es basiert auf verschiedenen vom Institut f{\"u}r Museumskunde gemeinsam mit dem ZIB durchgef{\"u}hrten Projekten und beschreibt mit zahlreichen Beispielen Struktur und Aufbau eines Thesaurus.}, language = {de} } @misc{SaroSchroederVolkmann1998, author = {Saro, Carlos and Schr{\"o}der, Beate and Volkmann, Katrin}, title = {GOS Benutzer--Handbuch. Anleitung zum Projekt: Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5584}, number = {TR-97-16}, year = {1998}, abstract = {Das Handbuch enth{\"a}lt eine ausf{\"u}hrliche Einf{\"u}hrung in das am ZIB f{\"u}r den Einsatz in der Museumsdokumentation entwickelte Datenbanksystem GOS.}, language = {de} } @misc{ClemensSaro1998, author = {Clemens, Hans-H. and Saro, Carlos}, title = {Abschlussbericht f{\"u}r das Projekt: Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5595}, number = {TR-97-17}, year = {1998}, abstract = {Von Januar 1995 bis Februar 1997 wurde am ZIB ein von der Robert Bosch Stiftung gef{\"o}rdertes Projekt zum Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern durchgef{\"u}hrt. In dem vorliegenden Abschlußbericht werden die Ziele, die Strategie, die Durchf{\"u}hrung und die Ergebnisse des Projekts beschrieben.}, language = {de} } @misc{Clemens1998, author = {Clemens, Hans-H.}, title = {Systemanalyse und Datenkatalog zum Projekt: Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5603}, number = {TR-97-18}, year = {1998}, abstract = {Von Januar 1995 bis Februar 1997 wurde am ZIB ein von der Robert Bosch Stiftung gef{\"o}rdertes Projekt zum Sammlungsmanagement f{\"u}r kulturgeschichtliche Museen in den neuen Bundesl{\"a}ndern durchgef{\"u}hrt. Die vorliegende Systemanalyse beschreibt exemplarisch die Voraussetzungen und die notwendigen Arbeitsschritte f{\"u}r den Aufbau einer Dokumentation in einem Museum. Ein im Anhang wiedergegebener Datenfeldkatalog hilft beim "`sanften"' {\"U}bergang von einer papiergest{\"u}tzten zu einer computergest{\"u}tzten Dokumentation.}, language = {de} } @misc{WolfBrandtMohammadzadeh1998, author = {Wolf, Thomas and Brandt, Andreas and Mohammadzadeh, Majid}, title = {Computer algebra algorithms and routines for the computation of conservation laws and fixing of gauge in differential expressions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3482}, number = {SC-98-05}, year = {1998}, abstract = {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.}, language = {en} } @misc{HegeStalling1998, author = {Hege, Hans-Christian and Stalling, Detlev}, title = {Fast LIC with Higher Order Filter Kernels}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3439}, number = {SC-97-74}, year = {1998}, abstract = {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.}, language = {en} } @misc{Luegger1998, author = {L{\"u}gger, Joachim}, title = {Wo ist der Opac der virtuellen Bibliothek?- Strukturen des Kooperativen Bibliotheksverbundes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5524}, number = {TR-97-10}, year = {1998}, abstract = {Als neue Herausforderung f{\"u}r die Bibliotheken stellen sich heute die vielf{\"a}ltigen Publikationsm{\"o}glichkeiten, die den Wissenschaften durch das Internet zur Verf{\"u}gung stehen. Die neuen Arten der wissenschaftlichen Information zu erschließen, wird f{\"u}r die Bibliotheken zu den neuen Aufgaben geh{\"o}ren. Der Artikel diskutiert zun{\"a}chst die Frage, inwieweit dabei die traditionell hohen Maßst{\"a}be bei der bibliographischen Beschreibung und sachlichen Erschließung noch aufrechterhalten werden k{\"o}nnen. Der Autor pl{\"a}diert in diesem Zusammenhang f{\"u}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{\"a}ben weiterentwickeln, erm{\"o}glicht. Der zweite Teil der Arbeit stellt eine technische Interpretation des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) vor, den eine Expertengruppe als neue Informationsstruktur f{\"u}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{\"u}nden verzichtet der KOBV auf einen Zentralkatalog. Die in den lokalen Systemen vorliegende Information hingegen wird den Nutzern {\"u}ber eine Suchmaschine erschlossen und zur Verf{\"u}gung gestellt. Dabei wird vorausgesetzt, daß die Zielsysteme {\"u}ber offene Schnittstellen (Z39.50 und WWW) angesprochen werden k{\"o}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{\"u}gung. Mit der Kommunikation {\"u}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{\"o}ffnet der auf dezentralen Strukturen aufbauende Kooperative Bibliotheksverbunds auch die M{\"o}glichkeit, virtuelle Fachverb{\"u}nde zu beispielsweise einer Disziplin zu bilden.}, language = {de} } @misc{KuberekLohrum1998, author = {Kuberek, Monika and Lohrum, Stefan}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg - Schnittstelle Lokalsysteme-Suchmaschine, Spezifikation der Anforderungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5538}, number = {TR-97-11}, year = {1998}, abstract = {Die Kommunikation zwischen der Suchmaschine und den Lokalsystemen findet {\"u}ber eine offene Schnittstelle statt. Als Standardschnittstelle dient Z39.50-1995 (auch als Z39.50, Level 3 bekannt). Grunds{\"a}tzlich k{\"o}nnen auch Lokalsysteme angesprochen werden, die nur {\"u}ber eine WWW-Schnittstelle verf{\"u}gen. Dieses Papier spezifiziert die Anforderungen, die seitens der KOBV-Suchmaschine an ein Lokalsystem gestellt werden.}, language = {de} } @misc{Kuberek1998, author = {Kuberek, Monika}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg - Normdaten im KOBV}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5548}, number = {TR-97-12}, year = {1998}, abstract = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wird sich aktiv am Aufbau der deutschen Normdateien Gemeinsame K{\"o}rperschaftsdatei (GKD), Schlagwortnormdatei (SWD) und Personennamendatei (PND) beteiligen, die in Gemeinschaftsarbeit der deutschen Bibliotheksverb{\"u}nde erstellt werden. Nach der Konzeption liegen die Normdateien auf dem zentralen KOBV-Server auf und stehen {\"u}ber die Suchmaschine allen angeschlossenen Bibliotheken zur Verf{\"u}gung. Lokal befinden sich nur die Normdatens{\"a}tze, die mit Titeln verkn{\"u}pft sind. Das Update der Normdaten geschieht zentral. Es werden L{\"o}sungen aufgezeigt, wie die Normdaten von den KOBV-Bibliotheken mittels offener Schnittstellen (Z39.50) genutzt und erstellt werden k{\"o}nnen und auf welche Weise der KOBV mit den Redaktionen der Normdateien zusammenarbeiten kann. Neben den technischen werden auch die organisatorischen Fragen er{\"o}rtert, die mit dem neuartigen KOBV-Konzept der dezentralen Nutzung der Normdaten in den lokalen Bibliothekssystemen zusammenh{\"a}ngen. Weitere Themen sind die regionale Zusammenarbeit der Bibliotheken und der KOBV-Zentrale mit der Zeitschriftendatenbank (ZDB) sowie die Einbindung zus{\"a}tzlicher Normdaten, wie Universal- bzw. Fachklassifikationen und Thesauri.}, language = {de} } @misc{Willenborg1998, author = {Willenborg, Josef}, title = {Die Suchmaschine des KOBV - Spezifikation der Anforderungen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5552}, number = {TR-97-13}, year = {1998}, abstract = {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 ({\"u}ber Internet und andere Netze) erm{\"o}glicht. Auf die Suchmaschine greifen sowohl Bibliotheksmitarbeiter/innen als auch Endnutzer zu, d.h. sie muß unterschiedlichen Anwenderbed{\"u}rfnissen gerecht werden.}, language = {de} } @misc{LueggerRed1998, author = {L{\"u}gger(Red.), Joachim}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg - Lokale Konzepte und technische Schnittstellen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5566}, number = {TR-97-14}, year = {1998}, abstract = {Dieser Artikel faßt die Ergebnisse einer Arbeitsgruppe bestehend aus Bibliothekaren und Informatikern der Universit{\"a}ts- und Hochschulbibliotheken aus Berlin und Brandenburg zusammen, welche sich im Fr{\"u}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{\"u}gung steht. Zus{\"a}tzlich soll zur Unterst{\"u}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{\"u}cksichtigt.}, language = {de} } @misc{Rusch1998, author = {Rusch, Beate}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg - Strategien zur Nutzung von Fremddaten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5579}, number = {TR-97-15}, year = {1998}, abstract = {Ausgehend von einer Analyse der Fremddatenbedarfs in der Bibliotheksregion Berlin-Brandenburg wird {\"u}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{\"u}r die Region angeboten werden, den Daten, die die Bibliotheken (langfristig) {\"u}ber Z39.50 aus (verbund-) fremden Bibliotheken abrufen, und denjenigen Datenbest{\"a}nden, die ausschließlich zur lokalen Nutzung vorliegen.}, language = {de} } @misc{DeuflhardHuisingaFischeretal.1998, author = {Deuflhard, Peter and Huisinga, Wilhelm and Fischer, Alexander and Sch{\"u}tte, Christof}, title = {Identification of Almost Invariant Aggregates in Reversible Nearly Uncoupled Markov Chains}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3469}, number = {SC-98-03}, year = {1998}, abstract = {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.}, language = {en} } @misc{SchuetteFischerHuisingaetal.1998, author = {Sch{\"u}tte, Christof and Fischer, Alexander and Huisinga, Wilhelm and Deuflhard, Peter}, title = {A Hybrid Monte Carlo Method for Essential Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3474}, number = {SC-98-04}, year = {1998}, abstract = {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.}, language = {en} } @misc{Wolf1998, author = {Wolf, Thomas}, title = {A Study of Genetic Algorithms solving a combinatorial Puzzle}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3445}, number = {SC-98-01}, year = {1998}, abstract = {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.}, language = {en} } @misc{BoeingKoepf1998, author = {B{\"o}ing, Harald and Koepf, Wolfram}, title = {Algorithms for q-hypergeometric Summation in Computer Algebra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3453}, number = {SC-98-02}, year = {1998}, abstract = {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.}, language = {en} } @misc{LangErdmannSeebass1998, author = {Lang, Jens and Erdmann, Bodo and Seebass, Martin}, title = {Impact of Nonlinear Heat Transfer on Temperature Control in Regional Hyperthermia}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3426}, number = {SC-97-73}, year = {1998}, abstract = {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.}, language = {en} } @misc{FoupouagnigniRonveauxHounkonnou1998, author = {Foupouagnigni, Mama and Ronveaux, Andre and Hounkonnou, Mahouton Norbert}, title = {The Fourth-Order Difference Equation Satisfied by the Associated Orthogonal Polynomials of the Delta-Laguerre-HahnClass}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3409}, number = {SC-97-71}, year = {1998}, abstract = {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.}, language = {en} } @misc{FoupouagnigniKoepfRonveaux1998, author = {Foupouagnigni, Mama and Koepf, Wolfram and Ronveaux, Andre}, title = {Fourth Order Difference Equation for the Associated Classical Discrete Orthogonal Polynomials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3419}, number = {SC-97-72}, year = {1998}, abstract = {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.}, language = {en} } @phdthesis{Loebel1997, author = {L{\"o}bel, Andreas}, title = {Optimal Vehicle Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10169}, year = {1997}, abstract = {Die vorliegende Dissertation besch{\"a}ftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im {\"o}ffentlichen Personennahverkehr. Dieses Problem ist f{\"u}r die meisten praxisrelevanten F{\"a}lle schwierig (Ar'P-schwer). In dieser Arbeit pr{\"a}sentieren wir Methoden der ganzzahligen linearen Programmierung zur L{\"o}sung dieses Planungsproblems. "Vern{\"u}nftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrg{\"u}terfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir besch{\"a}ftigen uns mit beiden Ans{\"a}tzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrg{\"u}terfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen f{\"u}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{\"o}glicht, LPs dieser Art mit rund 70 Millionen Variablen zu l{\"o}sen. F{\"u}r den bogenorientierten (Mehrg{\"u}ter)Fluß-Zugang beschreiben wir ausf{\"u}hrlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gel{\"o}st werden. Zus{\"a}tzlich schlagen wir eine Heuristik vor, die schnell gute L{\"o}sungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der L{\"o}sung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrg{\"u}terfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell {\"u}berf{\"u}hrt werden kann. Der zweite Teil dieser Arbeit pr{\"a}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{\"a}ssig und stabil. Die mit diesen Verfahren durchgef{\"u}hrten Testl{\"a}ufe lieferten hervorragende Ergebnisse: Bis auf ein Problem k{\"o}nnen alle Beispiele optimal gel{\"o}st werden. Die L{\"o}sungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenw{\"a}rtig eingesetzten Verfahren verglichen: Wir konnten zus{\"a}tzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 \% aufzeigen. Der m{\"o}gliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und j{\"a}hrlich Einsparungen in H{\"o}he von rund 100 Millionen Mark erzielen zu k{\"o}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{\"u}r Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Dar{\"u}ber hinaus hat auch die Forschungsabteilung der SIEMENS AG in M{\"u}nchen dieses System erworben.}, language = {en} } @misc{NowakGebauer1997, author = {Nowak, Ulrich and Gebauer, Susanna}, title = {A New Test Frame for Ordinary Differential Equation Solvers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3370}, number = {SC-97-68}, year = {1997}, abstract = {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.}, language = {en} } @misc{NowakEhrigOeverdieck1997, author = {Nowak, Ulrich and Ehrig, Rainald and Oeverdieck, Lars}, title = {Parallel Extrapolation Methods and Their Application in Chemical Engineering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3387}, number = {SC-97-69}, year = {1997}, abstract = {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.}, language = {en} } @misc{AscheuerJuengerReinelt1997, author = {Ascheuer, Norbert and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Branch \& Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3391}, number = {SC-97-70}, year = {1997}, abstract = {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.}, language = {en} } @misc{BeckDeuflhardHiptmairetal.1997, author = {Beck, Rudolf and Deuflhard, Peter and Hiptmair, Ralf and Hoppe, Ronald H. W. and Wohlmuth, Barbara}, title = {Adaptive Multilevel Methods for Edge Element Discretizations of Maxwell's Equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3356}, number = {SC-97-66}, year = {1997}, abstract = {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.}, language = {en} } @misc{FischerCordesSchuette1997, author = {Fischer, Alexander and Cordes, Frank and Sch{\"u}tte, Christof}, title = {Hybrid Monte Carlo with Adaptive Temperature in a Mixed-Canonical Ensemble: Efficient Conformational Analysis of RNA}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3364}, number = {SC-97-67}, year = {1997}, abstract = {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.}, language = {en} } @misc{Bornemann1997, author = {Bornemann, Folkmar A.}, title = {Homogenization in Time II: Mechanical Systems Subject to Friction and Gyroscopic Forces}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3348}, number = {SC-97-65}, year = {1997}, abstract = {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.}, language = {en} } @misc{Schmidt1997, author = {Schmidt, Frank}, title = {Computation of Discrete Transparent Boundary Conditions for the 2D Helmholtz Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3330}, number = {SC-97-64}, year = {1997}, abstract = {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.}, language = {en} } @misc{EhrigDeuflhard1997, author = {Ehrig, Rainald and Deuflhard, Peter}, title = {GMERR - an Error Minimizing Variant of GMRES}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3323}, number = {SC-97-63}, year = {1997}, abstract = {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.}, language = {en} } @misc{Wolf1997, author = {Wolf, Thomas}, title = {Structural equations for Killing tensors of arbitrary rank}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3310}, number = {SC-97-62}, year = {1997}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1997, author = {Martin, Alexander and Weismantel, Robert}, title = {The Intersection of Knapsack Polyhedra and Extensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3300}, number = {SC-97-61}, year = {1997}, abstract = {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.}, language = {en} } @misc{ErdmannLangSeebass1997, author = {Erdmann, Bodo and Lang, Jens and Seebass, Martin}, title = {Optimization of Temperature Distributions for Regional Hyperthermia Based on a Nonlinear Heat Transfer Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3283}, number = {SC-97-59}, year = {1997}, abstract = {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 .}, language = {en} } @misc{Schmidt1997, author = {Schmidt, Frank}, title = {Construction of Discrete Transparent Boundary Conditions for Schr{\"o}dinger-Type Equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3292}, number = {SC-97-60}, year = {1997}, abstract = {We present a general technique for constructing nonlocal transparent boundary conditions for time-discretized one-dimensional Schr{\"o}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.}, language = {en} } @misc{Wolf1997, author = {Wolf, Thomas}, title = {Killing Pairs in Flat Space}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3275}, number = {SC-97-58}, year = {1997}, abstract = {In this paper the integrability conditions for Killing pairs in flat spaces are investigated and it is shown that only trivial Killing pairs exist.}, language = {en} } @misc{Friese1997, author = {Friese, Tilmann}, title = {On the Computation of Eigenmodes of Integrated Optical Components}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3268}, number = {SC-97-57}, year = {1997}, abstract = {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.}, language = {en} } @misc{NettesheimReich1997, author = {Nettesheim, Peter and Reich, Sebastian}, title = {Symplectic Multiple-Time-Stepping Integrators for Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3250}, number = {SC-97-56}, year = {1997}, abstract = {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.}, language = {en} } @misc{DeuflhardFrieseSchmidt1997, author = {Deuflhard, Peter and Friese, Tilmann and Schmidt, Frank}, title = {A Nonlinear Multigrid Eigenproblem Solver for the Complex Helmholtz Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3240}, number = {SC-97-55}, year = {1997}, abstract = {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.}, language = {en} } @misc{MuellerDecker1997, author = {M{\"u}ller, Peter and Decker, Ingmar}, title = {The Electronic Visualization Library}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5517}, number = {TR-97-09}, year = {1997}, abstract = {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.}, language = {en} } @misc{BorndoerferWeismantel1997, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Discrete Relaxations of Combinatorial Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3230}, number = {SC-97-54}, year = {1997}, abstract = {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.}, language = {en} } @misc{Reich1997, author = {Reich, Sebastian}, title = {Modified potential energy functions for constrained molecular dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3189}, number = {SC-97-49}, year = {1997}, abstract = {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.}, language = {en} } @misc{AscherReich1997, author = {Ascher, Uri and Reich, Sebastian}, title = {On some difficulties in integrating highly oscillatory Hamiltonian systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3193}, number = {SC-97-50}, year = {1997}, abstract = {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.}, language = {en} } @misc{AscherReich1997, author = {Ascher, Uri and Reich, Sebastian}, title = {The midpoint scheme and variants for Hamiltonian systems: advantages and pitfalls}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3201}, number = {SC-97-51}, year = {1997}, abstract = {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.}, language = {en} } @misc{Reich1997, author = {Reich, Sebastian}, title = {Preservation of Adiabatic Invariants under Symplectic Discretization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3210}, number = {SC-97-52}, year = {1997}, abstract = {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.}, language = {en} } @misc{BarthLeimkuhlerReich1997, author = {Barth, Eric and Leimkuhler, Benedict and Reich, Sebastian}, title = {A Time-Reversible Variable-Stepsize Integrator for Constrained Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3220}, number = {SC-97-53}, year = {1997}, abstract = {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.}, language = {en} } @misc{LangMerz1997, author = {Lang, Jens and Merz, Wilhelm}, title = {Numerical Simulation of Single Species Dopant Diffusion in Silicon under Extrinsic Conditions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3163}, number = {SC-97-47}, year = {1997}, abstract = {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.}, language = {en} } @phdthesis{Bornemann1997, author = {Bornemann, Folkmar A.}, title = {Homogenization in Time of Singularly Perturbed Conservative Mechanical Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3170}, number = {SC-97-48}, year = {1997}, abstract = {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.}, language = {en} } @misc{Wagler1997, author = {Wagler, Annegret}, title = {Critical Edges in Perfect Graphs and Some Polyhedral Consequences}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3153}, number = {SC-97-46}, year = {1997}, abstract = {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\$.\\}, language = {en} } @misc{Kornhuber1997, author = {Kornhuber, Ralf}, title = {Globally Convergent Multigrid Methods for Porous Medium Type Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3142}, number = {SC-97-45}, year = {1997}, abstract = {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.}, language = {en} } @misc{ErdmannLangSeebass1997, author = {Erdmann, Bodo and Lang, Jens and Seebass, Martin}, title = {Adaptive Solutions of Nonlinear Parabolic Equations with Application to Hyperthermia Treatments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3130}, number = {SC-97-44}, year = {1997}, abstract = {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.}, language = {en} } @misc{SchulzBusch1997, author = {Schulz, Sandra and Busch, Hubert}, title = {Schlussbericht des Berliner Regionalen Testbed (BRTB) Projektes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5496}, number = {TR-97-07}, year = {1997}, abstract = {Im M{\"a}rz 1993 wurde das Projekt ,Regionales Testbed - RTB" in den DFN-Mitteilungen bundesweit mit folgenden Zielen ausgeschrieben und festgelegt: Einf{\"u}hrung bzw. Pilotnutzung fortgeschrittener Netztechniken, Entwicklung von Anwendungsumgebungen mit Bedarf f{\"u}r hohe {\"U}bertragungsraten und Einsatz von Anwendungsumgebungen durch nachgewiesene Anwendergruppen. Die Ziele sollten durch die Vernetzung einer beschr{\"a}nkten Anzahl von Institutionen (Universit{\"a}ten, Fachhochschulen und Forschungseinrichtungen) der jeweiligen Region, die sowieso schon einen hohen Kommunikationsbedarf untereinander hatten, erreicht werden. Die Berliner Universit{\"a}ten, das HMI, das ISST und das LIT f{\"u}hrten unter Federf{\"u}hrung des ZIB f{\"u}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{\"u}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{\"u}r ein deutschland-weites Breitband-Wissenschaftsnetz, ist erreicht worden. Wir danken dem DFN-Verein und dem BMBF f{\"u}r die F{\"o}rderung dieses Projektes und allen, die zu seinem Gelingen beigetragen haben.}, language = {de} }