Bibliothek

Beschreibung: Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only while there are examples with clique number $〉4$ having non-rank facets.

Beschreibung: The bio-heat transfer equation is a macroscopic model for describing the heat transfer in microvascular tissue. In [{\sl Deuflhard, Hochmuth 2002}] the authors applied homogenization techniques to derive the bio-heat transfer equation as asymptotic result of boundary value problems which provide a microscopic description for microvascular tissue. Here those results are generalized to a geometrical setting where the regions of blood are allowed to be connected. Moreover, asymptotic corrector results are derived.

Beschreibung: Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.

Beschreibung: In this paper, first solutions of the dust moment equations developed in [{\sl Woitke & Helling 2002}] for the description of dust formation and precipitation in brown dwarf and giant gas planet atmospheres are presented. We consider the special case of a static brown dwarf atmosphere, where dust particles continuously nucleate from the gas phase, grow by the accretion of molecules, settle gravitationally and re-evaporate thermally. Applying a kinetic description of the relevant microphysical and chemical processes for TiO$_2$-grains, the model makes predictions about the large-scale stratification of dust in the atmosphere, the depletion of molecules from the gas phase, the supersaturation of the gas in the atmosphere as well as the mean size and the mass fraction of dust grains as function of depth. Our results suggest that the nucleation occu in the upper atmosphere where the gas is cool, strongly depleted, but nevertheless highly supersaturated ($S\!\gg\!1$). These particles settle gravitationally and populate the warmer layers below, where the in-situ formation (nucleation) is ineffective or even not possible. During their descent, the particles grow up to radii $\approx\!0.3\,\mu{\rm m}\,...\,150\,\mu{\rm m}$, depending gas around the cloud base. The particles finally sink into layers which are sufficiently hot to cause their thermal evaporation. Hence, an effective transport mechanism for condensable elements exi considered solid/liquid material. In the stationary case studied here, this downward directed element transport by precipitating dust grains is balanced by an upward directed flux of condensable elements from the deep interior of the star via convective mixing (no dust without mixing). We find a self-regulation mechanism which leads to an approximate phase equilibrium ($S\!\approx\!1$) around the cloud base. The mass fraction of dust present in the atmosphere results be to approximately given by the mass fraction of condensable elements in the gas being mixed up.

Beschreibung: Analysis of phenomena that simultaneously occur on quite different spatial and temporal scales require adaptive, hierarchical schemes to reduce computational and storage demands. For data represented as grid functions, the key are adaptive, hierarchical, time-dependent grids that resolve spatio-temporal details without too much redundancy. Here, so-called AMR grids gain increasing popularity. For visualization and feature identification/tracking, the underlying continuous function has to be faithfully reconstructed by spatial and temporal interpolation. Well designed interpolation methods yield better results and help to reduce the amount of data to be stored. We address the problem of temporal interpolation of AMR grid data, e.g.\ for creation of smooth animations or feature tracking. Intermediate grid hierarchies are generated by merging the cells on all refinement levels that are present in the key frames considered. Utilizing a clustering algorithm a structure of nested grids is induced on the resulting collection of cells. The grid functions are mapped to the intermediate hierarchy, thus allowing application of appropriate interpolation techniques.

Beschreibung: An improved general-purpose technique for the visualization of symmetric positive definite tensor fields of rank two is described. It is based on a splatting technique that is built from tiny transparent glyph primitives which are capable to incorporate the full directional information content of a tensor. The result is an information-rich image that allows to read off the preferred directions in a tensor field at each point of a three-dimensional volume or two-dimensional surface. It is useful for analyzing slices or volumes of a three-dimensional tensor field and can be overlayed with standard volume rendering or color mapping. The application of the rendering technique is demonstrated on general relativistic data and the diffusion tensor field of a human brain.

Beschreibung: Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Grötschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number $\geq 4$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of $\omega$ including all odd values at least 5, that there are only finitely many webs with clique number $\omega$ whose stable set polytopes admit rank facets only.

Beschreibung: We present an algorithm that constructs parametrizations of boundary and interface surfaces automatically. Starting with high-resolution triangulated surfaces describing the computational domains, we iteratively simplify the surfaces yielding a coarse approximation of the boundaries with the same topological type. While simplifying we construct a function that is defined on the coarse surface and whose image is the original surface. This function allows access to the correct shape and surface normals of the original surface as well as to any kind of data defined on it. Such information can be used by geometric multigrid solvers doing adaptive mesh refinement. Our algorithm runs stable on all types of input surfaces, including those that describe domains consisting of several materials. We have used our method with success in different fields and we discuss examples from structural mechanics and biomechanics.

Beschreibung: This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.

Beschreibung: We construct non-constructible simplicial $d$-spheres with $d+10$ vertices and non-constructible, non-realizable simplicial $d$-balls with $d+9$ vertices for $d\geq 3$.

Beschreibung: We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported.

Beschreibung: We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results.

Beschreibung: In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case.

Beschreibung: The paper presents a new affine invariant theory on asymptotic mesh independence of Newton's method in nonlinear PDEs. Compared to earlier attempts, the new approach is both much simpler and more natural from the algorithmic point of view. The theory is exemplified at collocation methods for ODE boundary value problems and at finite element methods for elliptic PDE problems.

Beschreibung: In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by [{\sl Spielman and Teng} STOC 2001] to explain the behaviour of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, where the initial processing times are smoothened by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O(max((2^k/\sigma)^3, (2^k/\sigma)^2 2^K-k))$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^K-k)$ if $\sigma = \Theta(2^k)$. %The analysis holds for an oblivious as well as for a stronger adaptive %adversary. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, including the additive symmetric smoothening model used by [{\sl Spielman and Teng}], we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.

Beschreibung: For the general G/G/1 processor sharing (PS) system a sample path result for the sojourn times in a busy period is proved, which yields a relation between the sojourn times under PS and FCFS discipline. In particular, the result provides a formula for the mean sojourn time in G/D/1-PS in terms of the mean sojourn time in the corresponding G/D/1-FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of the formula provide the basis for a two-moment approximation of the mean sojourn time in G/GI/1-PS in terms of a related G/D/1-FCFS.

Beschreibung: The paper surveys recent progress in the mathematical modelling and simulation of essential molecular dynamics. Particular emphasis is put on computational drug design wherein time scales of $msec$ up to $min$ play the dominant role. Classical long-term molecular dynamics computations, however, would run into ill-conditioned initial value problems already after time spans of only $psec=10^{-12} sec$. Therefore, in order to obtain results for times of pharmaceutical interest, a combined deterministic-stochastic model is needed. The concept advocated in this paper is the direct identification of metastable conformations together with their life times and their transition patterns. It can be interpreted as a {\em transfer operator} approach corresponding to some underlying hybrid Monte Carlo process, wherein short-term trajectories enter. Once this operator has been discretized, which is a hard problem of its own, a stochastic matrix arises. This matrix is then treated by {\em Perron cluster analysis}, a recently developed cluster analysis method involving the numerical solution of an eigenproblem for a Perron cluster of eigenvalues. In order to avoid the 'curse of dimension', the construction of appropriate boxes for the spatial discretization of the Markov operator requires careful consideration. As a biomolecular example we present a rather recent SARS protease inhibitor.

Beschreibung: The operative planning problem in natural gas distribution networks is addressed. An optimization model focusing on the governing PDE and other nonlinear aspects is presented together with a suitable discretization for transient optimization in large networks by SQP methods. Computational results for a range of related dynamic test problems demonstrate the viability of the approach.

Beschreibung: This article presents a new computational approach to the three-dimensional (3D) modeling of ribonucleic acid (RNA) sequences with unknown spatial structure. The main concept is a mapping of the query sequence onto the 3D structures of a suitable template RNA molecule. This technique called \textit{threading} has originally been developed for the modeling of protein 3D structures. The application to RNA systems bridges the information gap between the growing mass of RNA sequence data and the relatively limited number of available 3D structures. The new RNA threading method is demonstrated on a tRNA model system because sufficient representative 3D structures have experimentally been elucidated and deposited in the public databases. Nevertheless, the method is in principle transferable on all other RNA species. Algorithms are developed that decompose these template structures into their secondary structure elements and gather this information in a specific template database. The best template is chosen with public alignment and secondary structure prediction tools which are integrated in the RNA modeling module. The structural information gathered from the template and the best alignment is combined to establish a comprehensive 3D model of the query sequence. A range of complete tRNA structures has successfully been modeled with the RNA threading method. The prototype module visualizes the models and provides convenient access to the proposed 3D structures. Therefore, the method could give new insight into a variety of RNA systems which in the recent years have become increasingly important as potential new pharmaceutical agents.

Beschreibung: Collection of abstracts of the Korean-German Bilateral Symposium on Scientific Computing, Berlin January 15/16, 2004

Beschreibung: Beim Entwurf und Ausbau von Informations- und Kommunikationsnetzwerken m{ü}ssen zahlreiche interdependente Entscheidungen getroffen und gleichzeitig mannigfaltige Bedingungen ber{ü}cksichtigt werden. Die verf{ü}gbaren technischen und organisatorischen Alternativm{ö}glichkeiten sind normalerweise so vielf{ä}ltig und komplex, dass eine manuelle Planung praktisch nicht m{ö}glich ist. In diesem Artikel wird das Potential und die Methodik der mathematischen Optimierung bei der kostenoptimalen Planung von Kommunikationsnetzen vorgestellt. Als Ausgangspunkt wird exemplarisch eine typische praktische Aufgabe, die Struktur- und Konfigurationsplanung mehrstufiger Telekommunikationsnetzwerke, dargestellt. Anschließend werden kurz die wesentlichen Modellierungstechniken und Verfahrensans{ä}tze der mathematischen Optimierung skizziert. Abschließend gehen wir auf die Planung einer ad{ä}quaten Informations- und Kommunikations- Infrastruktur f{ü}r ein dezentrales Energieversorgungsnetz ein.

Beschreibung: Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.

Beschreibung: The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.

Beschreibung: Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\% on the average.

Beschreibung: Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice.

Beschreibung: A recently developed algorithm allows Rigid Body Docking of ligands to proteins, regardless of the accessibility and location of the binding site. The Docking procedure is divided into three subsequent optimization phases, two of which utilize rigid body dynamics. The last one is applied with the ligand already positioned inside the binding pocket and accounts for full flexibility. Initially, a combination of geometrical and force-field based methods is used as a Coarse Docking strategy, considering only Lennard-Jones interactions between the target and pharmaceutically relevant atoms or functional groups. The protein is subjected to a Hot Spot Analysis, which reveals points of high affinity in the protein environment towards these groups. The hot spots are distributed into different subsets according to their group affiliation. The ligand is described as a complementary point set, consisting of the same subsets. Both sets are matched in $\mathrm{I\!R}^{3}$, by superimposing members of the same subsets. In the first instance, steric inhibition is nearly neglected, preventing the system's trajectory from trapping in local minima and thus from finding false positive solutions. Hence the exact location of the binding site can be determined fast and reliably without any additional information. Subsequently, errors resulting from approximations are minimized via finetuning, this time considering both Lennard-Jones and Coulomb forces. Finally, the potential energy of the whole complex is minimized. In a first evaluation, results are rated by a reduced scoring function considering only noncovalent interaction energies. Exemplary Screening results will be given for specific ligands.

Beschreibung: We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved.

Beschreibung: Dieser Bericht beschreibt die Erfahrungen und Schlussfolgerungen,die im Rahmen der VDS-Vorstudie bei der Speicherung der vom Friedrich-Althoff-Konsortium lizenzierten Zeitschriften des Kluwer-Verlages gewonnen wurden.

Beschreibung: Der KOBV setzt für die endnutzerbasierte Online-Fernleihe den Sisis ZFL-Server (Zentraler Fernleih-Server) ein. Mit dem Einsatz des ZFL-Servers können in den Bibliotheken echte Rationalisierungseffekte erzielt werden: Der Server ist in der Lage, Fernleih-Bestellungen an lokale Systeme zu übergeben, so dass sie im lokalen System automatisch - ohne Eingreifen von Bibliotheksmitarbeitern - weiterverarbeitet werden können. Im KOBV können derzeit Sisis- und Aleph-Lokalsysteme diese Schnittstelle voll bedienen. Andere Bibliothekssysteme im KOBV, die diese Schnittstelle nicht bedienen können, werden mittels eines E-Mail-Verfahrens in die Online-Fernleihe integriert. Die vorliegende Kurzbeschreibung der Online-Fernleihe im KOBV soll - im Gegensatz zur Spezifikation, die möglichst vollständig sein sollte - einen leicht verständlichen Einblick in die Abläufe der Online-Fernleihe vermitteln. Nach einem Überblick über zu erwartende Rationalisierungseffekte ist der Ablauf einer Online-Fernleih-Bestellung - veranschaulicht durch eine Graphik mit dem technischen Aufbau im KOBV - kurz dargestellt. \vspace{6mm} {\it Hinweis:} Die von einer Arbeitsgruppe des KOBV erstellte Spezifikation zur Online-Fernleihe ist als ZIB Report 02-30 auf dem Preprint-Server des ZIB veröffentlicht. Siehe: Monika Kuberek (Red.) {\begin{rawhtml} 〈a href="http://www.zib.de/Publications/Reports/ZR-02-30.pdf"〉 〈i〉 Spezifikation für eine Verbund-Fernleih-Software im KOBV〈/i〉 〈/a〉 \end{rawhtml}}

Beschreibung: The problem of clustering data can often be transformed into the problem of finding a hidden block diagonal structure in a stochastic matrix. Deuflhard et al. have proposed an algorithm that state s the number $k$ of clusters and uses the sign structure of $k$ eigenvectors of the stochastic matrix to solve the cluster problem. Recently Weber and Galliat discovered that this system of eigenvectors can easily be transformed into a system of $k$ membership functions or soft characteristic functions describing the clusters. In this article we explain the corresponding cluster algorithm and point out the underlying theory. By means of numerical examples we explain how the grade of membership can be interpreted.

Beschreibung: Mit der Entwicklung des KOBV-Informationsportals soll den Benutzern in der Region Berlin-Brandenburg ein verbesserter Zugang zu Informationsressourcen geboten werden. Einen wesentlichen Anteil diese Auf der Grundlage der Analyse der Rahmenbedingungen werden Anforderungen an die Zugriffskontrolle im KOBV definiert und Lösungsmöglichkeiten auf der Ebene allgemeiner Modelle diskutiert.

Beschreibung: The KOBV Informationsportal aims to be a universal gateway to the sources of information hosted by the partner libraries from the Berlin-Brandenburg area. Due to the large number of these sources, an intuitive navigation is an essential component of the portal. The navigation-component should preserve the partner libraries? independence and overcome their administrative and technical differences. This paper proposes a collection-level navigation with four dimensions: the sources? subject areas (e.g. the first two levels of DDC), the sources? type (e.g. e-journals, databases, OPACs, etc.), the sources? location (e.g. Berlin, Brandenburg) / the library that hosts that source and the sources? accessing state (e.g. free, restricted, etc.).

Beschreibung: Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.

Beschreibung: The NETLIB has now served for 18 years as a repository of LP problem instances. From the beginning to the present day there was some uncertainness about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the \emph{exact} optimal objective values for all NETLIB problems.

Beschreibung: Based on the knowledge gained from direct numerical simulations which are only possible in the microscale regime, a concept of driven turbulence is presented which allows to enter the mesoscopic scale regime. Here, dust formation under stochastic hydro- and thermodynamic conditions is studied: constructively superimposed stochastic waves initiate dust formation by the creation of singular nucleation events. It, hence, results a varying mean grain size and dust density in space and time. The newly formed dust changes the thermodynamic behavior from almost isotherm to adiabatic and chemically depletes the gas phase.

Beschreibung: Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuführen. Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der mathematischen Optimierung für die Praxis.

Beschreibung: Dust formation {in brown dwarf atmospheres} is studied by utilizing a model for driven turbulence in the mesoscopic scale regime. We apply a pseudo-spectral method where waves are created and superimposed {within} a {limited} wavenumber interval. The turbulent kinetic energy distribution follows the Kolmogoroff spectrum which is assumed to be the most likely value. Such superimposed, stochastic waves may occur in a convectively active environment. They cause nucleation fronts and nucleation events and thereby initiate the dust formation process which { continues until} all condensible material is consumed. Small disturbances {are found to} have a large impact on the dust forming system. An initially dust-hostile region, which may originally be optically thin, becomes optically thick in a patchy way showing considerable variations in the dust properties during the formation process. The dust appears in lanes and curls as a result of the interaction with waves, i.e. turbulence, which form larger and larger structures with time. Aiming on a physical understanding of the variability of brown dwarfs, related to structure formation in substellar atmospheres, we work out first necessary criteria for small-scale closure models to be applied in macroscopic simulations of dust forming astrophysical systems.

Beschreibung: Substellar atmospheres are observed to be irregularly variable for which the formation of dust clouds is the most promising candidate explanation. The atmospheric gas is convectively unstable and, last but not least, colliding convective cells are seen as cause for a turbulent fluid field. Since dust formation depends on the local properties of the fluid, turbulence influences the dust formation process and may even allow the dust formation in an initially dust-hostile gas. A regime-wise investigation of dust forming substellar atmospheric situations reveals that the largest scales are determined by the interplay between gravitational settling and convective replenishment which results in a dust-stratified atmosphere. The regime of small scales is determined by the interaction of turbulent fluctuations. Resulting lane-like and curled dust distributions combine to larger and larger structures. We compile necessary criteria for a subgrid model in the frame of large scale simulations as result of our study on small scale turbulence in dust forming gases.

Beschreibung: The solution of scattering problems described by the Helmholtz equation on unbounded domains is of importance for a wide variety of applications, for example in electromagnetics and acoustics. An implementation of a solver for scattering problems based on the programming language Matlab is introduced. The solver relies on the finite-element-method and on the perfectly-matched-layer-method, which allows for the simulation of scattering problems on complex geometries surrounded by inhomogeneous exterior domains. This report gives a number of detailed examples and can be understood as a user manual to the freely accessible code of the solver HelmPole.

Beschreibung: \noindent The size of data sets produced on remote supercomputer facilities frequently exceeds the processing capabilities of local visualization workstations. This phenomenon increasingly limits scientists when analyzing results of large-scale scientific simulations. That problem gets even more prominent in scientific collaborations, spanning large virtual organizations, working on common shared sets of data distributed in Grid environments. In the visualization community, this problem is addressed by distributing the visualization pipeline. In particular, early stages of the pipeline are executed on resources closer to the initial (remote) locations of the data sets. \noindent This paper presents an efficient technique for placing the first two stages of the visualization pipeline (data access and data filter) onto remote resources. This is realized by exploiting the ``extended retrieve'' feature of GridFTP for flexible, high performance access to very large HDF5 files. We reduce the number of network transactions for filtering operations by utilizing a server side data processing plugin, and hence reduce latency overhead compared to GridFTP partial file access. The paper further describes the application of hierarchical rendering techniques on remote uniform data sets, which make use of the remote data filtering stage.

Beschreibung: Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.

Beschreibung: We call an edge $e$ of a perfect graph $G$ critical if $G-e$ is imperfect and call $e$ anticritical if $G+e$ is imperfect. The present paper surveys several questions in this context. We ask in which perfect graphs critical and anticritical edges occur and how to detect such edges. The main result by [{\sl Wagler, PhD thesis 2000}] shows that a graph does not admit any critical edge if and only if it is Meyniel. The goal is to order the edges resp.~non-edges of certain perfect graphs s.t. deleting resp.~adding all edges in this order yields a sequence of perfect graphs only. Results of [{\sl Hayward 1985}] and [{\sl Spinrad & Sritharan 1995}] show the existence of such edge orders for weakly triangulated graphs; the line-perfect graphs are precisely these graphs where all edge orders are perfect [{\sl Wagler 2001}]. Such edge orders cannot exist for every subclass of perfect graphs that contains critically resp.~anticritically perfect graphs where deleting resp.~adding an arbitrary edge yields an imperfect graph. We present several examples and properties of such graphs, discuss constructions and characterizations from [{\sl Wagler 1999, Wagler PhD thesis 2000}]. An application of the concept of critically and anticritically perfect graphs is a result due to [{\sl Hougardy & Wagler 2002}] showing that perfectness is an elusive graph property.

Beschreibung: Hasenbusch has proposed splitting the pseudo-fermionic action into two parts, in order to speed-up Hybrid Monte Carlo simulations of QCD. We have tested a different splitting, also using clover-improved Wilson fermions. An additional speed-up between 5 and 20\% over the original proposal was achieved in production runs.

Beschreibung: A set of vertices $S\subseteq V$ is called a safe separator for treewidth, if $S$ is a separator of $G$, and the treewidth of $G$ equals the maximum of the treewidth over all connected components $W$ of $G-S$ of the graph, obtained by making $S$ a clique in the subgraph of $G$, induced by $W\cup S$. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every minimal separator of size one or two is safe, every minimal separator of size three that does not split off a component with only one vertex is safe, and every minimal separator that is an almost clique is safe; an almost clique is a set of vertices $W$ such that there is a $v\in W$ with $W-\{v\}$ a clique. We report on experiments that show significant reductions of instance sizes for graphs from proba! bilistic networks and frequency assignment.

Beschreibung: A primal-dual interior point method for optimal control problems is considered. The algorithm is directly applied to the infinite dimensional problem. Existence and convergence of the central path are analyzed, and linear convergence of a short step pathfollowing method is established.

Beschreibung: We explicitly construct small triangulations for a number of well-known $3$-dimensional manifolds and give a brief outline of some aspects of the underlying theory of $3$-manifolds and its historical development.

Beschreibung: Peer-to-Peer (P2P) Systeme werden u.a. zur Verwaltung von großen Datenmengen benutzt, die auf verschiedene Rechner verteilt sind. Benutzern soll damit der Zugriff auf Daten innerhalb des Systems leicht ermöglicht werden. Damit in P2P Systemen die Daten effizient verteilt und gesucht werden können, existieren Distributed Hash Tables. Distributed Hash Tables (DHT) sind eine Methode, um globale Informationen persistent speichern zu können. Der Wertebereich der Hashfunktion, welche die zu veröffentlichenden Einträge auf Werte abbildet, wird in Abschnitte aufgeteilt, die einzelnen Knoten zugeteilt werden. Die meisten DHTs haben aber ein Problem bei der Verteilung der Last. Die verschiedenen DHT Systeme beruhen meist auf einem identischen Ansatz der Lastverteilung. Die Last wird nur mit Hilfe einer Hashfunktion verteilt. Es wird davon ausgegangen, dass diese Funktion die Last gleichmäßig verteilt. Im Rahmen dieser Arbeit wurde ein Verfahren zur Last Verteilung entwickelt, simuliert und implementiert. Bei dem Verfahren wird die Last wie bei der Verteilung von Wärme an die Umgebung abgegeben. Es wird mit existierenden Lastbalancierungsalgorithmen verglichen. Mit diesem neuen Verfahren ist es möglich, Last in DHTs besser zu verteilen ohne große Änderungen an den DHTs vorzunehmen. Es wird gezeigt, wie mit dem Verfahren zusätzlich die Fehlertoleranz des P2P Systems erhöht werden kann.

Beschreibung: One of the many uses of Peer-to-Peer (P2P) systems is the administration of large data sets that are distributed across different computers, with the goal of facilitating user access to files within the system. Distributed Hash Tables (DHT) are designed to enable the efficient distribution and search of files, by allowing global information to be persistently stored. The range of values of the hash function (the possible entries in the published hash table) are assigned to individual nodes. Most DHTs, however, have a problem with load distribution. The various DHT systems usually operate by distributing load equally among nodes. Thus the load is distributed using the help of the hash function. One assumes this function distributes the load evenly. In the context of this work a method of distributing load has been developed, simulated and implemented. With this method load is transferred in a fashion analogous to the dissipation of heat into the environment. Comparisons with existing algorithms for load balancing are drawn. With the new procedure it is possible to better distribute load in DHTs without requiring major changes to the DHTs themselves. It is shown that with the procedure the fault tolerance of P2P systems may also be increased.

Beschreibung: The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.

Beschreibung: In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs.

Beschreibung: The correlation of the inner architecture of bone and its functional loading was already stated by Wolff in 1892. Our objective is to demonstrate this interdependence in the case of the human mandible. For this purpose, stress/strain profiles occuring at a human lateral bite were simulated. Additionally, by a combination of computer graphics modules, a three--dimensional volumetric visualization of bone mineral density could be given. Qualitative correspondences between the density profile of the jaw and the simulated stress/strain profiles could be pointed out. In the long run, this might enable the use of the simulation for diagnosis and prognosis. The solution of the underlying partial differential equations describing linear elastic material behaviour was provided by an adaptive finite element method. Estimates of the discretization errors, local grid refinement, and multilevel techniques guaranteed the reliability and efficiency of the method.

Beschreibung: UMTS is a 3rd generation mobile telecommunication system which enables multi-service and multi-bit rate communication going beyond the possibilities of previous systems. The simulator MoDySim models UMTS in great detail. Characteristics of UMTS such as soft hand-over and the interdependency of load and capacity among neighbouring cells are challenges for the parallelisation of such a system. In this paper we explain how the software was parallelised and present performance results of a UMTS simulation for the city of Berlin.

Beschreibung: We report on a numerical reinvestigation of the Aoki phase in lattice QCD with two flavors of Wilson fermions where the parity-flavor symmetry is spontaneously broken. For this purpose the Hybrid Monte Carlo algorithm was used and an explicit symmetry-breaking source term $h\bar{\psi} i \gamma_{5} \tau^{3}\psi$ was added to the Wilson fermion action. The order parameter $\langle\bar{\psi}i\gamma_{5}\tau^{3}\psi\rangle$ was studied at several values of $(\beta,\kappa,h)$ on lattices of sizes $4^4$ to $12^4$. Our largest lattices can be considered as infintely large allowing to extrapolate to $h=0$. The existence of a parity-flavor-breaking phase can be confirmed at $\beta=4.0$ and $\beta=4.3$ while we find no sign of parity-flavor-breaking at $\beta=4.6$ and $\beta=5.0$.

Beschreibung: In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs.

Beschreibung: The Web of the future will provide a huge amount of information. We need better ways for dealing with and managing the information. A qualified semantic annotation of the information plays a key role for the Web of the future. This article gives an overview about the efforts of the mathematical community to build up a distributed and open information and communication system for mathematics: the Math-Net. The Math-Net Initiative has developed metadata schemas for some classes of Web resources which are relevant in mathematics. Math-Net Services process this information and enable the user to efficiently search and access the information.

Beschreibung: In this paper we propose a new finite element realization of the Perfectly Matched Layer method (PML-method). Our approach allows to deal with arbitrary shaped polygonal domains and with certain types of inhomogeneous exterior domains. Among the covered inhomogeneities are open waveguide structures playing an essential role in integrated optics. We give a detailed insight to implementation aspects. Numerical examples show exponential convergence behavior to the exact solution with the thickness of the PML sponge layer.

Beschreibung: \def\Bbb{\mathbb} For Gorenstein quotient spaces $\Bbb{C}^d/G$, a direct generalization of the classical McKay correspondence in dimensions $d\geq 4$ would primarily demand the existence of projective, crepant desingularizations. Since this turned out to be not always possible, Reid asked about special classes of such quotient spaces which would satisfy the above property. We prove that the underlying spaces of all Gorenstein abelian quotient singularities, which are embeddable as complete intersections of hypersurfaces in an affine space, have torus-equivariant projective crepant resolutions in all dimensions. We use techniques from toric and discrete geometry.

Beschreibung: We investigate the potential and limits of interior point based cutting plane algorithms for semidefinite relaxations on basis of implementations for max-cut and quadratic 0-1 knapsack problems. Since the latter has not been described before we present the algorithm in detail and include numerical results.

Beschreibung: \def\KukaRob {{\sf KUKA IR\,761}} {\small Industrial robots have greatly enhanced the performance of automated manufacturing processes during the last decades. International competition, however, creates an increasing demand to further improve both the accuracy of off-line programming and the resulting cycle times on production lines. To meet these objectives, validated dynamic robot models are required. We describe in detail the development of a generic dynamic model, specialize it to an actual industrial robot \KukaRob, and discuss the problem of dynamic calibration. Efficient and robust trajectory optimization algorithms are then presented which, when integrated into a CAD system, are suitable for routine application in an industrial environment. Our computational results for the \KukaRob\ robot performing a real life transport maneuver show that considerable gains in productivity can be achieved by minimizing the cycle time.}

Beschreibung: Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.

Beschreibung: We present a new technique for generating surface meshes from a uniform set of discrete samples. Our method extends the well-known marching cubes algorithm used for computing polygonal isosurfaces. While in marching cubes each vertex of a cubic grid cell is binary classified as lying above or below an isosurface, in our approach an arbitrary number of vertex classes can be specified. Consequently the resulting surfaces consist of patches separating volumes of two different classes each. Similar to the marching cubes algorithm all grid cells are traversed and classified according to the number of different vertex classes involved and their arrangement. The solution for each configuration is computed based on a model that assigns probabilities to the vertices and interpolates them. We introduce an automatic method to find a triangulation which approximates the boundary surfaces - implicitly given by our model - in a topological correct way. Look-up tables guarantee a high performance of the algorithm. In medical applications our method can be used to extract surfaces from a 3D segmentation of tomographic images into multiple tissue types. The resulting surfaces are well suited for subsequent volumetric mesh generation, which is needed for simulation as well as visualization tasks. The proposed algorithm provides a robust and unique solution, avoiding ambiguities occuring in other methods. The method is of great significance in modeling and animation too, where it can be used for polygonalization of non-manifold implicit surfaces.

Beschreibung: {\small Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computes recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions. In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation. In this article we extend these results be presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible. The main technique is again to use explicit formulas for structural identities of the given polynomial systems.}

Beschreibung: \noindent In molecular dynamics applications there is a growing interest in so-called {\em mixed quantum-classical} models. These models describe most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of quantum mechanics. A particularly extensively used model, the QCMD model, consists of a {\em singularly perturbed}\/ Schrödinger equation nonlinearly coupled to a classical Newtonian equation of motion. This paper studies the singular limit of the QCMD model for finite dimensional Hilbert spaces. The main result states that this limit is given by the time-dependent Born-Oppenheimer model of quantum theory---provided the Hamiltonian under consideration has a smooth spectral decomposition. This result is strongly related to the {\em quantum adiabatic theorem}. The proof uses the method of {\em weak convergence} by directly discussing the density matrix instead of the wave functions. This technique avoids the discussion of highly oscillatory phases. On the other hand, the limit of the QCMD model is of a different nature if the spectral decomposition of the Hamiltonian happens not to be smooth. We will present a generic example for which the limit set is not a unique trajectory of a limit dynamical system but rather a {\em funnel} consisting of infinitely many trajectories.

Beschreibung: 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.

Beschreibung: Increasing demands on industrial robot operation call for optimal motion planning based on dynamic models. The resulting mathematical problems can be handled efficiently by sparse direct boundary value problem methods. Within this framework we propose a new solution technique that is closely related to the conventional kinematic approach: it eliminates the need for numerical integration of differential equations. First optimization results on a real life transport maneuver demonstrate that the technique may save over 50\,\%\ computation time.

Beschreibung: A mixed hypergraph ${\cal H}=(X,{\cal A},{\cal E})$ consists of the vertex set $X$ and two families of subsets: the family of edges ${\cal E}$ and the family of co-edges ${\cal A}$. In a coloring every edge $E \in {\cal E}$ has at least two vertices of different colors, while every co-edge $A \in {\cal A}$ has at least two vertices of the same color. The smallest (largest) number of colors for which there exists a coloring of a mixed hypergraph $\cal H$ using all the colors is called the lower (upper) chromatic number and is denoted $\chi ({\cal H})$ $(\bar {\chi} ({\cal H}) )$. A mixed hypergraph is called uncolorable if it admits no coloring. \par We show that there exist uncolorable mixed hypergraphs ${\cal H}=$ $(X, {\cal A}, {\cal E})$ with arbitrary difference between the upper chromatic number $\bar{\chi } ({\cal H}_{\cal A}) $ of ${\cal H}_{\cal A}=(X,{\cal A})$ and the lower chromatic number ${\chi }({\cal H}_{\cal E})$ of ${\cal H}_{\cal E}=(X,{\cal E}).$ Moreover, for any $k=\bar \chi ({\cal H}_{\cal A})- \chi ({\cal H}_{\cal E})$, the minimum number $v(k)$ of vertices of an inclusionwise minimal uncolorable mixed hypergraph is exactly $k+4.$ \par We introduce the measure of uncolorability which is called the vertex uncolorability number and propose a greedy algorithm that finds an estimate on it, and is a mixed hypergraph coloring heuristic at the same time. \par We show that the colorability problem can be expressed as an integer linear programming problem. \par Concerning particular cases, we describe those complete $(l,m)$-uniform mixed hypergraphs which are uncolorable, and observe that for given $(l,m)$ almost all complete $(l,m)$-uniform mixed hypergraphs are uncolorable, whereas generally almost all complete mixed hypergraphs are colorable.

Beschreibung: We present a self--adaptive finite element method to solve combustion problems in 1D, 2D, and 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. A posteriori error estimates are obtained by constructing locally higher order solutions involving all variables of the problem. Adaptive strategies such as step size control, spatial refinement and coarsening allow us to get economically an accurate solution. Various examples are presented to demonstrate practical applications of the proposed method.

Beschreibung: Let $G$ be a finite subgroup of SL$\left( r,% {\mathbb{C}}\right) $. In dimensions $r=2$ and $r=3$, McKay correspondence provides a natural bijection between the set of irreducible representations of $G$ and a cohomology-ring basis of the overlying space of a projective, crepant desingularization of ${\mathbb{C}}^r/G$. For $r=2$ this desingularization is unique and is known to be determined by the Hilbert scheme of the $G$% -orbits. Similar statements (including a method of distinguishing just {\it{one}} among all possible smooth minimal models of ${\mathbb{C}}^3/G$), are very probably true for all $G$'s $\subset $ SL$\left( 3,{\mathbb{C}}\right) $ too, and recent Hilbert-scheme-techniques due to Ito, Nakamura and Reid, are expected to lead to a new fascinating uniform theory. For dimensions $r\geq 4 $, however, to apply analogous techniques one needs extra modifications. In addition, minimal models of ${\mathbb{C}}^r/G$ are smooth only under special circumstances. ${\mathbb{C}}^4/\left( \hbox{\rm involution}\right) $, for instance, cannot have any smooth minimal model. On the other hand, all abelian quotient spaces which are c.i.'s can always be fully resolved by torus-equivariant, crepant, projective morphisms. Hence, from the very beginning, the question whether a given Gorenstein quotient space ${\mathbb{C}}% ^r/G$, $r\geq 4$, admits special desingularizations of this kind, seems to be absolutely crucial.\noindent In the present paper, after a brief introduction to the existence-problem of such desingularizations (for abelian $G$'s) from the point of view of toric geometry, we prove that the Gorenstein cyclic quotient singularities of type \[ \frac 1l\,\left( 1,\ldots ,1,l-\left( r-1\right) \right) \] with $l\geq r\geq 2$, have a \textit{unique }torus-equivariant projective, crepant, partial resolution, which is full'' iff either $l\equiv 0$ mod $% \left( r-1\right) $ or $l\equiv 1$ mod $\left( r-1\right) $. As it turns out, if one of these two conditions is fulfilled, then the exceptional locus of the full desingularization consists of $\lfloor\frac{l}{r-1} \rfloor $ prime divisors, $\lfloor\frac{l}{r-1} \rfloor -1$ of which are isomorphic to the total spaces of ${\mathbb{P}}_{{\mathbb{C}}}^1$-bundles over ${\mathbb{P}}_{{\mathbb{C}}% }^{r-2}$. Moreover, it is shown that intersection numbers are computable explicitly and that the resolution morphism can be viewed as a composite of successive (normalized) blow-ups. Obviously, the monoparametrized singularity-series of the above type contains (as its first member'') the well-known Gorenstein singularity defined by the origin of the affine cone which lies over the $r$-tuple Veronese embedding of ${\mathbb{P}}_{\mathbb{C}}^{r-1}$.

Beschreibung: We describe an extension of the line integral convolution method (LIC) for imaging of vector fields on arbitrary surfaces in 3D space. Previous approaches were limited to curvilinear surfaces, i.e.~surfaces which can be parametrized globally using 2D-coordinates. By contrast our method also handles the case of general, possibly multiply connected surfaces. The method works by tesselating a given surface with triangles. For each triangle local euclidean coordinates are defined and a local LIC texture is computed. No scaling or distortion is involved when mapping the texture onto the surface. The characteristic length of the texture remains constant. In order to exploit the texture hardware of modern graphics computers we have developed a tiling strategy for arranging a large number of triangular texture pieces within a single rectangular texture image. In this way texture memory is utilized optimally and even large textured surfaces can be explored interactively.

Beschreibung: A new technique for interactive vector field visualization using large numbers of properly illuminated field lines is presented. Taking into account ambient, diffuse, and specular reflection terms as well as transparency and depth cueing, we employ a realistic shading model which significantly increases quality and realism of the resulting images. While many graphics workstations offer hardware support for illuminating surface primitives, usually no means for an accurate shading of line primitives are provided. However, we show that proper illumination of lines can be implemented by exploiting the texture mapping capabilities of modern graphics hardware. In this way high rendering performance with interactive frame rates can be achieved. We apply the technique to render large numbers of integral curves of a vector field. The impression of the resulting images can be further improved by a number of visual enhancements, like transparency and depth-cueing. We also describe methods for controlling the distribution of field lines in space. These methods enable us to use illuminated field lines for interactive exploration of vector fields.

Beschreibung: The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.

Beschreibung: In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the %LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.

Beschreibung: In this paper we present a self--adaptive finite element method to solve flame propagation problems in 3D. An implicit time integrator of Rosenbrock type is coupled with a multilevel approach in space. The proposed method is applied to an unsteady thermo--diffusive combustion model to demonstrate its potential for the solution of complicated problems.

Beschreibung: The paper is concerned with the analysis of an $s$ server queueing system in which the calls become impatient and leave the system if their waiting time exceeds their own patience. The individual patience times are assumed to be i.i.d.\ and arbitrary distributed. The arrival and service rate may depend on the number of calls in the system and in service, respectively. For this system, denoted by $M(n)/M(m)/s+GI$, where $m=\min(n,s)$ is the number of busy servers in the system, we derive a system of integral equations for the vector of the residual patience times of the waiting calls and their original maximal patience times. By solving these equations explicitly we get the stability condition and, for the steady state of the system, the occupancy distribution and various waiting time distributions. As an application of the \mbox{$M(n)/M(m)/s+GI$} system we give a performance analysis of an Automatic Call Distributor system (ACD system) of finite capacity with outbound calls and impatient inbound calls, especially in case of patience times being the minimum of constant and exponentially distributed times.

Beschreibung: During the last years the interest in the numerical simulation of reacting flows has grown considerably and numerical methods are available, which allow to couple chemical kinetics with flow and molecular transport. The use of detailed physical and chemical models, involving several hundred species, is restricted to very simple flow configurations like one-dimensional systems or two-dimensional systems with very simple geometries, and models are required, which simplify chemistry without sacrificing accuracy. One method to simplify the chemical kinetics is based on Intrinsic Low-Dimensional Manifolds (ILDM). They present attractors for the chemical kinetics, i.e. fast chemical processes relax towards them, and slow chemical processes represent movements within the manifolds. Thus the identification of the ILDMs allows a decoupling of the fast time scales. The concept has been verified by many different reacting flow calculations. However, one remaining problem of the method is the efficient calculation of the low-dimensional manifolds. This problem is addressed in this paper. We present an efficient, robust method, which allows to calculate intrinsic low-dimensional manifolds of chemical reaction systems. It is based on a multi-dimensional continuation process. Examples are shown for a typical combustion system. The method is not restricted to this class, but can be applied to other chemical systems, too.

Beschreibung: Given a communication demand between each pair of nodes of a network we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy the demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. We treat, in addition, several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real world data.

Beschreibung: We present a mathematical formulation of a \emph{frequency assignment problem} encountered in cellular phone networks: frequencies have to be assigned to stationary transceivers (carriers) such that as little interference as possible is induced while obeying several technical and legal restrictions. The optimization problem is NP-hard, and no good approximation can be guaranteed---unless P = NP. We sketch some starting and improvement heuristics, and report on their successful application for solving the frequency assignment problem under consideration. Computational results on real-world instances with up to 2877 carriers and 50 frequencies are presented.

Beschreibung: This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.

Beschreibung: We survey the literature on those variants of the {\em chromatic number\/} problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the {\em list colorings\/} and the {\em precoloring extensions\/} are considered. \par In one of the most general formulations, a graph $G=(V,E)$, sets $L(v)$ of admissible colors, and natural numbers $c_v$ for the vertices $v\in V$ are given, and the question is whether there can be chosen a subset $C(v)\subseteq L(v)$ of cardinality $c_v$ for each vertex in such a way that the sets $C(v),C(v')$ are disjoint for each pair $v,v'$ of adjacent vertices. The particular case of constant $|L(v)|$ with $c_v=1$ for all $v\in V$ leads to the concept of {\em choice number}, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. \par To illustrate typical techniques, some of the proofs are sketched.

Beschreibung: A graph $G$ is called preperfect if each induced subgraph $G' \subseteq G$ of order at least 2 has two vertices $x,y$ such that either all maximum cliques of $G'$ containing $x$ contain $y$, or all maximum indepentent sets of $G'$ containing $y$ contain $x$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph $G$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if $G$ is bipartite, 3-edge-connected, regular of degree $d$ for some $d \ge 3$, and contains no 3-edge-connected $d'$-regular subgraph for any $3 \le d' \le d$. \end{itemize}

Beschreibung: A (vertex) $k$-ranking of a graph $G=(V,E)$ is a mapping $ p:V\to \{1,\dots,k\}$ such that each path with endvertices of the same color $i$ contains an internal vertex of color $\ge i+1$. In the on-line coloring algorithms, the vertices $v_1,\dots,v_n$ arrive one by one in an unrestricted order, and only the edges inside the set $\{v_1,\dots,v_i\}$ are known when the color of $v_i$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a $(3\log_2 n)$-ranking for the path with $n \geq 2$ vertices, independently of the order in which the vertices are received.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: In molecular dynamics applications there is a growing interest in including quantum effects for simulations of larger molecules. This paper is concerned with {\em mixed quantum-classical} models which are currently discussed: the so-called QCMD model with variants and the time-dependent Born-Oppenheimer approximation. All these models are known to approximate the full quantum dynamical evolution---under different assumptions, however. We review the meaning of these assumptions and the scope of the approximation. In particular, we characterize those typical problematic situations where a mixed model might largely deviate from the full quantum evolution. One such situation of specific interest, a non-adiabatic excitation at certain energy level crossings, can promisingly be dealt with by a modification of the QCMD model that we suggest.

Beschreibung: Seit fast drei Jahren betreibt das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) Parallelrechner der höchsten Leistungsklasse im normalen Rechenzentrumsbetrieb. Bereits im Mai 1995 hat das ZIB über seine Erfahrungen mit dem damals leistungsstärksten Parallelrechner Deutschlands berichtet. Das Gesamtkonzept des ZIB sieht weiterhin einen Höchstleistungsrechner als unabdingbaren Bestandteil des High Performance Scientific Computing (HPSC) im ZIB vor. Der vorliegende Bericht beschreibt die aktuelle Konfiguration, Betriebserfahrungen und die Rechnernutzung sowie typische Rechenleistungen, die für einzelne Anwendungsprogramme erzielt wurden. Beschreibungen der Forschungsgebiete mit den Forschungsgruppen, die den Rechner nutzen und die Anforderungen an den Rechnerausbau, die sich aus deren Arbeiten herleiten, beschließen den Bericht.

Beschreibung: This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.

Beschreibung: In this paper, we present a Dantzig-Wolfe decomposition for the $NP$-hard multiple-depot vehicle scheduling problem in public mass transit. It turned out that such a decomposition approach is an unsuitable method to solve such kind of multicommodity flow problems. The major obstacle to solve such problems is that the continuous master problem relaxations become too hard to be solved efficiently. Especially for problems with more than one thousand timetabled trips, the LU factorization in solving a restricted master problem takes far too much time. We will describe our computational experiments in detail and discuss the reasons why the decomposition method fails in this case. Our computational investigations are based on real-world problems from the city of Hamburg with up to 2,283 timetabled trips. Our decomposition implementation is compared with a delayed column generation to solve the linear programming (LP) relaxation directly. This LP method can solve the LP relaxations of the integer linear programming formulation exactly for truly large-scale real-world problems of the cities of Berlin and Hamburg.

Beschreibung: In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.

Beschreibung: This paper presents an integer linear programming approach with delayed column generation for the {\em NP} Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail all basic ingredients of our approach that are indispensable to solve truly large-scale real-world instances to optimality, and we report on computational investigations that are based on real-world instances from the city of Berlin, the city of Hamburg, and the region around Hamburg. These real-world instances have up to 25 thousand timetabled trips and 70 million dead-head trips. Computational tests using the data of the Hamburger Hochbahn AG indicate savings of several vehicles and a cost reduction of about 10\% compared with the solution provided by HOT II, the vehicle scheduling tool of the HanseCom GmbH, Hamburg. Parts of our algorithms are already integrated in the BERTA system of the Berliner Verkehrsbetriebe (BVG) and will soon be integrated in the MICROBUS system of the Gesellschaft für Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin.

Beschreibung: Based on an approach of Affentranger&Schneider we give an asymptotic formula for the expected number of $k$-faces of the orthogonal projection of a regular $n$-crosspolytope onto a randomly chosen isotopic subspace of fixed dimension, as $n$ tends to infinity. In particular, we present a precise asymptotic formula for the (spherical) volume of spherical regular simplices, which generalizes Daniel's formula.

Beschreibung: Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice.

Beschreibung: {\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before.

Beschreibung: \noindent The speaker and his co-workers in Scientific Computing and Visualization have established a close cooperation with medical doctors at the Rudolf--Virchow--Klinikum of the Humboldt University in Berlin on the topic of regional hyperthermia. In order to permit a patient--specific treatment planning, a special software system ({\sf\small HyperPlan}) has been developed. \noindent A mathematical model of the clinical system ({\it radio frequency applicator with 8 antennas, water bolus, individual patient body}) involves Maxwell's equations in inhomogeneous media and a so--called bio--heat transfer PDE describing the temperature distribution in the human body. The electromagnetic field and the thermal phenomena need to be computed at a speed suitable for the clinical environment. An individual geometric patient model is generated as a quite complicated tetrahedral ``coarse'' grid (several thousands of nodes). Both Maxwell's equations and the bio--heat transfer equation are solved on that 3D--grid by means of {\em adaptive} multilevel finite element methods, which automatically refine the grid where necessary in view of the required accuracy. Finally optimal antenna parameters for the applicator are determined . \noindent All steps of the planning process are supported by powerful visualization methods. Medical images, contours, grids, simulated electromagnetic fields and temperature distributions can be displayed in combination. A number of new algorithms and techniques had to be developed and implemented. Special emphasis has been put on advanced 3D interaction methods and user interface issues.

Beschreibung: This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.

Beschreibung: A central drawback of interior point methods for semidefinite programs is their lack of ability to exploit problem structure in cost and coefficient matrices. This restricts applicability to problems of small dimension. Typically semidefinite relaxations arising in combinatorial applications have sparse and well structured cost and coefficient matrices of huge order. We present a method that allows to compute acceptable approximations to the optimal solution of large problems within reasonable time. Semidefinite programming problems with constant trace on the primal feasible set are equivalent to eigenvalue optimization problems. These are convex nonsmooth programming problems and can be solved by bundle methods. We propose to replace the traditional polyhedral cutting plane model constructed by means of subgradient information by a semidefinite model that is tailored for eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficacy of the approach on combinatorial examples.

Beschreibung: This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view.