TY - GEN A1 - Baumann, Wolfgang A1 - Hege, Hans-Christian A1 - Schwarz, Uwe A1 - Stüben, Hinnerk T1 - Netzverteilte Visualisierung und Simulation N2 - Dieser Bericht beschreibt die Ergebnisse eines Anwendungsprojektes, das parallel zum Aufbau des Berliner Hochgeschwindigkeitsdatennetzes (Berlin Regional Testbed) am ZIB durchgeführt wurde. Es werden allgemeine Werkzeuge und anwendungsspezifische Arbeitsumgebungen zur netzverteilten Visualisierung und Simulation vorgestellt. Die allgemeinen Werkzeuge unterstützen folgende Aufgaben: Kopplung von Simulationen auf (Hochleistungs-)Rechnern an lokale Grafikarbeitsplätze, objektorientierte und verteilte Visualisierung, Remote-Videoaufzeichnung, Bilddatenkompression und digitaler Filmschnitt. Die spezifischen Arbeitsumgebungen wurden für Aufgaben aus den Bereichen Numerische Mathematik, Astrophysik, Strukturforschung, Chemie, Polymerphysik und Strömungsmechanik entwickelt. T3 - ZIB-Report - TR–96–08 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5379 ER - TY - GEN A1 - Oevermann, Michael A1 - Scharfenberg, Carsten A1 - Klein, Rupert T1 - A sharp interface finite volume method for elliptic equations on Cartesian grids N2 - We present a second order sharp interface finite volume method for the solution of the three-dimensional poisson equation with variable coefficients on Cartesian grids. In particular, we focus on interface problems with discontinuities in the coefficient, the source term, the solution, and the fluxes across the interface. The method uses standard piecewiese trilinear finite elements for normal cells and a double piecewise trilinear ansatz for the solution on cells intersected by the interface resulting always in a compact 27-point stencil. Singularities associated with vanishing partial volumes of intersected grid cells are removed by a two-term asymptotic approach. In contrast to the 2D method presented by two of the authors in [M.~Oevermann, R.~Klein: A Cartesian grid finite volume method for elliptic equations with variable coefficients and embedded interfaces, J.~Comp.~Phys.~219 (2006)] we use a minimization technique to determine the unknown coefficients of the double trilinear ansatz. This simplifies the treatment of the different cut-cell types and avoids additional special operations for degenerated interface topologies. The resulting set of linear equations has been solved with a BiCGSTAB solver preconditioned with an algebraic multigrid. In various testcases -- including large coefficient ratios and non-smooth interfaces -- the method achieves second order of accuracy in the L_inf and L_2 norm. T3 - ZIB-Report - 08-38 KW - elliptische Gleichungen KW - Finite Volumen KW - eingebettete Ränder KW - variable und diskontinuierliche Koeffizienten KW - diskontinuierliche Lösung KW - Elliptic equations KW - finite volume methods KW - embedded interface KW - variable and discontinuous coefficients KW - discontinuous solution Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10900 SN - 1438-0064 ER - TY - GEN A1 - Kube, Susanna A1 - Lasser, Caroline A1 - Weber, Marcus T1 - Monte Carlo sampling of Wigner functions and surface hopping quantum dynamics N2 - Wigner transformation provides a one-to-one correspondence between functions on position space (wave functions) and functions on phase space (Wigner functions). Weighted integrals of Wigner functions yield quadratic quantities of wave functions like position and momentum densities or expectation values. For molecular quantum systems, suitably modified classical transport of Wigner functions provides an asymptotic approximation of the dynamics in the high energy regime. The article addresses the computation of Wigner functions by Monte Carlo quadrature. An ad aption of the Metropolis algorithm for the approximation of signed measures with disconnected support is systematically tested in combination with a surface hopping algorithm for non-adiabatic quantum dynamics. The numerical experiments give expectation values and level populations with an error of two to three percent, which agrees with the theoretically expected accuracy. T3 - ZIB-Report - 07-17 KW - Metropolis Monte Carlo KW - approximation KW - quadrature KW - oscillating functions Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9604 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 07-16 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9599 ER - TY - GEN A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Capacitated network design using general flow-cutset inequalities N2 - This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities. T3 - ZIB-Report - 07-14 KW - general flow-cutset inequalities KW - capacitated network design KW - mixed integer rounding KW - SNDlib Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9576 ER - TY - GEN A1 - Vater, Stefan A1 - Klein, Rupert T1 - Stability of a Cartesian Grid Projection Method for Zero Froude Number Shallow Water Flows N2 - In this paper a Godunov-type projection method for computing approximate solutions of the zero Froude number (incompressible) shallow water equations is presented. It is second-order accurate and locally conserves height (mass) and momentum. To enforce the underlying divergence constraint on the velocity field, the predicted numerical fluxes, computed with a standard second order method for hyperbolic conservation laws, are corrected in two steps. First, a MAC-type projection adjusts the advective velocity divergence. In a second projection step, additional momentum flux corrections are computed to obtain new time level cell-centered velocities, which satisfy another discrete version of the divergence constraint. The scheme features an exact and stable second projection. It is obtained by a Petrov-Galerkin finite element ansatz with piecewise bilinear trial functions for the unknown incompressible height and piecewise constant test functions. The stability of the projection is proved using the theory of generalized mixed finite elements, which goes back to Nicola{\"i}des (1982). In order to do so, the validity of three different inf-sup conditions has to be shown. Since the zero Froude number shallow water equations have the same mathematical structure as the incompressible Euler equations of isentropic gas dynamics, the method can be easily transfered to the computation of incompressible variable density flow problems. T3 - ZIB-Report - 07-13 KW - incompressible flows KW - shallow water equations KW - projection method KW - stability KW - mixed finite elements KW - inf-sup-condition Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9562 ER - TY - GEN A1 - Ruprecht, Daniel A1 - Schädle, Achim A1 - Schmidt, Frank A1 - Zschiedrich, Lin T1 - Transparent boundary conditons for time-dependent problems N2 - A new approach to derive transparent boundary conditions (TBCs) for wave, Schrödinger, heat and drift-diffusion equations is presented. It relies on the pole condition and distinguishes between physical reasonable and unreasonable solutions by the location of the singularities of the spatial Laplace transform of the exterior solution. To obtain a numerical algorithm, a Möbius transform is applied to map the Laplace transform onto the unit disc. In the transformed coordinate the solution is expanded into a power series. Finally, equations for the coefficients of the power series are derived. These are coupled to the equation in the interior, and yield transparent boundary conditions. Numerical results are presented in the last section, showing that the error introduced by the new approximate TBCs decays exponentially in the number of coefficients. T3 - ZIB-Report - 07-12 KW - transparent boundary condition KW - non-reflecting boundary condition KW - pole condition KW - wave equation KW - Schrödinger equation KW - drift diffusion equation Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9558 ER - TY - GEN A1 - Geerdes, Hans-Florian A1 - Eisenblätter, Andreas T1 - Reconciling Theory and Practice: A Revised Pole Equation for W-CDMA Cell Powers N2 - The performance evaluation of W-CDMA networks is intricate as cells are strongly coupled through interference. Pole equations have been developed as a simple tool to analyze cell capacity. Numerous scientific contributions have been made on their basis. In the established forms, the pole equations rely on strong assumptions such as homogeneous traffic, uniform users, and constant downlink orthogonality factor. These assumptions are not met in realistic scenarios. Hence, the pole equations are typically used during initial network dimensioning only. Actual network (fine-) planning requires a more faithful analysis of each individual cell's capacity. Complex analytical analysis or Monte-Carlo simulations are used for this purposes. In this paper, we generalize the pole equations to include inhomogeneous data. We show how the equations can be parametrized in a cell-specific way provided the transmit powers are known. This allows to carry over prior results to realistic settings. This is illustrated with an example: Based on the pole equation, we investigate the accuracy of average snapshot'' approximations for downlink transmit powers used in state-of-the-art network optimization schemes. We confirm that the analytical insights apply to practice-relevant settings on the basis of results from detailed Monte-Carlo simulation on realistic datasets. T3 - ZIB-Report - 07-11 Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9543 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian A1 - Kutschka, Manuel T1 - Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts N2 - Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or $\frac{1}{2}$, such cuts are known as $\{0,\frac{1}{2}\}$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of $\{0,\frac{1}{2}\}$-cuts is NP-hard. In this paper, we study ways to separate $\{0,\frac{1}{2}\}$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated $\{0,\frac{1}{2}\}$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers. T3 - ZIB-Report - 07-10 KW - {0 KW - 1/2}-Chvatal-Gomory cuts KW - separation algorithms KW - integer programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9531 ER - TY - GEN A1 - Deuflhard, Peter A1 - Nowak, Ulrich A1 - Lutz-Westphal, Brigitte T1 - Bessel'scher Irrgarten N2 - Dieser Artikel berichtet über eine erfolgreiche Schüleraktivität, die seit Jahren am Zuse-Institut Berlin (ZIB) bei Besuchen von Schülergruppen erprobt und verfeinert worden ist. Das hier zusammengestellte Material ist gedacht als Basis für eine Unterrichtseinheit in Leistungskursen Mathematik an Gymnasien. Inhaltlich wird von einem zwar für Schüler (wie auch Lehrer) neuen, aber leicht fasslichen Gegenstand ausgegangen: der Drei-Term-Rekursion für Besselfunktionen. Die Struktur wird erklärt und in ein kleines Programm umgesetzt. Dazu teilen sich die Schüler selbstorganisierend in Gruppen ein, die mit unterschiedlichen Taschenrechnern "um die Wette" rechnen. Die Schüler und Schülerinnen erfahren unmittelbar die katastrophale Wirkung von an sich kleinen'' Rundungsfehlern, sie landen -- ebenso wie der Supercomputer des ZIB -- im Bessel'schen Irrgarten''. Die auftretenden Phänomene werden mathematisch elementar erklärt, wobei lediglich auf das Konzept der linearen Unabhängigkeit zurückgegriffen wird. Das dabei gewonnene vertiefte Verständnis fließt ein in die Konstruktion eines klassischen Algorithmus sowie eines wesentlich verbesserten Horner-artigen Algorithmus. T3 - ZIB-Report - 07-09 KW - Rundungsfehler KW - Drei-Term-Rekursionen KW - Bessel-Rekursion Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9525 ER -