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 presents a numerical algorithm for computing the restricted singular value decomposition of matrix triplets (RSVD). It is shown that one can use unitary transformations to separate the regular part from a general matrix triplet. After preprocessing on the regular part, one obtains a matrix triplet consisting of three upper triangular matrices of the same dimensions. The RSVD of this special matrix triplet is computed using the implicit Kogbetliantz technique. The algorithm is well suited for parallel computation. {\bf Keywords:} Restricted singular values, matrix triplets, unitary transformations, implicit Kogbetliantz technique.

Description: The paper presents a detailed analysis of the possible accuracy available for TVD schemes in one dimension with emphasis to the semi-discrete 1-D TVD schemes. The analysis shows that the widely accepted statement [1] of degeneration of accuracy at critical points for TVD schemes should be corrected. We have theorem: TVD schemes using flux limiters $ \varphi $ of the form [1], [2] may be second-order accurate at critical points if $ \varphi $ (3) + $ \varphi $(-1) = 2, but cannot be uniformly second-order accurate in the whole neighborhood of critical point. If $ \varphi $(1) = 1, then the TVD schemes are second-order accurate in the region of smooth solutions sufficiently far from the critical points. Two ways are suggested to improve the accuracy. Numerical example is given. {\bf Keywords:} Semi-discrete schemes, TVD, flux limiter, degeneration of accuracy.

Description: The solidification of an $ N $-component alloy is described by an initial boundary value problem for a system of degenerate parabolic equations modelling heat conduction and mass diffusion. Discretizing implicitly in time and by piecewise linear finite elements in the space variables, at each time step the solution of a system of quasivariational inequalities is required. For the numerical solution of that system, a multi-grid algorithm is developed by making use of game theoretic concepts and duality arguments from convex analysis. Finally, the efficiency of the algorithm is demonstrated by displaying numerical results for a ternary alloy.

Description: The Programmers Manual contains the documentation of the C-KASKADE implementation. KASKADE is an adaptive finite element code (see SC ). The interfaces of all modules are described.

Description: The SPARC processor is a RISC (Reduced Instruction Set Computer) microcomputer, built into the SUN4 workstations. Since RISC processors are very well-suited for LISP processing, the implementation of a dialect of LISP (Portable Standard LISP, PSL) boded well for a great speed-up in comparison with other types of microcomputers. A first approach was done at The RAND Corporation in Santa Monica, which was derived from classical processor types like MC68000 or VAX. At the Konrad- Zuse-Zentrum für Informationstechnik Berlin (ZIB) that initial implementation was redesigned in order to adapt PSL to the specific features of the SPARC processor. The present implementation, in some parts, is very close to Cray PSL version also done in ZIB. Some timing informations are given in the appendix.

Description: Die Parallelisierung eines vorhandenen sequentiellen Programmes erfolgt im allgemeinen in der Weise, daß es auf Grund einer Analyse der Datenabhängigkeiten in mehrere parallel ausführbare Teile zerlegt wird, die ihrerseits sequentiell ablaufen und untereinander Daten austauschen. Eine parallele Programmiersprache sollte diese Vorgehensweise unterstützen, indem sie Sprachmittel zur Verfügung stellt, mittels derer sich die Modularisierung und Kommunikation bequem formulieren läßt. Nun läßt sich prinzipiell jede vorhandene sequentielle Programmiersprache um solche Konstrukte erweitern; günstiger in Hinblick auf die Strukturierung eines parallelen Programmes erscheint es aber möglicherweise, eine solche Programmiersprache zu verwenden, die die genannten Konzepte als elementare zur Verfügung stellt. Dies ist offensichtlich bei objektorientierten Programmiersprachen der Fall. Im vorliegenden Bericht wird an Hand eines Beispiels - TRAPEX -, das in POOL-T implementiert wurde, untersucht, inwieweit eine objektorientierte Sprache zur effektiven Programmierung eines numerischen Algorithmus geeignet ist. {\bf Key Words:} parallele objektorientierte Programmiersprache, Message Passing, Abstract Data Typing, Klassenhierarchi, Modul-Import-Mechanismus, Client/Server-Prinzip, Load Balancing, adaptive numerische Algorithmen, Ordnungs- und Schrittweitensteuerung, Romberg-Quadratur.

Description: Der Bericht ist die Ausarbeitung eines Vortrages, der auf dem Transputer Anwender Treffen (TAT'89) im September 1989 gehalten wurde. Es wird die Parallelisierung und Implementierung eines adaptiven Algorithmus zur numerischen Integration (Romberg Quadratur) beschrieben. Ausgewählte Meßergebnisse sind enthalten. {\bf Keywords:} Numerischer Algorithmus, Romberg Quadratur, paralleler adaptiver Algorithmus, dynamische Lastverteilung und Prozessorzahl, lokaler Speicher, Nearest-Neighbour-Architektur, Transputer, TDS, OCCAM2.

Description: The hierarchical basis preconditioner and the recent preconditioner of BRAMBLE, PASCIAK and XU are derived and analyzed within a joint framework. This discussion elucidates the close relationship between both methods. Special care is devoted to highly nonuniform meshes; our theory is based exclusively on local properties like the shape regularity of the finite elements.

Description: The Users Manual contains an introduction to the usage of the C-KASKADE implementation. KASKADE is an adaptive finite element code (see SC ). The manual includes a description of all commands, a simple recipe to define a new problem by changing the KASKADE source and a complete example.

Description: Das voliegende Skriptum entstand aus einer Vorlesung, die ich im WS 87/88 an der Freien Universität Berlin im Fachbereich Mathematik gehalten habe. Mein ursprüngliches Vorlesungsmanuskript wurde von Herrn F. Bornemann in weiten Teilen überarbeitet, reorganisiert und substantiell ergänzt. Der Inhalt stammt größtenteils aus Originalarbeiten jüngeren Datums. Darüberhinaus finden sich zahlreiche Teile, die aus meiner jahrelangen Beschäftigung mit dem Thema entstanden aber unpubliziert geblieben sind. Das Skriptum erhebt nicht den Anspruch, ein Lehrbuch zu sein. Es war zunächst als Ausarbeitung für meinen studentischen Hörerkreis sowie als internes Arbeitspapier für das ZIB bestimmt. Die Kunde von der bloßen Existenz eines solchen Skriptums hat jedoch zu einer derart regen Nachfrage geführt, daß es hiermit als Technischer Report des ZIB einer breiteren ffentlichkeit zugänglich gemacht werden soll. In der vorliegenden Form richtet es sich in erster Linie an Mathematiker; es soll sich jedoch auch für Naturwissenschaftler und Ingenieure eignen, die sich einen Einblick in den theoretischen und algorithmischen Hintergrund der von ihnen verwendeten wissenschaftlichen Software verschaffen wollen.

Description: Der folgende Bericht ist eine Ergänzung des ZIB Technical Report TR 88-05. Entsprechend wird hier nicht auf die grundsätzlichen Fragen der Parallelisierbarkeit des sequentiellen TRAPEX eingegangen. Diese sind im TR 88-5 erörtert, die dort beschriebenen Algorithmen (vertikale und horizontale Parallelisierung) werden auch für die Transputerarchitektur verwendet. Meßergebnisse sind im letzten Teil angefügt.

Description: Ausgangspunkt bei der Behandlung konvektiv dominierter, elliptischer Probleme sind die bekannten hierarchischen Finite-Element-Methoden für den rein elliptischen Fall. Als stabile Erweiterung des Standard-Galerkin-Verfahrens wird das Stromlinien-Diffusions-Verfahren durch physikalische Überlegungen motiviert und kurz diskutiert. Anschließend zeigen wir, daß diese Methode erst in Verbindung mit einer hier erstmals vorgestellten lokalen Ausrichtung der Kanten wirksam eingesetzt werden kann. Zusammen mit einer ebenfalls neu entwickelten richtungsorientierten Verfeinerungsstrategie erhält man eine erheblich stabilere, genauere und schnellere Auflösung von Grenzschichten als mit herkömmlichen Methoden.

Description: In this paper we consider the problem of reconstructing a multivariate rational function, when only its values at sufficiently many points are known. We use for the reconstruction of bivariate rational functions a bivariate rational interpolation operator investigated by Siemaszko [7] and a new one, compare both by examples in a Computer Algebra system, and present their multivariate generalizations. {\bf Keywords:} Multivariate rational interpolation, reconstruction, symbolic computation.

Description: In this paper we introduce the concept of restricted singular values (RSV's) of matrix triplets. A theorem concerning the RSV's of a general matrix triplet $ (A,B,C) $, where $ A \in C^{m\times n} $, $B\in C^{m\times p} $ and $ C\in C^{q\times n} $, which is called restricted singular value decomposition (RSVD) of matrix triplets, is derived. This result generalizes the wellknown SVD, GSVD and the recently proposed product induced SVD (PSVD). Connection of RSV's with the problem of determination of matrix rank under restricted perturbation is also discussed. {\bf Keywords:} Matrix rank, singular values, generalized singular values, product induced singular values, restricted singular values, matrix decompositions.

Description: We propose an anisotropic refinement strategy which is specially designed for the efficient numerical resolution of internal and boundary layers. This strategy is based on the directed refinement of single triangles together with adaptive multilevel grid orientation. It is demonstrated by several numerical examples that compared to usual methods, the new anisotropic refinement ends up in more stable and more accurate solutions at much less computational cost. {\bf Keywords:} Adaptive finite elements, directed refinement, adaptive grid orientation, convection diffusion equation, internal and boundary layers.

Description: Modeling of free radical polymerization leads to very large and usually stiff systems of ordinary differential equations which cannot be solved directly in an efficient way. This paper presents the application of a new approach called discrete Galerkin method to a realistic example - the polymerization of methyl methacrylate(MMA). The method is characterized by a Galerkin approximation on the basis of orthogonal polynomials of a discrete variable which represents the polymer degree. It allows the efficient computation of solutions of complete kinetic schemes with time- or moment-dependent reaction coefficients by reducing the complexity to a few differential equations. The approximation error can be controlled by an error estimation. In the case of MMA polymerization a reduction of computational effort by a factor of about 25 compared to a standard method can be obtained for the quasi-steady-state approximation of the model. In addition solutions of the instationary kinetic scheme can be easily computed.

Description: In this paper we present the MmB schemes, which preserve the local maximum and minimum bounds of the initial data in the smallest union of mesh elements of previous time step containing the domain of dependence of the solution on the mesh element with center at point $ P $\ under consideration. In 1-D, the MmB schemes are almost identical with TVD schemes. As well-known, there is no second-order TVD scheme in 2-D, nevertheless, we present here two classes of 2-D second-order accurate MmB-schemes. It is proved that 1-D discrete MmB (or TVD) and 1-D semi-discrete TVD schemes may have second-order accuracy at (nonsonic) critical points, but cannot be of uniformly second-order accurate in the whole neighborhood of the critical points. New accurate high resolution flux limiters are suggested. Numerical results for 1-D and 2-D test problems are given. {\bf Keywords:} Difference scheme, TVD, MmB, flux limiter.

Description: A new approach for the discretisation of hyperbolic conservation laws via a finite element method is developed and analysed. Appropriate forms of the Eulers equation of gas dynamic are considered to employ the algorithm in a reasonable way for this system of nonlinear equations. Both mathematical and physical stability results are obtained. A main part of the paper is devoted to the convergence proof with energy methods under strong regularity of the solution of a scalar nonlinear conservation law. Some hints on the implementation and numerical results for the calculation of transonic gasflow through a Laval nozzle are given. The necessary amount of numerical work is compared to an established finite difference method and the efficiency of the algorithm is shown. A survey on recent literature about finite element methods for hyperbolic problem is included.

Description: The present paper developes an adaptive multilevel approach for parabolic PDE's - as a first step, for one linear scalar equation. Full adaptivity of the algorithm is conceptually realized by simultaneous multilevel discretization in both time and space. Thus the approach combines multilevel time discretization, better known as extrapolation methods, and multilevel finite element space discretization such as the hierarchical basis method. The algorithmic approach is theoretically backed by careful application of fundamental results from semigroup theory. These results help to establish the existence of asymptotic expansions (in terms of time-steps) in Hilbert space. Finite element approximation then leads to perturbed expansions, whose perturbations, however, can be pushed below a necessary level by means of an adaptive grid control. The arising space grids are not required to satisfy any quasi- uniformity assumption. Even though the theoretical presentation is independent of space dimension details of the algorithm and numerical examples are given for the 1-D case only. For the 1-D elliptic solver, which is used, an error estimator is established, which works uniformly well for a family of elliptic problems. The numerical results clearly show the significant perspectives opened by the new algorithmic approach.