TY - GEN A1 - Helmberg, Christoph T1 - Semidefinite Programming N2 - Due to its many applications in control theory, robust optimization, combinatorial optimization and eigenvalue optimization, semidefinite programming had been in wide spread use even before the development of efficient algorithms brought it into the realm of tractability. Today it is one of the basic modeling and optimization tools along with linear and quadratic programming. Our survey is an introduction to semidefinite programming, its duality and complexity theory, its applications and algorithms. T3 - ZIB-Report - SC-99-49 KW - semidefinite programming Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4382 ER - TY - GEN A1 - Stüben, Hinnerk T1 - Decorrelation of the Topological Charge in Tempered Simulations of Full QCD N2 - The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied. As an indicator for decorrelation the topological charge is used. T3 - ZIB-Report - SC-99-47 KW - QCD KW - parallel tempering KW - topological charge Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4369 ER - TY - GEN A1 - Marchand, Hugues A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Cutting Planes in Integer and Mixed Integer Programming N2 - This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored. T3 - ZIB-Report - SC-99-44 KW - Mixed Integer Programming KW - Cutting Planes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4339 ER - TY - GEN A1 - Friese, Tilman A1 - Schmidt, Frank A1 - Yevick, David T1 - Transparent Boundary Conditions for a Wide-Angle Approximation of the One-Way Helmholtz Equation N2 - We present nonlocal discrete transparent boundary conditions for a fourth-order wide-angle approximation of the two-dimensional Helmholtz equation. The boundary conditions are exact in the sense that they supply the same discrete solution on a bounded interior domain as would be obtained by considering the problem on the entire unbounded domain with zero boundary conditions at infinity. The proposed algorithm results in an unconditionally stable propagation method. Numerical examples from optics illustrate the efficiency of our approach. T3 - ZIB-Report - SC-99-45 KW - Helmholtz equation KW - Wide-angle approximation KW - Transparent boundary conditions KW - Finite-element method Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4345 ER - TY - GEN A1 - Schmidt, Frank A1 - Friese, Tilmann A1 - Yevick, David T1 - Transparent Boundary Conditions for Split-Step Pade Approximations of the One-Way Helmholtz Equation N2 - In this paper, we generalize the nonlocal discrete transparent boundary condition introduced by Schmidt and Deuflhard {[}Comp. Math. Appl. 29 (1995) 53-76{]} and Schmidt and Yevick {[}J. Comput. Phys. 134 (1997) 96-107{]} to propagation methods based on arbitrary Pad\'e approximations to the two-dimensional one-way Helmholtz equation. Our approach leads to a recursive formula for the coefficients appearing in the nonlocal condition which then yields an unconditionally stable propagation method. T3 - ZIB-Report - SC-99-46 KW - Helmholtz equation KW - Wide-angle approximation KW - Pad/'e split step approximation KW - Transparent boundary conditions KW - Finite-element method Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4353 ER - TY - GEN A1 - Benger, Werner A1 - Hege, Hans-Christian A1 - Merzky, Andre A1 - Radke, Thomas A1 - Seidel, Edward T1 - Efficient Distributed File I/O for Visualization in Grid Environments N2 - Large scale simulations running in metacomputing environments face the problem of efficient file I/O. For efficiency it is desirable to write data locally, distributed across the computing environment, and then to minimize data transfer, i.e.\ reduce remote file access. Both aspects require I/O approaches which differ from existing paradigms. For the data output of distributed simulations, one wants to use fast local parallel I/O for all participating nodes, producing a single distributed logical file, while keeping changes to the simulation code as small as possible. For reading the data file as in postprocessing and file based visualization, one wants to have efficient partial access to remote and distributed files, using a global naming scheme and efficient data caching, and again keeping the changes to the postprocessing code small. However, all available software solutions require the entire data to be staged locally (involving possible data recombination and conversion), or suffer from the performance problems of remote or distributed file systems. In this paper we show how to interface the HDF5 I/O library via its flexible Virtual File Driver layer to the Globus Data Grid. We show, that combining these two toolkits in a suitable way provides us with a new I/O framework, which allows efficient, secure, distributed and parallel file I/O in a metacomputing environment. T3 - ZIB-Report - SC-99-43 KW - Grid KW - Data Grid KW - Globus KW - HDF5 KW - Cactus KW - CCTK KW - Amira KW - VFD KW - Storage Systems Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4326 ER - TY - GEN A1 - Powell, Gary A1 - Weiser, Martin T1 - Container Adaptors N2 - The C++ standard template library has many useful containers for data. The standard library includes two adpators, queue, and stack. The authors have extended this model along the lines of relational database semantics. Sometimes the analogy is striking, and we will point it out occasionally. An adaptor allows the standard algorithms to be used on a subset or modification of the data without having to copy the data elements into a new container. The authors provide many useful adaptors which can be used together to produce interesting views of data in a container. T3 - ZIB-Report - SC-99-41 KW - C++ KW - STL KW - views Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4308 ER - TY - GEN A1 - Galliat, Tobias T1 - Clustering Data of Different Information Levels N2 - For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis. T3 - ZIB-Report - SC-99-42 KW - cluster analysis KW - Data Mining KW - data preprocessing KW - information theory KW - missing values KW - Self-Organizing Maps KW - similarity measures Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4319 ER - TY - GEN A1 - Beck, Rudolf T1 - Algebraic Multigrid by Component Splitting for Edge Elements on Simplicial Triangulations N2 - Our focus is on Maxwell's equations in the low frequency range; two specific applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the finite element approximation we choose N\'{e}d\'{e}lec's $H(curl)$-conforming edge elements of the lowest order. For the solution of the arising linear equation systems we devise an algebraic multigrid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally, we have to cope with the kernel of the $curl$-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efficacy of the proposed algorithms. T3 - ZIB-Report - SC-99-40 KW - Algebraic multigrid KW - mesh coarsening KW - edge elements KW - N\'{e}d\'{e}lec spaces KW - Maxwell's equations Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4290 ER - TY - GEN A1 - Schmidt-Ehrenberg, Johannes A1 - Hege, Hans-Christian T1 - Visualizing Quantum Mechanical Phenomena N2 - In this paper we discuss several ways to visualize stationary and non-stationary quantum mechanical systems. We demonstrate an approach for the quantitative interpretation of probability density isovalues which yields a reasonable correlation between isosurfaces for different timesteps. As an intuitive quantity for visualizing the momentum of a quantum system we propose the probability flow density which can be treated by vector field visualization techniques. Finally, we discuss the visualization of non-stationary systems by a sequence of single timestep images. T3 - ZIB-Report - SC-99-39 KW - quantum dynamics KW - isosurfaces KW - probability flow KW - animation Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4287 ER - TY - GEN A1 - Galliat, Tobias A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification N2 - One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included. T3 - ZIB-Report - SC-99-38 KW - Self-Organizing Maps KW - cluster analysis Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4279 ER - TY - GEN A1 - Helmberg, Christoph A1 - Kiwiel, K.C. T1 - A Spectral Bundle Method with Bounds N2 - Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. Encouraging preliminary computational results are reported. T3 - ZIB-Report - SC-99-37 KW - Eigenvalue optimization KW - convex optimization Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4256 ER - TY - GEN A1 - Schütte, Christof A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - Transfer Operator Approach to Conformational Dynamics in Biomolecular Systems N2 - The article surveys the development of novel mathematical concepts and algorithmic approaches based thereon in view of their possible applicability to biomolecular design. Both a first deterministic approach, based on the Frobenius-Perron operator corresponding to the flow of the Hamiltonian dynamics, and later stochastic approaches, based on a spatial Markov operator or on Langevin dynamics, can be subsumed under the unified mathematical roof of the transfer operator approach to effective dynamics of molecular systems. The key idea of constructing specific transfer operators especially taylored for the purpose of conformational dynamics appears as the red line throughout the paper. Different steps of the algorithm are exemplified by a trinucleotide molecular system as a small representative of possible RNA drug molecules. T3 - ZIB-Report - SC-99-36 KW - Transfer operator KW - Markov process KW - Markov chain KW - molecular dynamics KW - biomolecular conformations KW - canonical ensemble KW - transition prohability KW - Ha Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4247 ER - TY - GEN A1 - Linke, Matthias A1 - Krebs, Carsten A1 - Schünemann, Marion T1 - Metacomputing zwischen Berlin und Rostock N2 - Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) und das Rechenzentrum der Universität Rostock, beide Einrichtungen betreiben massiv-parallele Rechner vom Typ CRAY T3E, haben sich an Hand einer Anwendung aus dem Bereich der Botanik mit den Möglichkeiten der Verteilung auf zwei Parallelrechner, gekoppelt nur über das Breitband-Wissenschaftsnetz des Deutschen Forschungsnetzes, vertraut gemacht. Das Projekt besteht aus zwei Teilen. Im ersten Teil wird ausführlich das zwischen den Rechnern liegende Netz und die Ergebnisse einer Performanceanalyse dieses Netzes dokumentiert. Der zweite Teil beschreibt die Anwendung "Simulation des Wachstums von Pflanzen"' sowie die Ergebnisse der Verteilung dieser Anwendung auf beide Rechner. \begin{center} \bf{Abstract} \end{center} The "'Konrad-Zuse-Zentrum für Informationstechnik Berlin"' (ZIB) and the Computing Centre of the University of Rostock operate high-performance computers of type CRAY T3E. In this project an application from the area of the botany is distributed on two parallel computers, only coupled through the Broadband Science Network of the German Research Network (DFN). This project consists of two parts. In the first part the network which is situated between the computers and the results of a performance analysis is documented in detail. The second part describes the application "'Simulation of the growth of plants"' as well as the results of the distribution of this application to both computers. T3 - ZIB-Report - SC-99-35 KW - Metacomputing KW - Performanceanalyse KW - verteilte Anwendung KW - Latenzzeiten KW - Bandbreite Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4239 ER - TY - GEN A1 - Deuflhard, Peter T1 - Differential Equations in Technology and Medicine. Computational Concepts, Adaptive Algorithms, and Virtual Labs N2 - This series of lectures has been given to a class of mathematics postdocs at a European summer school on Computational Mathematics Driven by Industrial Applications in Martina Franca, Italy (organized by CIME). It deals with a variety of challenging real life problems selected from clinical cancer therapy, communication technology, polymer production, and pharmaceutical drug design. All of these problems from rather diverse application areas share two common features: (a) they have been modelled by various differential equations -- elliptic, parabolic, or Schrödinger--type partial differential equations, countable ordinary diffential equations, or Hamiltonian systems, (b) their numerical solution has turned out to be real challenge to computational mathematics. T3 - ZIB-Report - SC-99-34 KW - differential equations: KW - ordinary KW - partial KW - countable KW - hamiltonian KW - finite element methods: KW - adaptive KW - multilevel KW - grid generation KW - medical t Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4223 ER - TY - GEN A1 - Zöckler, Malte A1 - Stalling, Detlev A1 - Hege, Hans-Christian T1 - Fast and Intuitive Generation of Geometric Shape Transitions N2 - We describe a novel method for continuously transforming two triangulated models of arbitrary topology into each other. Equal global topology for both objects is assumed, extensions for genus changes during metamorphosis are provided. The proposed method addresses the major challenge in 3D metamorphosis, namely specifying the morphing process intuitively, with minimal user interaction and sufficient detail. Corresponding regions and point features are interactively identified. These regions are parametrized automatically and consistently, providing a basis for smooth interpolation. Utilizing suitable 3D interaction techniques a simple and intuitive control over the whole morphing process is offered. T3 - ZIB-Report - SC-99-33 KW - morphing KW - surface parametrization KW - shape transition Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4219 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Der Schnellste Weg zum Ziel N2 - Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg! T3 - ZIB-Report - SC-99-32 KW - Kürzeste Wege KW - Kombinatorische Optimierung KW - Operations Research Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4209 ER - TY - GEN A1 - Steinbach, Marc T1 - Markowitz Revisited: Single-Period and Multi-Period Mean-Variance Models N2 - Mean-variance portfolio analysis provided the first quantitative treatment of the tradeoff between profit and risk. We investigate in detail the interplay between objective and constraints in a number of single-period variants, including semi-variance models. Particular emphasis is laid on avoiding the penalization of overperformance. The results are then used as building blocks in the development and theoretical analysis of multi-period models based on scenario trees. A key property is the possibility to remove surplus money in future decisions, yielding approximate downside risk minimization. T3 - ZIB-Report - SC-99-30 KW - mean-variance analysis KW - downside risk KW - multi-period model Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4183 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut N2 - Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions. T3 - ZIB-Report - SC-99-31 KW - Asymmetric Travelling Salesman Problem KW - Time Windows KW - Integer Programs KW - Branch&Cut-Algorithm KW - Heuristics KW - Control of Stacker Cranes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4191 ER - TY - GEN A1 - Ilgenfritz, Ernst-Michael A1 - Kerler, Werner A1 - Stüben, Hinnerk T1 - Decorrelation of the topological charge in tempered Hybrid Monte Carlo simulations of QCD N2 - We study the improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering. As an indicator for decorrelation we use the topological charge. T3 - ZIB-Report - SC-99-28 KW - QCD KW - parallel tempering KW - topological charge Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4168 ER - TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Wo bleibt der Aufzug? N2 - Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung. T3 - ZIB-Report - SC-99-29 KW - Aufzugsteuerung KW - Online-Optimierung KW - Echtzeit-Optimierung KW - kompetitive Analyse Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4175 ER - TY - GEN A1 - Schütte, Christof A1 - Huisinga, Wilhelm T1 - On Conformational Dynamics induced by Langevin Processes N2 - The function of many important biomolecules is related to their dynamic properties and their ability to switch between different {\em conformations}, which are understood as {\em almost invariant} or {\em metastable} subsets of the positional state space of the system. Recently, the present authors and their coworkers presented a novel algorithmic scheme for the direct numerical determination of such metastable subsets and the transition probability between them. Although being different in most aspects, this method exploits the same basic idea as {\sc Dellnitz} and {\sc Junge} in their approach to almost invariance in discrete dynamical systems: the almost invariant sets are computed via certain eigenvectors of the Markov operators associated with the dynamical behavior. In the present article we analyze the application of this approach to (high--friction) Langevin models describing the dynamical behavior of molecular systems coupled to a heat bath. We will see that this can be related to theoretical results for (symmetric) semigroups of Markov operators going back to {\sc Davies}. We concentrate on a comparison of our approach in respect to random perturbations of dynamical systems. T3 - ZIB-Report - SC-99-25 KW - Smoluchowski equation KW - Fokker--Planck equation KW - semigroup of Markov operators KW - canonical ensemble KW - small noise KW - first exit time KW - half time perio Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4130 ER -