Library

Description: An edge of a perfect graph $G$ is critical if $G-e$ is imperfect. We would like to decide whether $G - e$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.

Description: Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.

Description: {\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.

Description: Im ersten Teil des folgenden Aufsatzes werden allgemeine Überlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen für sowohl elektronische wie auch gedruckte Medien angestellt. Basierend auf den Ergebnissen der Evaluation digitaler Bibliotheken und Informationsportale in Deutschland wird ein erster Kriterienkatalog für ein Verbund-Informationsportal für den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht über Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesländern evaluiert.

Description: Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers.

Description: Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.

Description: In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary.

Description: Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.

Description: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.

Description: Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.

Description: Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.

Description: We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.

Description: In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The $GI/M/C/0$ system is used to model a single link, where the $GI$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a $GI/M/C/0$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.

Description: In this work we concentrate on developing methods which determine good lower bounds for set partitioning problems (SPP) in an appropriate amount of time. We found out that it makes sense to use the Lagrangian relaxation method for this task. The Lagrangian relaxed problem of SPP has a simple structure, which leads to algorithms and heuristics, whose total complexity per iteration depends linearly on the number of non-zeros of the problem matrix of SPP. In contrast, other methods like simplex methods or interior point methods have a complexity of higher order. Because the problem matrices of our tested instances are sparse, the linear dependence becomes an advantage for the algorithms and heuristics mentioned above. As a reference for the state-of-the-art we have applied the dual simplex method and the barrier function method, implemented in CPLEX. The methods, which we have developed and compared with those of CPLEX, are SBM, CAM, CCBM, and CBM. SBM is a subgradient bundle method derived from the basic subgradient method, which is a global convergent method for determining the maximum of concave functions. CAM is a coordinate ascent method, where the convex coordinate bundle method CCBM and the coordinate bundle method CBM are derivatives from CAM. We observed that the basic subgradient and the coordinate ascent method are improved if bundling techniques can be used. But the motivation for bundling differs for both approaches. In the former case bundling helps to approximate a minimum norm subgradient, which provides a steepest ascent direction, in order to speed up the performance. In the latter case bundling enables proceeding along directions, which are not restricted on the coordinate directions. By this the performance is accelerated. Among all used techniques stabilization is worth mentioning. Stabilization improves the performance especially at the beginning by avoiding too big steps during the proceeding. This leads to a more stabilized progression. Stabilization was successfully applied to SBM, CAM, CCBM, and CBM. As an overall result we conclude the following: \begin{enumerate} \item CPLEX computes the optimal objective values, whereas SBM and CBM has on average a gap of under $1.5\%$. \item In comparison to CPLEX baropt, SBM, CAM, and CBM the algorithm CCBM has a slow convergence because of the convex combination of ascent coordinate directions. An alternative is to relax the convex combination to a simple sum of the corresponding directions. This idea is realized in CBM. \item If we focus on the running time rather than on optimality then CBM is on average the fastest algorithm. \end{enumerate} Note that methods like SBM or CBM are applied on static SPP instances in order to determine a good lower bound. For solving SPP we need dynamical methods. Due to the complex topic of dynamical methods we will not discuss them, but a certain technique is worth mentioning. It is called column generation. We have indicated that this technique needs good Lagrangian multipliers of the corresponding SPP instances in order to generate further columns (in our case duties), which are added to the current SPP instance. Those multipliers are by-products of methods like our six considered methods. Due to the large number of such generation steps the running time depends on the computation time of these methods. Therefore, CBM fits more to this technique than CPLEX baropt or SBM. To sum it up it can be said that applications such as a duty scheduling can be described as set partitioning problems, whose lower bound can be solved by simplex, interior points, subgradient, or coordinate ascent methods. It turns out that the interior points method CPLEX baropt and the heuristic CBM have good performances. Furthermore, good Lagrangian multipliers, which are by-products of these methods, can be used by techniques like column generation. For this particular technique it also turns out that among our tested algorithms CBM is the most efficient one. In general we can state that real-world applications, which have to solve a large number of Lagrangian relaxed SPP instances can improve their performance by using CBM.

Description: The success of large-scale multi-national projects like the forthcoming analysis of the LHC particle collision data at CERN relies to a great extent on the ability to efficiently utilize computing a management software (Datagrid, Globus, etc.), while the effective integration of computing nodes has been largely neglected up to now. This is the focus of our work. We present a framework for a high-performance cluster that can be used as a reliable computing node in the Grid. We outline the cluster architecture, the management of distributed data and the seamless intergration of the cluster into the Grid environment.

Description: Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten am 05.04.2001 auf dem 91. Deutschen Bibliothekartag in Bielefeld. Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist im Rahmen eines wissenschaftlichen Projektes in den Jahren 1997 bis 2000 am Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) aufgebaut worden. Nachdem das Projekt erfolgreich abgeschlossen ist, wird der KOBV 2001 institutionalisiert. In dem Vortrag hat die Verfasserin einen Überblick über das bisher Erreichte, den derzeitigen Stand und die Perspektiven des neuen Verbundes gegeben. Der KOBV stellt eine neue Art von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der {\sl Internetphilosophie}. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg. Eine kleine Verbundzentrale koordiniert dieses Geflecht vernetzter lokaler Einheiten, vertritt den KOBV nach außen und arbeitet - in Form von Projekten - an seiner Weiterentwicklung. Der Entwicklungsaspekt und die Nutzerorientierung sind zwei wesentliche Komponenten in der Verbundarbeit. Berlin und Brandenburg haben auf engem Raum zahlreiche Bibliotheken mit großen, reichhaltigen Medienbeständen. Mittel- bis langfristig sollen Bibliotheken aller Sparten und Größen in den KOBV integriert werden, seien es wissenschaftliche Universalbibliotheken, universitäre Bibliothekssysteme, Spezialbibliotheken, Behörden- und Parlamentsbibliotheken oder öffentliche Bibliotheken. Auch regionale Bibliotheksverbünde können als Subverbünde am KOBV teilnehmen. Mit der KOBV-Suchmaschine ist eine offene Plattform geschaffen worden, auf der weitere Entwicklungen aufsetzen können. Der Aufbau einer virtuellen Regionalbibliothek mit Bestell- und Lieferkomponenten ist eines der Ziele. Darüber hinaus ist es die Vision, in der Region ein virtuelles {\sl Wissensportal} aufzubauen, das dem Nutzer unter einer Adresse den umfassenden Zugang und die umfassende Bereitstellung von Informationen aller Art bietet.

Description: A new approach to the numerical solution of optimal control problems including control and state constraints is presented. Like hybrid methods, the approach aims at combining the advantages of direct and indirect methods. Unlike hybrid methods, however, our method is directly based on interior-point concepts in function space --- realized via an adaptive multilevel scheme applied to the complementarity formulation and numerical continuation along the central path. Existence of the central path and its continuation towards the solution point is analyzed in some theoretical detail. An adaptive stepsize control with respect to the duality gap parameter is worked out in the framework of affine invariant inexact Newton methods. Finally, the performance of a first version of our new type of algorithm is documented by the successful treatment of the well-known intricate windshear problem.

Description: Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich über die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und Lösungsvorschläge hierfür zu erarbeiten. Das Kernthema ist natürlich "`Elektronisches Publizieren"'. Dazu gehören auch Copyright-Regelungen. % Sie sind -- % neben einer Andeutung der weiteren CEIC-Pläne -- der Fokus dieses % kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten % Aufruf zu vernünftigem Verhalten bei Copyright-Vereinbarungen. Eine % nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren % Aktivitäten -- könnte die (derzeit kaum noch bezahlbare und % dadurch gefährdete) Literaturversorgung nachhaltig zum Positiven % verändern. Mit diesem Artikel beginnt eine kleine Serie von Aufsätzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erläutern werde. % Das heutige Thema sind die % CEIC-Vorschläge zum Copyright

Description: By computed tomography data (CT), the individual geometry of the mandible is quite well reproduced, also the separation between cortical and trabecular bone. Using anatomical knowledge about the architecture and the functional potential of the masticatory muscles, realistic situations were approximated. The solution of the underlying partial differential equations describing linear elastic material behaviour is provided by an adaptive finite element method. Estimations of the discretization error, local grid refinement, and multilevel techniques guarantee the reliability and efficiency of the method.

Description: Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.

Description: This paper describes a new simulation tool for the prediction of aerosol formation and behavior in gas--liquid contact devices such as absorbers, scrubbers, quench coolers, and condensers as well as multistage gas cleaning processes, respectively. Aerosol formation can impact severely the separation efficiency of gas cleaning processes. Aerosol or fog formation can arise by spontaneous condensation or desublimation in supersaturated gas phases. The rigorous description of the mass and energy transfer between the gas phase, the liquid phase, and the growing aerosol droplets leads to a system of partial differential and algebraic equations. For the solution of these systems we have developed the plant simulation tool AerCoDe. This program bases upon the linearly--implicit Euler discretisation, which in combination with extrapolation permits an adaptive step size and order control. Typical simulation results of a multistage industrial flue gas scrubbing process are presented. It is shown, that experimental data can be confirmed if the number concentration of condensation nuclei as an input parameter is roughly known.

Description: This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.

Description: Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.

Description: This paper is a summary of the Round Table: ``The Impact of Mathematical Research on Industry and Vice Versa'' held at 3ecm in Barcelona on July 11, 2000. The round table started with contributions of the three panelists. Irene Fonseca, the panel chair, opened the discussion by stating six questions addressing the main issues of the round table topic. She presented the panel's answers to these questions, drawing on many examples from her own academic experience. In the following additional presentations, the other two panel members added further points of view based on their personal involvement with industry. The round table ended with a lively discussion with members from the audience. This written summary of the oral presentations follows the structure of the round table indicated above.

Description: This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.

Description: The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.

Description: Der Wissenschaftsrat hat in seiner Juli-Sitzung 2001 \glqq Empfehlungen zur digitalen Informationsversorgung durch Hochschulbibliotheken \grqq verabschiedet. Einige der Vorschläge des Wissenschaftsrates können, falls sie von den angesprochenen Institutionen aufgenommen werden, zu einer nachhaltigen Veränderung der wissenschaftlichen Informationslandschaft führen. In meinem kurzen Kommentar zu diesem Papier möchte ich auf einige dieser Anregungen hinweisen.

Description: Von welcher "Informationsumwelt" träumt jemand, der für seine wissenschaftliche (und sonstige) Arbeit digitale Informationstechnologie intensiv einsetzt? In diesem Artikel beschreibe ich meinen "digitalen Traum". Er ist ganz einfach zu formulieren:"Ich will alles und zwar sofort, jederzeit, "überall" und kostenlos zur Verfügung haben." Ich schildere, was davon heute schon (fast) realisiert ist und was noch fehlt. Ich skizziere einige zentrale Schwierigkeiten der vollständigen Realisierung und skizziere mögliche Lösungen.

Description: Im Rahmen der biomechanischen Simulation knöcherner Organe ist die Frage nach einer befriedigenden Materialbeschreibung nach wie vor ungelöst. Computertomographische Datensätze liefern eine räumliche Verteilung der (Röntgen-)Dichte und ermöglichen damit eine gute Darstellung der individuellen Geometrie. Weiter können die verschiedenen Materialbestandteile des Knochens, Spongiosa und Kortikalis, voneinander getrennt werden. Aber die richtungsabängige Information der Materialanisotropie ist verloren. In dieser Arbeit wird ein Ansatz für eine anisotrope Materialbeschreibung vorgestellt, die es ermöglicht, den Einfluss der individuellen knöchernen Struktur auf das makroskopische Materialverhalten abzuschätzen.

Description: Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.

Description: By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants.

Description: Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed.

Description: Two traffic streams $\Phi_1$, $\Phi_2$ are offered a link. The calls of $\Phi_i$ require exponential holding times with parameter $\mu$ and are accepted if less than $C_i$ trunks are occupied. Approximating the $\Phi_i$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter $\mu$, stable recursive algorithms of complexity $O(\max(C_1,C_2))$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.

Description: We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on $10^4$ and $12^4$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter $\kappa$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.

Description: Dem vorliegenden Aufsatz liegt ein Vortrag zugrunde, den die Verfasserin auf der Ersten Gemeinsamen Fachtagung der DBV-Landesverbände Berlin und Brandenburg "Wir machen den Weg frei : Fusionen - Kooperationen in Berlin und Brandenburg" am 17. Oktober 2001 gehalten hat, in der Vortragsreihe "Möglichkeiten und Grenzen von Ausleih- und bibliographischen Verbünden - VÖB Berlin, VÖB Brandenburg, KOBV". Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist angetreten, um auf der Basis neuer Technologien zeitgemäße, nutzerorientierte Dienstleistungen für den Informationsbereich zu entwickeln und die Informationsinfrastruktur in der Region Berlin-Brandenburg neu zu organisieren. Dabei setzt der KOBV insbesondere auf das Internet. Die Verfasserin beschreibt die einzelnen Stufen, in denen die Dienste des KOBV aufgebaut wurden und kontinuierlich weiter ausgebaut werden. Dabei zeigt sie Vorteile auf, die Nutzern und Bibliotheken durch den Verbund entstehen, und lotet gleichzeitig die Grenzen aus, die dem Verbund gesetzt sind.

Description: We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.

Description: Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.

Description: The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.

Description: {\begin{rawhtml} 〈a href="http://dx.doi.org/10.1007/s10479-007-0178-0"〉 Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0〈/a〉 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

Description: Telota ist ein Kunstwort, das für alle Aktivitäten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der Förderung von Forschung, Kommunikation und Präsentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig für alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen für die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit fördern.

Description: The pole condition is a general concept for the theoretical analysis and the numerical solution of a variety of wave propagation problems. It says that the Laplace transform of the physical solution in radial direction has no poles in the lower complex half-plane. In the present paper we show that for the Helmholtz equation with a radially symmetric potential the pole condition is equivalent to Sommerfeld's radiation condition. Moreover, a new representation formula based on the pole condition is derived and used to prove existence, uniqueness and asymptotic properties of solutions. This lays the foundations of a promising new algorithm to solve time-harmonic scattering problems numerically and provides a new approach for analyzing existing algorithms such as the Perfectly Matched Layer (PML) method and the Bayliss-Gunzburger-Turkel (BGT) algorithm.

Description: In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.

Description: This paper addresses the problem of scheduling vehicles in a public mass transportation system. We show how this problem can be modelled as a special multicommodity flow problem and outline the solution methodology we have developed. Based on polyhedral investigations, we have designed and implemented a branch&cut algorithm and various heuristics with which real vehicle scheduling problems of truely large scale can be solved to optimality. We describe some implementation issues and report computational results.

Description: This paper provides the {\em first} detailed description of the architecture of the computing machines Z1 and Z3 designed by Konrad Zuse in Berlin between 1936 to 1941. The necessary information was obtained from a careful evaluation of the patent application filed by Zuse in 1941. Additional insight was gained from a software simulation of the machine's logic. The Z1 was built using purely mechanical components, the Z3 using electromechanical relays. However, both machines shared a common logical structure and the programming model was exactly the same. We argue that both the Z1 and the Z3 possessed features akin to those of modern computers: memory and processor were separate units, the processor could handle floating-point numbers and compute the four basic arithmetical operations as well as the square root of a number. The program was stored on punched tape and was read sequentially. In the last section of this paper we bring the architecture of the Z1 and Z3 into historical perspective by offering a comparison with computing machines built in other countries.

Description: We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Sun S20-502, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.

Description: We present an algorithm for solving stochastic integer programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-integer variables in each time stage. %We outline a branch-and-bound algorithm for obtaining primal feasible and %possibly optimal solutions. Numerical experience is presented for some two-stage test problems.

Description: The paper presents the concept of a new type of algorithm for the numerical computation of what the authors call the {\em essential dynamics\/} of molecular systems. Mathematically speaking, such systems are described by Hamiltonian differential equations. In the bulk of applications, individual trajectories are of no specific interest. Rather, time averages of physical observables or relaxation times of conformational changes need to be actually computed. In the language of dynamical systems, such information is contained in the natural invariant measure (infinite relaxation time) or in almost invariant sets ("large" finite relaxation times). The paper suggests the direct computation of these objects via eigenmodes of the associated Frobenius-Perron operator by means of a multilevel subdivision algorithm. The advocated approach is different to both Monte-Carlo techniques on the one hand and long term trajectory simulation on the other hand: in our setup long term trajectories are replaced by short term sub-trajectories, Monte-Carlo techniques are just structurally connected via the underlying Frobenius-Perron theory. Numerical experiments with a first version of our suggested algorithm are included to illustrate certain distinguishing properties. A more advanced version of the algorithm will be presented in a second part of this paper.

Description: The aim of this work is to study the accuracy and stability of the Chebyshev--approximation method as a time--discretization for wavepacket dynamics. For this frequently used discretization we introduce estimates of the approximation and round--off error. These estimates mathematically confirm the stability of the Chebyshev--approximation with respect to round--off errors, especially for very large stepsizes. But the results also disclose threads to the stability due to large spatial dimensions. All theoretical statements are illustrated by numerical simulations of an analytically solvable example, the harmonic quantum oszillator.

Description: We present an integrated time--space adaptive finite element method for solving systems of twodimensional nonlinear parabolic systems in complex geometry. The partial differential system is first discretized in time using a singly linearly implicit Runge--Kutta method of order three. Local time errors for the step size control are defined by an embedding strategy. These errors are used to propose a new time step by a PI controller algorithm. A multilevel finite element method with piecewise linear functions on unstructured triangular meshes is subsequently applied for the discretization in space. The local error estimate of the finite element solution steering the adaptive mesh refinement is obtained solving local problems with quadratic trial functions located essentially at the edges of the triangulation. This two--fold adaptivity successfully ensures an a priori prescribed tolerance of the solution. The devised method is applied to laminar gaseous combustion and to solid--solid alloying reactions. We demonstrate that for such demanding applications the employed error estimation and adaption strategies generate an efficient and versatile algorithm.

Description: \iffalse Recently, Todorov and Wilf independently realized that de Branges' original proof of the Bieberbach and Milin conjectures and the proof that was later given by Weinstein deal with the same special function system that de Branges had introduced in his work. In this article, we present an elementary proof of this statement based on the defining differential equations system rather than the closed representation of de Branges' function system. Our proof does neither use special functions (like Wilf's) nor the residue theorem (like Todorov's) nor the closed representation (like both), but is purely algebraic. On the other hand, by a similar algebraic treatment, the closed representation of de Branges' function system is derived. Our whole contribution can be looked at as the study of properties of the Koebe function. Therefore, in a very elementary manner it is shown that the known proofs of the Bieberbach and Milin conjectures can be understood as a consequence of the Löwner differential equation, plus properties of the Koebe function. \fi In his 1984 proof of the Bieberbach and Milin conjectures de Branges used a positivity result of special functions which follows from an identity about Jacobi polynomial sums that was found by Askey and Gasper in 1973, published in 1976. In 1991 Weinstein presented another proof of the Bieberbach and Milin conjectures, also using a special function system which (by Todorov and Wilf) was realized to be the same as de Branges'. In this article, we show how a variant of the Askey-Gasper identity can be deduced by a straightforward examination of Weinstein's functions which intimately are related with a Löwner chain of the Koebe function, and therefore with univalent functions.

Description: This paper presents a large-scale real-world application of the minimum-cost flow problem, describes some details of a new implementation of the network simplex algorithm, and reports on computational comparisions. The real-world test sets include minimum-cost flow problems that are based on single-depot vehicle scheduling problems and on a Lagrangean relaxation of multiple-depot vehicle scheduling problems. Some of the problems are extremely large with up to 42,000 nodes and 20,000,000 arcs. The standard test problems are generated with NETGEN and include parts of the DIMACS standard problems. Our network simplex code is compared with \mbox{RELAX-IV}, Cost Scaling 2 version 3.4, and CPLEX's network solver NETOPT.

Description: Integrals of optimal values of random optimization problems depending on a finite dimensional parameter are approximated by using empirical distributions instead of the original measure. Under fairly broad conditions, it is proved that uniform convergence of empirical approximations of the right hand sides of the constraints implies uniform convergence of the optimal values in the linear and convex case.

Description: The adaptive Rothe method approaches a time-dependent PDE as an ODE in function space. This ODE is solved {\em virtually} using an adaptive state-of-the-art integrator. The {\em actual} realization of each time-step requires the numerical solution of an elliptic boundary value problem, thus {\em perturbing} the virtual function space method. The admissible size of that perturbation can be computed {\em a priori} and is prescribed as a tolerance to an adaptive multilevel finite element code, which provides each time-step with an individually adapted spatial mesh. In this way, the method avoids the well-known difficulties of the method of lines in higher space dimensions. During the last few years the adaptive Rothe method has been applied successfully to various problems with infinite speed of propagation of information. The present study concerns the adaptive Rothe method for hyperbolic equations in the model situation of the wave equation. All steps of the construction are given in detail and a numerical example (diffraction at a corner) is provided for the 2D wave equation. This example clearly indicates that the adaptive Rothe method is appropriate for problems which can generally benefit from mesh adaptation. This should be even more pronounced in the 3D case because of the strong Huygens' principle.

Description: A numerical method for the treatment of moving discontinuities in the model equations of chemical engineering systems is presented. The derived model describing the effects of condensation and evaporation in a regenerative air to air heat exchanger yields an illustrative example for these so called moving boundary problems. The presented adaptive moving grid method is based on the algorithm {\sc Pdex} for parabolic partial differential equations. It is shown that the method is suited for problems where the arising discontinuities cause low rates of convergence if the equations are solved with a static grid.

Description: Nahezu flächendeckend sind die mathematischen Fachbereiche der BRD zum Jahresende '95 im WWW vertreten. Durch die relative hohe Zahl von Servern entstehen Schwierigkeiten bei der Sichtung der angebotenen Information. Wir besprechen "Harvest" als brauchbares und gebrauchsfähiges Hilfsmittel zur Dokumentation.

Description: Der Report analysiert die Ergebnisse des Projektes ,,Verbesserung des benutzerorientierten Zugriffs auf fachspezifische Online und CD-ROM Datenbanken für Mathematische Institute der Bundesrepublik Deutschland'' der Deutschen Mathematiker-Vereinigung. An dem Projekt, das vom ZIB geleitet und koordiniert worden ist, haben mehr als 50 mathematische Fachbereiche und Forschungsinstitute teilgenommen. Dieses vom damaligen BMFT (einem Teil des jetzigen Bundesministeriums für Bildung, Wissenschaft, Forschung und Technologie) geförderte Projekt hat wesentlich dazu beigetragen, dass fachspezifische Datenbanken heute in den mathematischen Fachbereichen in Deutschland zu den selbstverständlichen Arbeitsmitteln gehören. Darüber hinaus hat das Projekt die Grundlagen für eine moderne elektronische Informations- und Kommunikationsstruktur in den mathematischen Fachbereichen gelegt.

Description: Dieser Report beschreibt ein Konzept zur einheitlichen Bereitstellung von Software in heterogenen Umgebungen. Software kann so kooperativ durch mehrere Beteiligten (z. B. auch über Institutsgrenzen hinweg) angeboten und genutzt werden. Die Konzepte stammen ursprünglich vom Rechenzentrum der Universität Stuttgart (RUS) und wurden im Rahmen eines vom Verein zur Förderung eines Deutschen Forschungsnetzes (DFN) mit Mitteln des BMBF geförderten Projekts zur Berliner Software Distribution (BeSD) weiterentwickelt.

Description: In this thesis we describe a practical problem that we encountered in the on--line optimization of a complex Flexible Manufacturing System. In the considered system a stacker crane has to fulfill all transportation tasks (jobs) in a single aisled automatic storage system. The jobs have to be sequenced in such a way, that the time needed for the unloaded moves is minimized. The modelling of this question leads to the so--called on--line Hamiltonian path problem. We computationally compare several on--line heuristics and derive lower bounds on the value obtained by an optimal on--line strategy by analyzing two off--line Combinatorial Optimization problems: the asymmetric Hamiltonian path problem with precedence constraints, also called sequential ordering problem (SOP), and the asymmetric Hamiltonian path problem with time windows (AHPPTW). We study the SOP and AHPPTW from a polyhedral point of view and derive several new classes of valid inequalities. Based on the polyhedral investigations we develop branch&cut algorithms for both problems and can achieve encouraging results on solving problem instances from real--world examples of the practical application.

Description: Steht uns das Ende des traditionellen wissenschaftlichen Publizierens bevor? Neue Technologien eröffnen neue Chancen zur Bewältigung der Informationsflut und des gleichzeitigen Informationsmangels. Doch der Einsatz von Technik allein reicht nicht aus.

Description: Der Artikel ist die ausgearbeitete und erweiterte Fassung eines eingeladenen Vortrags der Tagung ,,Die unendliche Bibliothek - Digitale Information in Wissenschaft, Verlag und Bibliothek''. Dieses Treffen, eine Veranstaltung des Börsenvereins des Deutschen Buchhandels e.V., der Deutschen Bibliothek und der Bundesvereinigung Deutscher Bibliothkesverbände, fand im Dezember 1995 in Bonn als Beitrag zur der heute aktuellen Debatte unter Wissenschaftlern, Verlegern, Buchhändlern, Bibliothekaren und Politikern statt, wie unser Wissen und unsere Informationen digital transferiert werden können. Der Vortrag stellte das zentrale Problem des heutigen wissenschaftlichen Informationswesens dar, die gleichzeitige Existenz von Informationsflut und Informationsmangel. Nach einer knappen Bestimmung der Veränderung der Kommunikationsstrukturen in den Wissenschaften fragte er nach den essentiellen Veränderungen der Informationsarten, d.h. nach der Natur der kommenden Globalen Digitalen Bibliothek, die als ein über die ganze Welt und auf viele Institutionen verteilter globaler Speicher gesehen wird. Der Vortrag diskutierte zum Schluss die Bedürfnisse und Interessen der Wissenschaften und ihre spezifische Verantwortung beim Übergang in die elektronische Welt. Der Tagungsband ist erschienen beim Harrassowitz Verlag, Wiesbaden, 1996.

Description: The Internet and the new electronic means of information and communication are transforming scientific communication fundamentally. In particular, mathematicians, physicists and other natural scientists intensify, accelerate and extend their communication by the use of the Internet and its tools, from electronic mail up to the World Wide Web. In doing so, they also exchange scientific results of a new kind and quality yet unknown to traditional information providers such as publishers, libraries, and database suppliers (e.g. in the form of current research software, scientific data collections, observations and experimental data, visualizations, animations etc.). They, on the other hand, perceive the new ways, which are passing their own field of activity, as breakdowns of traditional publishing, as it was termed by the Association of Computing Machinery. In addition, scientific libraries find themselves caught in a structural crisis -- not only because of budget restraints. The {\it Deutsche Mathematiker-Vereinigung} (DMV), however, sees the new electronic means as an opportunity to master a crisis of this kind rather than a threat. By discussing concrete models, which may be - in a certain technical sense -- realizable already today, the article gives an introduction into the subject of a {\it Distributed Information- and Communication System for Mathematics}, a project prepared and planned by the DMV for the years 1996 to 1998. In the context of possible realization variants it also deals with questions of costs, resulting load of network connections, and -- showing the beginnings -- the (absolutely essential) solution of problems related to quality, authenticity, archival and intellectual property rights, which arise with the employment of electronic means. Obviously (even if not discussed explicitly) also computing centers, whose tasks and position are also affected by the electronic revolution, have the chance to find a new and forward-looking role in this field - in particular by new forms of cooperation with scientific libraries.

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

Description: In diesem Handbuch werden die Bausteine zum Aufbau einer graphischen Benutzeroberfläche mit {\tt ZGUI} beschrieben. Auf der einen Seite stehen die Tcl/Tk--Prozeduren, die die graphischen Elemente definieren. Die Beschreibung der Anwendung der Prozeduren und der Interaktionen der Elemente bildet den ersten Teil des Handbuches. Auf der anderen Seite stehen die Anforderungen an Anwendungen, die mit einer {\tt ZGUI}--Benutzeroberlfäche gesteuert werden sollen. Hier findet man im Handbuch die Beschreibung der Anwendungsprogrammierschnittstelle (application programming interface, API).

Description: Dieser Aufsatz ist die Ausarbeitung eines Vortrags auf der 4. Jahrestagung der Gesellschaft Information Bildung (GIB) am 10. und 11. Oktober 1996 an der Humboldt-Universität Berlin. Er enthält einen Überblick über die neuesten Entwicklungen in der Informations- und Kommunikationstechnik und beleuchtet deren Auswirkungen auf den Wissenschaftsbetrieb. Er beginnt mit historischen Anmerkungen zur Entstehung der Schrift und zur Speicherung und Übertragung von Information. Er führt, nach einer knappen Diskussion der Defizite in der gegenwärtigen Informationsversorgung und einem kurzen Ausflug in die Geschichte des Internet und des World Wide Web, zu einer Darstellung ausgewählter aktueller Aktivitäten der Wissenschaften im Bereich elektronischer Information, Kommunikation, Dokumentation und Archivierung. Dabei zeigt sich, dass sich der Begriff wissenschaftlicher Information bereits zu wandeln beginnt. Zur traditionellen papiergebundenen Information treten völlig neue Informationsarten hinzu, von Software- und Datensammlungen über multimediale Information bis hin zu Fernübertagungen von wissenschaftlichen Vorträgen und Experimenten. Eine Vielzahl von Links; (URL's bzw. anklickbaren Verweisen) soll diesen Wandel nicht nur belegen, sondern auch das rasche Auffinden wichtiger Dokumente und Quellen im Internet ermöglichen.

Description: {\footnotesize In der vorliegenden Arbeit werden neue Implementierungen des dualen und primalen revidierten Simplex-Algorithmus für die Lösung linearer Programme (LPs) vorgestellt. Dazu werden die Algorithmen mithilfe einer Zeilenbasis dargestellt, aus der über einen Spezialfall die übliche Darstellung mit einer Spaltenbasis folgt. Beide Darstellungen sind über die Dualität eng miteinander verbunden. Ausserdem wird eine theoretische Untersuchung der numerischen Stabilität von Simplex-Algorithmen durchgeführt, und es werden verschiedene Möglichkeiten der Stabilisierung diskutiert. Beide Darstellungen der Basis werden in den Implementierungen algorithmisch ausgenutzt, wobei der Einsatz der Zeilenbasis für LPs mit mehr Nebenbedingungen als Variablen Geschwindigkeitsvorteile bringt. Darüberhinaus werden weitere Beschleunigung gegenüber anderen state-of-the-art Implentierungen erzielt, und zwar durch den Einsatz eines Phase-1 LPs, das eine grösstmögliche Übereinstimmung mit dem Ausgangs-LPs aufweist, durch eine dynamische Anpassung der Faktorisierungsfrequenz für die Basis-Matrix und durch die Optimierung der Lösung linearer Gleichungssysteme für besonders dünnbesetzte Matrizen und Vektoren. Es wurden drei Implementierungen vorgenommen. Die erste läuft sequentiell auf einem PC oder einer Workstation. Ihre hohe numerische Stabilität und Effizienz durch die Integration der oben genannten Konzepte machen sie zu einem zuverlässigen Hilfsmittel für den täglichen Einsatz z.B.~in Schnittebenenverfahren zur Lösung ganzzahliger Programme. Als Programmiersprache wurde C++ verwendet, und es wurde ein objektorientierter Software-Entwurf zugrundegelegt. Dieser leistet eine hohe Flexibilität und Anpassbarkeit z.B.~für die Integration benutzerdefinierter Pricing-Strategien. Bei den anderen beiden Implentierungen handelt es sich um parallele Versionen für Parallelrechner mit gemeinsamem und für solche mit verteiltem Speicher. Dabei wird der objektorientierte Entwurf so genutzt, dass lediglich die zusätzlichen Aufgaben für die Parallelisierung (Synchronisation, Kommunikation und Verteilung der Arbeit) implementiert werden, während alle Algorithmen von der sequentiellen Implementierung geerbt werden. Die Parallelisierung setzt an vier Punkten an. Der erste und einfachste ist die parallele Berechnung eines Matrix-Vektor-Produktes. Als zweites wurden beim Pricing und Quotiententest parallele Suchalgorithmen eingesetzt. Weiter werden beim steepest-edge Pricing zwei lineare Gleichungssysteme nebenläufig gelöst. Schliesslich wird ein paralleles Block-Pivoting verwendet, bei dem Gleichungssysteme mehrerer aufeinanderfolgender Iterationen gleichzeitig gelöst werden. Ob und welche der Parallelisierungs-Konzepte eine Beschleunigung bewirken, ist problemabhängig. Es gelingt z.B.~mit 32 Prozessoren eine Beschleunigung um mehr als einen Faktor 16 zu erzielen. Schliesslich wird die parallele Lösung dünnbesetzter linearer Gleichungssysteme mit unsymmetrischen Matrizen untersucht und eine Implementierung für den Cray T3D vorgenommen. Sie enthält ein neues Verfahren des Lastausgleichs, das keinen zusätzlichen Aufwand verursacht. Die Implementierung erzielt vergleichsweise günstige Laufzeiten.}

Description: We present parallel formulations of the well established extrapolation algorithms EULSIM and LIMEX and its implementation on a distributed memory architecture. The discretization of partial differential equations by the method of lines yields large banded systems, which can be efficiently solved in parallel only by iterative methods. Polynomial preconditioning with a Neumann series expansion combined with an overlapping domain decomposition appears as a very efficient, robust and highly scalable preconditioner for different iterative solvers. A further advantage of this preconditioner is that all computation can be restricted to the overlap region as long as the subdomain problems are solved exactly. With this approach the iterative algorithms operate on very short vectors, the length of the vectors depends only on the number of gridpoints in the overlap region and the number of processors, but not on the size of the linear system. As the most reliable and fast iterative methods based on this preconditioning scheme appeared GMRES or FOM and BICGSTAB. To further reduce the number of iterations in GMRES or FOM we can reuse the Krylov-spaces constructed in preceeding extrapolation steps. The implementation of the method within the program LIMEX results in a highly parallel and scalable program for solving differential algebraic problems getting an almost linear speedup up to 64 processors even for medium size problems. Results are presented for a difficult application from chemical engineering simulating the formation of aerosols in industrial gas exhaust purification.

Description: We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.

Description: The paper presents computations of decaying two--dimensional turbulence in an adaptive wavelet basis. At each time step the vorticity is represented by an adaptively selected set of wavelet functions which adjusts to the instantaneous distribution of vorticity. The results of this new algorithm are compared to a classical Fourier method and a Fourier method supplemented with wavelet compression in each time step.

Description: For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.

Description: In General Relativity, the motion of expanding shearfree perfect fluids is governed by the ordinary differential equation $y^{\prime \prime }=$ $% F(x)\,y^2$ , where $F$ is an arbitrary function from which the equation of state can be computed. A complete symmetry analysis of this differential equation is given; its solutions are classified according to this scheme, and in particular the relation to Wyman's Painlev\'e analysis is clarified.

Description: Der Entwurf und die Implementierung des auf Tcl/Tk basierenden Werkzeugkastens ZGUI wird beschrieben und an einigen Beispielen erläutert. ZGUI unterstützt die Entwicklung einer graphischen Benutzeroberfläche (GUI) für die am ZIB erstellte numerische Software. Es sollen folgende Ziele erreicht werden: \begin{itemize} \item einfaches Ausprobieren anhand vordefinierter Testprobleme,\vspace*{-2mm} \item Kennenlernen numerischer Steuergrö\ss en und Verfahrensvarianten,\vspace*{-2mm} \item einfache Eingabe neuer Probleme,\vspace*{-2mm} \item einfache Nutzung graphischer Ausgabemöglichkeiten und\vspace*{-2mm} \item einheitliche Darstellung gleicher oder ähnlicher Optionen. \end{itemize}

Description: We perform a high statistics calculation of the equation of state for non-compact QED on large lattices. The calculation extends to fermionic correlation lengths of $\approx 8$, and it is combined with a finite size scaling analysis of the lattice data.

Description: We consider the fast solution of large, piecewise smooth minimization problems as resulting from the approximation of elliptic free boundary problems. The most delicate question in constructing a multigrid method for a nonlinear, non--smooth problem is how to represent the nonlinearity on the coarse grids. This process usually involves some kind of linearization. The basic idea of monotone multigrid methods to be presented here is first to select a neighborhood of the actual smoothed iterate in which a linearization is possible and then to constrain the coarse grid correction to this neighborhood. Such a local linearization allows to control the local corrections at each coarse grid node in such a way that the energy functional is monotonically decreasing. This approach leads to globally convergent schemes which are robust with respect to local singularities of the given problem. The numerical performance is illustrated by approximating the well-known Barenblatt solution of the porous medium equation.

Description: We prove inequalities relating the inradius of a convex body with interior containing no point of the integral lattice, with the volume or surface area of the body. These inequalities are tight and generalize previous results.

Description: The paper addresses the unit commitment problem in power plant operation planning. For a real power system comprising coal and gas fired thermal as well as pumped storage hydro plants a large-scale mixed integer optimization model for unit commitment is developed. Then primal and dual approaches to solving the optimization problem are presented and results of test runs are reported.

Description: \small Many interesting phenomena in molecular systems like interactions between macro-molecules, protein-substrate docking, or channeling processes in membranes are gouverned to a high degree by classical Coulomb or van-der-Waals forces. The visualization of these force fields is important for verifying numerical simulations. Moreover, by inspecting the forces visually we can gain deeper insight into the molecular processes. Up to now the visualization of vector fields is quite unusual in computational chemistry. In fact many commercial software packages do not support this topic at all. The reason is not that vector fields are considered unimportant, but mainly because of the lack of adequate visualization methods. In this paper we survey a number of methods for vector field visualization, ranging from well-known concepts like arrow or streamline plots to more advanced techniques like line integral convolution, and show how these can be applied to computational chemistry. A combination of the most meaningful methods in an interactive 3D visualization environment can provide a powerful tool box for analysing simulations in molecular dynamics.

Description: In this paper we generalize a result by Rubin and Ungar on Hamiltonian systems containing a strong constraining potential to Langevin dynamics. Such highly oscillatory systems arise, for example, in the context of molecular dynamics. We derive constrained equations of motion for the slowly varying solution components. This includes in particular the derivation of a correcting force-term that stands for the coupling of the slow and fast degrees of motion. We will identify two limiting cases: (i) the correcting force becomes, over a finite interval of time, almost identical to the force term suggested by Rubin and Ungar (weak thermal coupling) and (ii) the correcting force can be approximated by the gradient of the Fixman potential as used in statistical mechanics (strong thermal coupling). The discussion will shed some light on the question which of the two correcting potentials is more appropriate under which circumstances for molecular dynamics. In Sec.~7, we also discuss smoothing in the context of constant temperature molecular dynamics.

Description: We present efficient techniques for the numerical approximation of complicated dynamical behavior. In particular, we develop numerical methods which allow to approximate SBR-measures as well as (almost) cyclic behavior of a dynamical system. The methods are based on an appropriate discretization of the Frobenius-Perron operator, and two essentially different mathematical concepts are used: the idea is to combine classical convergence results for finite dimensional approximations of compact operators with results from Ergodic Theory concerning the approximation of SBR-measures by invariant measures of stochastically perturbed systems. The efficiency of the methods is illustrated by several numerical examples.

Description: We present Multilevel Finite Element computations for twodimensional reaction-diffusion systems modelling laminar flames. These systems are prototypes for extreme stiffness in time and space. The first of these two rather general features is accounted for by an improved control mechanism for the time step. The second one is reflected through very thin travelling reaction fronts for which we propose an anisotropic discretization by local directional refinement.

Description: Simplified chemical kinetic schemes are a crucial prerequisite for the simulation of complex three-dimensional turbulent flows, and various methods for the generation of reduced mechanisms have been developed in the past. The method of intrinsic low-dimensional manifolds (ILDM), e.g., provides a mathematical tool for the automatic simplification of chemical kinetics, but one problem of this method is the fact that the information which comes out of the mechanism reduction procedure has to be stored for subsequent use in reacting flow calculations. In most cases tabulation procedures are used which store the relevant data (such as reduced reaction rates) in terms of the reaction progress variables, followed by table look-up during the reacting flow calculations. This can result in huge amounts of storage needed for the multi-dimensional tabulation. In order to overcome this problem we present a storage scheme which is based on orthogonal polynomials. Instead of using small tabulation cells and local mesh refinement, the thermochemical state space is divided into a small number of coarse cells. Within these coarse cells polynomial approximations are used instead of frequently used multi-linear interpolation. This leads to a considerable decrease of needed storage. The hydrogen-oxygen system is considered as an example. Even for this small chemical system we obtain a decrease of the needed storage requirement by a factor of 100.

Description: The Car-Parrinello (CP) approach to ab initio molecular dynamics serves as an approximation to time-dependent Born-Oppenheimer (BO) calculations. It replaces the explicit minimization of the energy functional by a fictitious Newtonian dynamics and therefore introduces an artificial mass parameter $\mu$ which controls the electronic motion. A recent theoretical investigation shows that the CP-error, i.e., the deviation of the CP--solution from the BO-solution {\em decreases} like $\mu^{1/2}$ asymptotically. Since the computational effort {\em increases} like $\mu^{-1/2}$, the choice of $\mu$ has to find a compromise between efficiency and accuracy. The asymptotical result is used in this paper to construct an easily implemented algorithm which automatically controls $\mu$: the parameter $\mu$ is repeatedly adapted during the simulation by choosing $\mu$ as large as possible while pushing an error measure below a user-given tolerance. The performance and reliability of the algorithm is illustrated by a typical example.

Description: The Car-Parrinello method for ab-initio molecular dynamics avoids the explicit minimization of energy functionals given by functional density theory in the context of the quantum adiabatic approximation (time-dependent Born-Oppenheimer approximation). Instead, it introduces a fictitious classical dynamics for the electronic orbitals. For many realistic systems this concept allowed first-principle computer simulations for the first time. In this paper we study the {\em quantitative} influence of the involved parameter $\mu$, the fictitious electronic mass of the method. In particular, we prove by use of a carefully chosen two-time-scale asymptotics that the deviation of the Car-Parrinello method from the adiabatic model is of order ${\rm O}(\mu^{1/2})$ --- provided one starts in the ground state of the electronic system and the electronic excitation spectrum satisfies a certain non-degeneracy condition. Analyzing a two-level model problem we prove that our result cannot be improved in general. Finally, we show how to use the gained quantitative insight for an automatic control of the unphysical ``fake'' kinetic energy of the method.

Description: We consider backward error analysis of numerical approximations to ordinary differential equations, i.e., the numerical solution is formally interpreted as the exact solution of a modified differential equation. A simple recursive definition of the modified equation is stated. This recursion is used to give a new proof of the exponentially closeness of the numerical solutions and the solutions to an appropriate truncation of the modified equation. We also discuss qualitative properties of the modified equation and apply these results to the symplectic variable step-size integration of Hamiltonian systems, the conservation of adiabatic invariants, and numerical chaos associated to homoclinic orbits.

Description: This paper presents two Lagrangean relaxation approaches for the {\em NP}-hard multiple-depot vehicle scheduling problem in public mass transit and reports on computational investigations. Our Lagrangean relaxation approaches can be applied to generate very tight lower bounds and to compute feasible solutions efficiently. A further application is to use the Lagrangean relaxations as new pricing strategies for a delayed column generation of a branch-and-cut approach. The computational investigations are based on real-world test sets from the cities of Berlin and Hamburg having up to 25 thousand timetabled trips and 70 million dead-head trips.

Description: It is well-known that by polynomial elimination methods, in particular by the computation of Gröbner bases, proofs for geometric theorems can be automatically generated. %% Several monographs On the other hand, it is much less known that Gröbner bases, in combination with rational factorization, can be even used to {\sl find} new geometric theorems. In this article such a method is described, and some new theorems on plane triangles are deduced.

Description: \begin{enumerate} \item[] {{\small In this article explicit formulas for the recurrence equation \[ p_{n+1}(x)=(A_n\,x+B_n)\,p_n(x)-C_n\,p_{n-1}(x) \] and the derivative rules \[ \sigma(x)\,p_n'(x)=\alpha_n\,p_{n+1}(x)+\beta_n\,p_n(x)+\gamma_n\,p_{n-1}(x) \] and \[ \sigma(x)\,p_n'(x)=(\tilde\alpha_n\,x+\tilde\beta_n)\,p_n(x)+ \tilde\gamma_n\,p_{n-1}(x) \] respectively which are valid for the orthogonal polynomial solutions $p_n(x)$ of the differential equation \[ \sigma(x)\,y''(x)+\tau(x)\,y'(x)+\lambda_n\,y(x)=0 \] of hypergeometric type are developed that depend {\sl only} on the coefficients $\sigma(x)$ and $\tau(x)$ % and $\lambda_n$ which themselves are polynomials w.r.t.\ $x$ of degrees not larger than $2$ and $1$% and $0$ , respectively. Partial solutions of this problem had been previously published by Tricomi, and recently by Y\'a\~nez, Dehesa and Nikiforov. Our formulas yield an algorithm with which it can be decided whether a given holonomic recurrence equation (i.e.\ one with polynomial coefficients) generates a family of classical orthogonal polynomials, and returns the corresponding data (density function, interval) including the standardization data in the affirmative case. In a similar way, explicit formulas for the coefficients of the recurrence equation and the difference rule \[ \sigma(x)\,\nabla p_n(x)= \alpha_n\,p_{n+1}(x)+\beta_n\,p_n(x)+\gamma_n\,p_{n-1}(x) \] of the classical orthogonal polynomials of a discrete variable are given that depend only on the coefficients $\sigma(x)$ and $\tau(x)$ of their difference equation \[ \sigma(x)\,\Delta\nabla y(x)+\tau(x)\,\Delta y(x)+\lambda_n\,y(x)=0 \;. \] Here \[ \Delta y(x)=y(x+1)-y(x) \quad\quad\mbox{and}\quad\quad \nabla y(x)=y(x)-y(x-1) \] denote the forward and backward difference operators, respectively. In particular this solves the corresponding inverse problem to find the classical discrete orthogonal polynomial solutions of a given holonomic recurrence equation. \iffalse Furthermore, an algorithmic approach to deduce these and similar properties is presented which is implementable in computer algebra, and which moreover generates relations between different standardizations of the polynomial system considered. \fi }} \end{enumerate}

Description: The paper addresses the possibilities of reducing the overall number of degrees of freedom in large scale reactive flow computations. Attention focusses on the dimension reduction technique ILDM due to {\sc Maas and Pope}, which treats certain automatically detected fast dynamic components as algebraic equations (so-called slow manifold). In earlier papers, the dimension of the reduction had been kept constant throughout each computation. Recently, a mathematically sound and nevertheless cheap dimension monitor for the chemistry part only has been suggested by {\sc Deuflhard and Heroth}. The present paper reports about first steps taken towards the implementation of that monitor into a flame code. Moreover, a sparse grid storage scheme is advocated and analyzed in view of the construction of efficient table look--ups for nested manifolds.

Description: Using the full multigrid method {\em without} any coarse grid correction steps but with an a posteriori control of the number of smoothing iterations was shown by Bornemann and Deuflhard [1996] to be an optimal iteration method with respect to the energy norm. They named this new kind of multigrid iteration the {\em cascadic multigrid method}. However, numerical examples with {\em linear} finite elements raised serious doubts whether the cascadic multigrid method can be made optimal with respect to the {\em $L^2$-norm}. In this paper we prove that the cascadic multigrid method cannot be optimal for linear finite elements and show that the case might be different for higher order elements. We present a careful analysis of the two grid variant of the cascadic multigrid method providing a setting where one can understand the methodical difference between the cascadic multigrid method and the classical multigrid $V$-cycle almost immediately. As a rule of thumb we get that whenever the cascadic multigrid works the classical multigrid will work too but not vice versa.

Description: An integrated time--space adaptive finite element method for solving mixed systems of nonlinear parabolic, elliptic, and differential algebraic equations is presented. The approach is independent of the spatial dimension. For the discretization in time we use singly diagonally linearly implicit Runge--Kutta methods of Rosenbrock type. Local time errors for the step size control are defined by an embedded strategy. A multilevel finite element Galerkin method is subsequently applied for the discretization in space. A posteriori estimates of local spatial discretization errors are obtained solving local problems with higher order approximation. Superconvergence arguments allow to simplify the required computations. Two different strategies to obtain the start grid of the multilevel process are compared. The devised method is applied to a solid--solid combustion problem.

Description: This paper investigates the solution of the linear programming (LP) relaxation of the multicommodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. We develop a column generation technique that makes it possible to solve the huge linear programs that come up there. The technique, which we call {\em Lagrangean pricing}, is based on two different Lagrangean relaxations. We describe in detail the basic ingredients of our approach and give computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies. Because of these results, we propose Lagrangean pricing as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality.

Description: The finite element setting for nonlinear elliptic PDEs directly leads to the minimization of convex functionals. Uniform ellipticity of the underlying PDE shows up as strict convexity of the arising nonlinear functional. The paper analyzes computational variants of Newton's method for convex optimization in an affine conjugate setting, which reflects the appropriate affine transformation behavior for this class of problems. First, an affine conjugate Newton--Mysovskikh type theorem on the local quadratic convergence of the exact Newton method in Hilbert spaces is given. It can be easily extended to inexact Newton methods, where the inner iteration is only approximately solved. For fixed finite dimension, a special implementation of a Newton--PCG algorithm is worked out. In this case, the suggested monitor for the inner iteration guarantees quadratic convergence of the outer iteration. In infinite dimensional problems, the PCG method may be just formally replaced by any Galerkin method such as FEM for linear elliptic problems. Instead of the algebraic inner iteration errors we now have to control the FE discretization errors, which is a standard task performed within any adaptive multilevel method. A careful study of the information gain per computational effort leads to the result that the quadratic convergence mode of the Newton--Galerkin algorithm is the best mode for the fixed dimensional case, whereas for an adaptive variable dimensional code a special linear convergence mode of the algorithm is definitely preferable. The theoretical results are then illustrated by numerical experiments with a {\sf NEWTON--KASKADE} algorithm.

Description: {\footnotesize In classical Molecular Dynamics a molecular system is modelled by classical Hamiltonian equations of motion. The potential part of the corresponding energy function of the system includes contributions of several types of atomic interaction. Among these, some interactions represent the bond structure of the molecule. Particularly these interactions lead to extremely stiff potentials which force the solution of the equations of motion to oscillate on a very small time scale. There is a strong need for eliminating the smallest time scales because they are a severe restriction for numerical long-term simulations of macromolecules. This leads to the idea of just freezing the high frequency degrees of freedom (bond stretching and bond angles) via increasing the stiffness of the strong part of the potential to infinity. However, the naive way of doing this via holonomic constraints mistakenly ignores the energy contribution of the fast oscillations. The paper presents a mathematically rigorous discussion of the limit situation of infinite stiffness. It is demonstrated that the average of the limit solution indeed obeys a constrained Hamiltonian system but with a {\em corrected soft potential}. An explicit formula for the additive potential correction is given via a careful inspection of the limit energy of the fast oscillations. Unfortunately, the theory is valid only as long as the system does not run into certain resonances of the fast motions. Behind those resonances, there is no unique limit solution but a kind of choatic scenario for which the notion ``Takens chaos'' was coined. For demonstrating the relevance of this observation for MD, the theory is applied to a realistic, but still simple system: a single butan molecule. The appearance of ``Takens chaos'' in smoothed MD is illustrated and the consequences are discussed.}

Description: Recently subdivision techniques have been introduced in the numerical investigation of complicated temporal behavior of dynamical systems. In this article we intertwine the subdivision process with the computation of invariant measures and propose an adaptive scheme for the box refinement which is based on the combination of these methods. Using this new algorithm the numerical effort for the computation of box coverings is in general significantly reduced, and we illustrate this fact by several numerical examples.

Description: In this paper we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms and primal heuristics. We are able to solve all problem instances discussed in literature to optimality, including one to our knowledge not yet solved problem. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called {\em SteinLib} that is accessible via World Wide Web.

Description: In the highly competitive area of telecommunications, cost, quality, and network management are among the most important aspects to be considered when designing a network. We study the problem of dimensioning a telecommunication network that is still operating in case of a failure of a network component. Given a demand between each pair of nodes of a telecommunication network and a finite set of possible capacities for each edge of the 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, even if a network component fails. The routing of the demands must satisfy the following additional restrictions: (a) there is a maximum number of nodes allowed in each path between any pair of nodes (path length restriction), and (b) there is a maximum percentage of the demand between each pair of nodes that can be routed through any network component (diversification restriction). Moreover, the chosen capacities must be such that, for every single node or single edge failure, a certain percentage of the demand between any pair of nodes is reroutable (i.e. it ``survives'' the particular failure). We formulate the problem as a mixed integer linear programming problem and present a cutting plane algorithm as well as several heuristics for its solution. Furthermore, we discuss several ways to implement survivability into a telecommunication network.

Description: A perfect graph is critical if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We investigate the relationship of critically perfect graphs to well-known classes of perfect graphs and study operations preserving critical perfectness.

Description: Designing low cost networks that survive certain failure situations belongs to one of the prime tasks in the telecommunications industry. In this paper we describe a mathematical model combining several aspects of survivability that are elsewhere treated in a hierarchical fashion. We present mathematical investigations of this integrated model, a cutting plane algorithm, as well as several heuristics for its solution. Moreover, we report computational results with real world data. The problem we address is the following. Suppose, between each pair of nodes in a region, a communication demand is given. We want to determine the topology of a telecommunication network connecting the given nodes and to dimension all potential physical links. For each link, the possible capacities are restricted to a given finite set. The capacities must be chosen such that the communication demands are satisfied, even if certain network components fail, and such that the network building costs are as small as possible. Moreover, for each pair of nodes and each failure situation, we want to determine the paths on which the demand between the nodes is routed.

Description: In this note we solve a problem about the rational representability of hypergeometric terms which represent hypergeometric sums. This problem was proposed by Koornwinder in Koornwinder, T. H.: Hypergeometric series evaluation by Zeilberger's algorithm. In: Open Problems, ed. by Walter van Assche. J. of Comput. and Appl. Math.48, 1993, 225--243.

Description: In many applications (hypergeometric-type) special functions like orthogonal polynomials are needed. For example in more than 50 \% of the published solutions for the (application-oriented) questions in the Problems Section'' of SIAM Review special functions occur. In this article the Mathematica package {\tt SpecialFunctions} which can be obtained from the URL {\tt http://www.zib.de/koepf} is introduced. Algorithms to convert between power series representations and their generating functions is the main topic of this package, extending the previous package {\tt PowerSeries}. Moreover the package automatically finds differential and recurrence equations for expressions and for sums (the latter using Zeilberger's algorithm. As an application the fast computation of polynomial approximations of solutions of linear differential equations with polynomial coefficients is presented. This is the asymptotically fastest known algorithm for series computations, and it is much faster than Mathematica's builtin {\tt Series} command if applicable. Many more applications are considered. Finally the package includes implementations supporting the efficient computation of classical continuous and discrete orthogonal polynomials.