Bibliothek

Beschreibung: Im Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) wird die verteilte Suche in heterogenen Datenbank mit einer integrierten Dublettenerkennung und -zusammenfuehrung realisiert. Beschrieben werden die einzelnen attributspezifischen Normierungsschritte, die dem eigentlichen Vergleich (MATCH) zweier Datensätze vorangehen.

Beschreibung: In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The {\em quantum-classical Liouville equation} (QCL) describes most atoms of the molecular system under consideration by means of classical phase space density but an important, small portion of the system by means of quantum mechanics. The QCL is derived from the full quantum dynamical (QD) description by applying the Wigner transform to the classical part'' of the system only. We discuss the conditions under which the QCL model approximates the full QD evolution of the system. First, analysis of the asymptotic properties of the Wigner transform shows that solving the QCL yields a first order approximation of full quantum dynamics. Second, we discuss the adiabatic limit of the QCL. This discussion shows that the QCL solutions may be interpretated as classical phase space densities, at least near the adiabatic limit. Third, it is demonstrated that the QCL yields good approximations of {\em non-adiabatic quantum effects,} especially near so-called {\em avoided crossings} where most quantum-classical models fail.

Beschreibung: Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.

Beschreibung: Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg!

Beschreibung: Mean-variance portfolio analysis provided the first quantitative treatment of the tradeoff between profit and risk. We investigate in detail the interplay between objective and constraints in a number of single-period variants, including semi-variance models. Particular emphasis is laid on avoiding the penalization of overperformance. The results are then used as building blocks in the development and theoretical analysis of multi-period models based on scenario trees. A key property is the possibility to remove surplus money in future decisions, yielding approximate downside risk minimization.

Beschreibung: The paper compares computational aspects of four approaches to compute conservation laws of single differential equations or systems of them, ODEs and PDEs. The only restriction, required by two of the four corresponding computer algebra programs, is that each DE has to be solvable for a leading derivative. Extra constraints may be given. Examples of new conservation laws include non-polynomial expressions, an explicit variable dependence and conservation laws involving arbitrary functions. Examples involve the following equations: Ito, Liouville, Burgers, Kadomtsev-Petviashvili, Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney.

Beschreibung: Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of $T$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted.

Beschreibung: In KOBV we offer the user an efficient tool for searching regional and worldwide accessible library catalogues (KOBV search engine). Search is performed by a distributed Z39.50 retrieval and an index based quicksearch. Due to the number of catalogues, result sets may contain a significant amount of duplicate records. Therefore we integrate a de-duplication procedure into KOBV search engine. It is part of the distributed search and the KOBV quicksearch as well. Main goals are the presentation of uniform retrieval results, the preservation of retrieval quality and cutting off redundant information. At least we keep an eye on efficiency. De-duplication is fully parametrizable, so that settings can be changed easily on line.

Beschreibung: A cascadic multigrid (CMG) method for elliptic problems with strong material jumps is proposed and analyzed. Non--matching grids at interfaces between subdomains are allowed and treated by mortar elements. The arising saddle point problems are solved by a subspace confined conjugate gradient method as smoother for the CMG. Details of algorithmic realization including adaptivity are elaborated. Numerical results illustrate the efficiency of this CMG algorithm.

Beschreibung: In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.

Beschreibung: We present an algebraic multigrid preconditioner which uses only the graphs of system matrices. Some elementary coarsening rules are stated, from which an advancing front algorithm for the selection of coarse grid nodes is derived. This technique can be applied to linear Lagrange-type finite element discretizations; for higher-order elements an extension of the multigrid algorithm is provided. Both two- and three-dimensional second order elliptic problems can be handled. Numerical experiments show that the resulting convergence acceleration is comparable to classical geometric multigrid.

Beschreibung: \\{\bf Zusammenfassung: }Diese Diplomarbeit beschreibt ein verteiltes Bibliotheks-Informationssystem für bibliographische Datenbanken im Internet. Der Name des Systems ist ZACK. Der Benutzer kann mit ZACK in einer oder mehreren bibliographischen Datenbanken nach einem Dokument suchen und die Treffer in die eigene lokale Datenbank übernehmen. Mit der Übernahme der Datensätze aus einer fremden Datenbank wird die Erfassung neuer Dokumente wesentlich erleichtert, da die Eigenkatalogisierung auf ein Minimum beschränkt werden kann. Es wird doppelte Arbeit vermieden, und die Datensätze haben eine gleichbleibend hohe Qualität. Bei der verteilten Suche mit ZACK wird parallel in mehreren Datenbanken gesucht. Dubletten werden als solche erkannt. Dem Benutzer wird eine übersichtliche Kurztrefferliste ohne doppelte Einträge angeboten. Er kann dann selbst entscheiden, aus welcher Datenbank er die Datensätze übernimmt. Die verteilte Suche hat in der Praxis eine deutlich bessere Trefferquote gebracht als die Suche in nur einer Datenbank. Dabei bleibt die Antwortzeit in einem für den Benutzer akzeptablen Rahmen. Die Kurztrefferliste wird durch die Dublettenkontrolle kürzer und übersichtlicher. English Title: A Distributed Library Information System on the Basis of the Z39.50 Protocol This diploma thesis desribes a distributed library information system for bibliographic databases in the Internet. The name of the system is ZACK. With ZACK the user is able to search for a particular document in several databases and to include the matches in his/her own local database. The inclusion of data records from an external database makes the capture of new documents much easier, as internal cataloging is reduced to a minimum. Double work is eliminated and a continuously high quality of data record is ensured. The distributed search by means of ZACK is carried out in several databases in parallel. Duplicates are recognized; and a short list of matches without double entries is offered. The user can then decide for himself from which database to include data records. In practice, a distributed search has produced far better results than the search in one particular database. Response times are within an acceptable limit for the user. The short list of hits is made clearer and more concise by the duplicate check. The diploma thesis is also available in PDF, HTML, and ASCII format: http://wolfram.schneider.org/lv/diplom/ .

Beschreibung: Flavone and the flavylium ion have been studied at Hartree-Fock, M{\o}ller-Plesset and B3LYP hybrid density functional level to determine the structures and barriers to internal rotation. Both molecules have a high perpendicular barrier about the single bond connecting the phenyl ring with the benzopyrone and benzopyrylium ring, respectively. In contrast to biphenyl both molecules have low coplanar barriers. B3LYP overestimates the perpendicular barrier heights compared to other methods. The dependence of the population and orbital energies on the torsion has been investigated and the structures of both flavonoids have been estimated by means of a reaction field model.

Beschreibung: Das Math-Net ist ein verteiltes Informationssystem f"ur die Mathematik. Es basiert auf den lokalen Informationsangeboten der Fachbereiche, die im Math-Net integriert, nutzerfreundlich aufbereitet und zug"anglich gemacht werden sollen. Das Math-Net ist durch die freiwillige Mitarbeit weiterer Institutionen in Deutschland zu einem flächendeckenden Dienst ausgebaut worden. Die am Projekt beteiligten Institutionen haben die mathematischen Institutionen in ihrer Region beim Aufbau eines qualitativ hochwertigen lokalen Informationsangebotes unterstützt und die Integration der lokalen Informationsangebote in das Math-Net koordiniert.

Beschreibung: The function of many important biomolecules is related to their dynamic properties and their ability to switch between different {\em conformations}, which are understood as {\em almost invariant} or {\em metastable} subsets of the positional state space of the system. Recently, the present authors and their coworkers presented a novel algorithmic scheme for the direct numerical determination of such metastable subsets and the transition probability between them. Although being different in most aspects, this method exploits the same basic idea as {\sc Dellnitz} and {\sc Junge} in their approach to almost invariance in discrete dynamical systems: the almost invariant sets are computed via certain eigenvectors of the Markov operators associated with the dynamical behavior. In the present article we analyze the application of this approach to (high--friction) Langevin models describing the dynamical behavior of molecular systems coupled to a heat bath. We will see that this can be related to theoretical results for (symmetric) semigroups of Markov operators going back to {\sc Davies}. We concentrate on a comparison of our approach in respect to random perturbations of dynamical systems.

Beschreibung: An introductory chapter on Groebner bases is given which also includes new results on the detection of Groebner bases for sparse polynomial systems. Algorithms for the computation of invariants and equivariants for finite groups, compact Lie groups and algebraic groups are presented and efficient implementation and time comparision are discussed. This chapter also inlcudes improvements of the computation of Noether normalisation and Stanley decomposition. These results are applied in symmetric bifurcation theory and equivariant dynamics. As preparation of the investigation of the orbit space reduction three methods are compared for solving symmetric polynomial systems exactly. The method of orbit space reduction is improved by using the Cohen-Macaulayness of the invariant ring and nested Noether normalization. Finally this is applied for a case of mode interaction in the Taylor-Couette problem.

Beschreibung: A class of sparse polynomial systems is investigated which is defined by a weighted directed graph and a weighted bipartite graph. They arise in the model of mass action kinetics for chemical reaction systems. In this application the number of real positive solutions within a certain affine subspace is of particular interest. We show that the simplest cases are equivalent to binomial systems while in general the solution structure is highly determined by the properties of the two graphs. First we recall results by Feinberg and give rigorous proofs. Secondly, we explain how the graphs determine the Newton polytopes of the system of sparse polynomials and thus determine the solution structure. The results on positive solutions from real algebraic geometry are applied to this particular situation. Examples illustrate the theoretical results.

Beschreibung: We study the improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering. As an indicator for decorrelation we use the topological charge.

Beschreibung: We describe a novel method for continuously transforming two triangulated models of arbitrary topology into each other. Equal global topology for both objects is assumed, extensions for genus changes during metamorphosis are provided. The proposed method addresses the major challenge in 3D metamorphosis, namely specifying the morphing process intuitively, with minimal user interaction and sufficient detail. Corresponding regions and point features are interactively identified. These regions are parametrized automatically and consistently, providing a basis for smooth interpolation. Utilizing suitable 3D interaction techniques a simple and intuitive control over the whole morphing process is offered.

Beschreibung: Our focus is on Maxwell's equations in the low frequency range; two specific applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the finite element approximation we choose N\'{e}d\'{e}lec's $H(curl)$-conforming edge elements of the lowest order. For the solution of the arising linear equation systems we devise an algebraic multigrid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally, we have to cope with the kernel of the $curl$-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efficacy of the proposed algorithms.

Beschreibung: Large scale simulations running in metacomputing environments face the problem of efficient file I/O. For efficiency it is desirable to write data locally, distributed across the computing environment, and then to minimize data transfer, i.e.\ reduce remote file access. Both aspects require I/O approaches which differ from existing paradigms. For the data output of distributed simulations, one wants to use fast local parallel I/O for all participating nodes, producing a single distributed logical file, while keeping changes to the simulation code as small as possible. For reading the data file as in postprocessing and file based visualization, one wants to have efficient partial access to remote and distributed files, using a global naming scheme and efficient data caching, and again keeping the changes to the postprocessing code small. However, all available software solutions require the entire data to be staged locally (involving possible data recombination and conversion), or suffer from the performance problems of remote or distributed file systems. In this paper we show how to interface the HDF5 I/O library via its flexible Virtual File Driver layer to the Globus Data Grid. We show, that combining these two toolkits in a suitable way provides us with a new I/O framework, which allows efficient, secure, distributed and parallel file I/O in a metacomputing environment.

Beschreibung: Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node $i$ to node $j$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for $m\ge 3$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for $m\ge 2$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for $m\ge 2$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.

Beschreibung: Due to its many applications in control theory, robust optimization, combinatorial optimization and eigenvalue optimization, semidefinite programming had been in wide spread use even before the development of efficient algorithms brought it into the realm of tractability. Today it is one of the basic modeling and optimization tools along with linear and quadratic programming. Our survey is an introduction to semidefinite programming, its duality and complexity theory, its applications and algorithms.

Beschreibung: Im Herbst 1999 ging der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) in Routinebetrieb. In technischer Hinsicht setzt der KOBV auf ein neuartiges, zukunftsweisendes Verbundkonzept, in dem die zentrale Datenbank mit dem Verbundkatalog ersetzt wird durch verteilte Datenbanken und lokale Kataloge, die durch das Netz (Internet) miteinander verbunden sind. Die zentrale Recherchefunktion wird ersetzt durch die KOBV-Suchmaschine. Beschrieben werden die Hintergründe, die zu diesem Konzept geführt haben, die Kriterien, die die Architekturentscheidungen der Software bestimmt haben, sowie die einzelnen realisierten Komponenten.

Beschreibung: Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d 〈 d' 〈 n$.

Beschreibung: In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.

Beschreibung: It is well known that the following class of systems of evolution equations \begin{eqnarray} \label{nsgen} \cases{ u_{t}=u_{xx}+F(u,v,u_x,v_x),\cr v_{t}=-v_{xx}+G(u,v,u_x,v_x),\cr} \end{eqnarray} is very rich in integrable cases. The complete classification problem is very difficult. Here we consider only the most interesting (from our opinion) subclass of systems (1). Namely, we consider equations linear in all derivatives of the form \begin{eqnarray} \label{kvazgen} \cases{ u_t = u_{xx} + A_{1}(u,v) u_x + A_{2}(u,v) v_x + A_{0}(u,v)\cr v_t = - v_{xx} + B_{1}(u,v) v_x + B_{2}(u,v) u_x + B_{0}(u,v). \cr} \end{eqnarray} without any restrictions on the functions $A_{i}(u,v), B_{i}(u,v)$.

Beschreibung: In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.

Beschreibung: In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5.

Beschreibung: A new seasonal energy storage for thermal solar systems has been developed on the basis of an adsorption-desorption process. Design and optimization of this storage will be supported by numerical simulations of heat and mass transfer with KARDOS. This paper focuses on the unsteady heat transfer during the major operating step of energetic discharge of the storage, which is characterized by conductive heat transfer in the fixed bed and a strong heat source caused by the adsorption enthalpy. Results are interpreted concerning the influence of variations in the parameter set. The method of implementation of the differential equation will be shown as well as the post-processing and gridwriting programs.

Beschreibung: In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.

Beschreibung: The function of many important biomolecules comes from their dynamic properties and their ability to switch between different {\em conformations}. In a conformation, the large scale geometric structure of the molecule is understood to be conserved, whereas on smaller scales the system may well rotate, oscillate or fluctuate. In a recent article [J. Comp. Phys., 151,1 (1999)], the present author and coworkers demonstrated that (a) conformations can be understood as almost invariant sets of some Markov chain being defined via the Hamiltonian system governing the molecular dynamics and that (b) these sets can efficiently be computed via eigenvectors of the corresponding Markov operator. The persent manuscript reviews the mathematical modelling steps behind the novel concept, includes a rigorous analytical justification of this approach and especially of the numerical details of the algorithm, and illustrates its performance when applied to realistic molecular systems.

Beschreibung: Der neue ''verteilte'' Bibliotheksverbund KOBV erfordert neue Arbeitsweisen und neue Formen der Zusammenarbeit der Bibliotheken untereinander. Im KOBV wird es keine zentrale Erschließung geben, sondern die Erschließung wird lokal, in den Bibliotheken durchgeführt. Entsprechend ihren Nutzerbedürfnissen bestimmen die Bibliotheken die Erschließungsart, den Erschließungsumfang und die Erschließungstiefe selbst. Als gemeinsamer regionaler Standard wird lediglich ein ''Mindeststandard'' auf der Basis von RAK-WB definiert. Dieser Gemeinsame KOBV-Standard berücksichtigt vor allem suchrelevante Elemente, um den Nutzern im KOBV möglichst einheitliche Sucheinstiege zu bieten. Der Gemeinsame KOBV-Standard wird in diesem Papier vorgestellt.

Beschreibung: Die KOBV-Suchmaschine verarbeitet Daten im bibliographischen Datenformat MAB2 (Maschinelles Austauschformat für Bibliotheken, Ausgabe 2), das in deutschsprachigen Ländern angewandt wird. Im MAB2-Format sind für mehrbändige begrenzte Werke und fortlaufende Sammelwerke hierarchische Strukturen realisiert - mit bis zu drei Hierarchiestufen und unterschiedlichem Aufbau, je nachdem, ob es sich um ein begrenztes Werk oder um ein Werk ohne geplanten Abschluß handelt. Jede hierarchische Stufe entspricht einem Datensatz, die zusammengehörigen Datensätze sind miteinander verknüpft. Inhaltlich enthält eine Stufe oft nur Teilinformationen des Werkes; erst die Stufen zusammen ergeben die vollständige Information. In der KOBV-Suchmaschine werden Dokumente aus verschiedenen Bibliotheken zusammengeführt. Hierarchische Strukturen potenzieren gewissermaßen die mit der Dublettenbehandlung (Match- und Merge-Verfahren) verbundene Problematik: Es müssen nicht nur Datensätze aus verschiedenen Bibliotheken zusammengeführt werden, sondern darüber hinaus die zusammengehörigen Datensätze der unterschiedlichen Hierarchiestufen. Der Artikel enthält eine ausführliche Analyse der in MAB2 vorkommenden hierarchischen Strukturen, beschreibt die Anforderungen für die Lieferung hierarchischer Datensätze aus den lokalen Systemen und stellt das Verfahren vor, wie in der KOBV-Suchmaschine mit diesen hierarchischen Datenstrukturen bei der Dublettenbehandlung umgegangen wird. Anhand von Fallbeispielen wird die Problematik der Verknüpfung zusammengeführter h-Sätze erörtert. Die KOBV-Suchmaschine verarbeitet Daten im bibliographischen Datenformat MAB2 (Maschinelles Austauschformat für Bibliotheken, Ausgabe 2), das in deutschsprachigen Ländern angewandt wird. Im MAB2-Format sind für mehrbändige begrenzte Werke und fortlaufende Sammelwerke hierarchische Strukturen realisiert - mit bis zu drei Hierarchiestufen und unterschiedlichem Aufbau, je nachdem, ob es sich um ein begrenztes Werk oder um ein Werk ohne geplanten Abschluß handelt. Jede hierarchische Stufe entspricht einem Datensatz, die zusammengehörigen Datensätze sind miteinander verknüpft. Inhaltlich enthält eine Stufe oft nur Teilinformationen des Werkes; erst die Stufen zusammen ergeben die vollständige Information. In der KOBV-Suchmaschine werden Dokumente aus verschiedenen Bibliotheken zusammengeführt. Hierarchische Strukturen potenzieren gewissermaßen die mit der Dublettenbehandlung (Match- und Merge-Verfahren) verbundene Problematik: Es müssen nicht nur Datensätze aus verschiedenen Bibliotheken zusammengeführt werden, sondern darüber hinaus die zusammengehörigen Datensätze der unterschiedlichen Hierarchiestufen. Der Artikel enthält eine ausführliche Analyse der in MAB2 vorkommenden hierarchischen Strukturen, beschreibt die Anforderungen für die Lieferung hierarchischer Datensätze aus den lokalen Systemen und stellt das Verfahren vor, wie in der KOBV-Suchmaschine mit diesen hierarchischen Datenstrukturen bei der Dublettenbehandlung umgegangen wird. Anhand von Fallbeispielen wird die Problematik der Verknüpfung zusammengeführter h-Sätze erörtert.

Beschreibung: This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.

Beschreibung: Die Recherche über die KOBV-Suchmaschine liefert Datensätze aus unterschiedlichen Bibliotheken. Damit der Nutzer nicht viele, unter Umständen lange Listen für jede Bibliothek durchblättern muss werden die Datensätze in der KOBV-Suchmaschine einer Dublettenbehandlung (Match- und Merge-Verfahren) unterzogen. Ziel dieses Verfahrens ist es, dem Nutzer möglichst nur einen einzigen Datensatz mit allen zugehörigen Bestandsnachweisen aus den Bibliotheken anzuzeigen. In dem vorliegenden Papier steht das Match-Verfahren, das von der KOBV-Projektgruppe eigens für den Einsatz in der KOBV-Suchmaschine entwickelt wurde, im Vordergrund. Das Merge-Verfahren, das auf Konzepte von Ex Libris zurückgeht, ist lediglich am Rande erwähnt. Ziel bei der Entwicklung des Match- und Merge-Verfahrens war es, in der KOBV-Suchmaschine ein Verfahren zu implementieren, das vollkommen automatisiert, ohne Zuhilfenahme manueller und intellektueller Eingriffe, abläuft. In diesem Papier sind die Grundlagen zum Match- und Merge-Verfahren in der KOBV-Suchmaschine zusammengefaßt. Zunächst wird definiert, was unter einer Dublette überhaupt zu verstehen ist. Die Begriffe Dokument und Werk werden analysiert, die wesentlich sind für die Entscheidung, welche Datensätze in der KOBV-Suchmaschine letztendlich zusammengeführt werden. Anhand umfassender Literaturrecherchen werden die zur Dublettenbehandlung herangezogenen bibliographischen Beschreibungselemente (Attribute) in verschiedenen MARC- und MAB-Datenbanken ermittelt und grundsätzliche Probleme beim Erkennen dubletter bibliographischer Datensätze aufgezeigt. Schließlich werden Verfahren vorgestellt und diskutiert, wie die Attribute in das Match- und Merge-Verfahren eingebunden werden: bei nur einer Gewichtung (positiver Wert) und bei zwei Gewichtungen (positiver und negativer Wert). Auf dieser Basis werden Tabellen mit Werten für zwei unterschiedliche Gewichtungsverfahren in der KOBV-Suchmaschine entwickelt, die als Ausgangswerte für erste Testverfahren in den Match- und Merge-Algorithmus in der KOBV-Suchmaschine implementiert werden.

Beschreibung: Abstract-Sammlung zum gleichnamigen Workshop am ZIB vom 19.--20. Mai 1999

Beschreibung: This monograph has been written to illustrate the interlocking of theory, algorithm, and application in developing solution techniques for complex PDE systems. A deep theoretical understanding is necessary to produce a powerful idea leading to a successful algorithm. Efficient and robust implementation is the key to make the algorithm perform satisfactorily. The extra insight obtained by solving real--life problems brings out the structure of the method more clearly and suggests often ways to improve the numerical algorithm. It is my intention to impart the beauty and complexity found in both the theoretical investigation of the adaptive algorithm proposed here, i.e., the coupling of Rosenbrock methods in time and multilevel finite elements in space, and its realization. I hope that this method will find many more interesting applications.

Beschreibung: Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions.

Beschreibung: Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) und das Rechenzentrum der Universität Rostock, beide Einrichtungen betreiben massiv-parallele Rechner vom Typ CRAY T3E, haben sich an Hand einer Anwendung aus dem Bereich der Botanik mit den Möglichkeiten der Verteilung auf zwei Parallelrechner, gekoppelt nur über das Breitband-Wissenschaftsnetz des Deutschen Forschungsnetzes, vertraut gemacht. Das Projekt besteht aus zwei Teilen. Im ersten Teil wird ausführlich das zwischen den Rechnern liegende Netz und die Ergebnisse einer Performanceanalyse dieses Netzes dokumentiert. Der zweite Teil beschreibt die Anwendung "Simulation des Wachstums von Pflanzen"' sowie die Ergebnisse der Verteilung dieser Anwendung auf beide Rechner. \begin{center} \bf{Abstract} \end{center} The "'Konrad-Zuse-Zentrum für Informationstechnik Berlin"' (ZIB) and the Computing Centre of the University of Rostock operate high-performance computers of type CRAY T3E. In this project an application from the area of the botany is distributed on two parallel computers, only coupled through the Broadband Science Network of the German Research Network (DFN). This project consists of two parts. In the first part the network which is situated between the computers and the results of a performance analysis is documented in detail. The second part describes the application "'Simulation of the growth of plants"' as well as the results of the distribution of this application to both computers.

Beschreibung: The method of symmetry adapted wavepackets (SAWP) to solve the time-dependent Schrödinger equation for a highly symmetric potential energy surface is introduced. The angular dependence of a quantum-mechanical wavepackets is expanded in spherical harmonics where the number of close-coupled equations for the corresponding radial functions can be efficiently reduced by symmetry adaption of the rotational basis using the SWAP approach. Various techniques to generate symmetry adapted spherical harmonics (SASHs) for the point groups of highest symmetry (octahedral, icosahedral) are discussed. The standard projection operator technique involves the use of Wigner rotation matrices. Two methods to circumvent numerical instabilities occuring for large azimuthal quantum numbers are suggested. The first is based on a numerical scheme which employs Gaussian integrations yielding exact and stable results. The second is a recursive algorithm to generate higher order SASHs accurately and efficiently from lower order ones. The paper gives a complete set of ``seed functions'' generated by projection techniques which can be used obtain SASHs for all irreducible representations of the octahedral and icosahedral point groups recursively.

Beschreibung: The article surveys the development of novel mathematical concepts and algorithmic approaches based thereon in view of their possible applicability to biomolecular design. Both a first deterministic approach, based on the Frobenius-Perron operator corresponding to the flow of the Hamiltonian dynamics, and later stochastic approaches, based on a spatial Markov operator or on Langevin dynamics, can be subsumed under the unified mathematical roof of the transfer operator approach to effective dynamics of molecular systems. The key idea of constructing specific transfer operators especially taylored for the purpose of conformational dynamics appears as the red line throughout the paper. Different steps of the algorithm are exemplified by a trinucleotide molecular system as a small representative of possible RNA drug molecules.

Beschreibung: In this paper we discuss several ways to visualize stationary and non-stationary quantum mechanical systems. We demonstrate an approach for the quantitative interpretation of probability density isovalues which yields a reasonable correlation between isosurfaces for different timesteps. As an intuitive quantity for visualizing the momentum of a quantum system we propose the probability flow density which can be treated by vector field visualization techniques. Finally, we discuss the visualization of non-stationary systems by a sequence of single timestep images.

Beschreibung: One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included.

Beschreibung: The photoassociation process shows strong dependence on the temporal duration of the electromagnetic field pulses and their frequencies. This dependence is investigated using quantum mechanical simulations that include all ranges of impact parameters and contributions from bound-to-bound transitions. The photoassociation yield of mercury atoms to produce excimer dimers is enhanced for short (ps) and for ultrashort (fs) pulse durations. Ultrashort laser pulses effectively overlap the entire range of free-to-bound transition, therefore achieving a maximum probability. Short pulses show a maximum in the photoassociation yield when their carrier frequency overlaps a particular free-to-bound spectroscopic resonance. Implications of these calculations on efforts to control bimolecular reactions are discussed.

Beschreibung: For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis.

Beschreibung: Auf dem 89. Deutschen Bibliothekartag, der vom 25. bis 29. Mai 1999 in Freiburg (Breisgau) stattgefunden hat, wurde der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) zum ersten Mal der großen bibliothekarischen Öffentlichkeit vorgestellt. Am KOBV-Stand, der im Rahmen des gemeinsamen Standes der Arbeitsgemeinschaft der Verbundsysteme organisiert wurde, führte die KOBV-Projektgruppe Funktionalitäten der KOBV-Suchmaschine vor. In der Vortragsreihe zum Themenkreis XI "Neue Entwicklungen in den Verbund- und Lokalsystemen", die unter Mitwirkung der Arbeitsgemeinschaft der Verbundsysteme veranstaltet wurde, war der KOBV mit einem eigenen Vortrag vertreten: "Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) - Ein innovatives Verbundkonzept für die Region". In dem Vortrag hat die Verfasserin einen umfassenden Überblick über das KOBV-Projekt und den bisherigen Projektverlauf gegeben, die Projektziele und den politischen Rahmen erörtert sowie die KOBV-Suchmaschine, das technische Kernstück des neuen Verbundes, vorgestellt. Der hier vorliegende Text ist die schriftlich ausgearbeitete Fassung dieses Vortrages.

Beschreibung: This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.

Beschreibung: The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied. As an indicator for decorrelation the topological charge is used.

Beschreibung: Im Herbst 1999 nimmt die KOBV-Suchmaschine, das technische "Herzstück" des KOBV, den Routinebetrieb auf. Nach einer kurzen Einführung in die politischen und rechtlichen Grundlagen des KOBV-Projektes werden in diesem Aufsatz die Funktionalitäten der KOBV-Suchmaschine, ihre Leistungen für Bibliotheksbenutzer und Bibliothekare, vorgestellt. Der Aufsatz schließt mit einem Überblick über den bisherigen Projektverlauf und der Erläuterung der wichtigsten Prinzipien des KOBV - Offenheit, Dezentralität und Heterogenität.

Beschreibung: This series of lectures has been given to a class of mathematics postdocs at a European summer school on Computational Mathematics Driven by Industrial Applications in Martina Franca, Italy (organized by CIME). It deals with a variety of challenging real life problems selected from clinical cancer therapy, communication technology, polymer production, and pharmaceutical drug design. All of these problems from rather diverse application areas share two common features: (a) they have been modelled by various differential equations -- elliptic, parabolic, or Schrödinger--type partial differential equations, countable ordinary diffential equations, or Hamiltonian systems, (b) their numerical solution has turned out to be real challenge to computational mathematics.

Beschreibung: Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. Encouraging preliminary computational results are reported.

Beschreibung: The C++ standard template library has many useful containers for data. The standard library includes two adpators, queue, and stack. The authors have extended this model along the lines of relational database semantics. Sometimes the analogy is striking, and we will point it out occasionally. An adaptor allows the standard algorithms to be used on a subset or modification of the data without having to copy the data elements into a new container. The authors provide many useful adaptors which can be used together to produce interesting views of data in a container.

Beschreibung: This report describes the development of an experimental service for picture-based document retrieval for the Electronic Visualization Library (EVlib). The EVlib is a digital library for scientific visualization, established at the Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB). The picture-based retrieval service allows users to look for documents by describing the pictures they contain. This query method was developed based on the assumption that (1) pictures often represent relevant parts of the contents of a document, and (2) pictures are often remembered well. A picture-based approach provides a new quality of accessing and exploring scientific literature. Motivation, concepts and realization of our service are outlined. Results of a user test are presented, too. The results indicate that this service can be used for searching and browsing the document collection in principle. On the other hand, problems were detected which can give fruitful hints for future work concerning document and image retrieval.

Beschreibung: In this paper, we generalize the nonlocal discrete transparent boundary condition introduced by Schmidt and Deuflhard {[}Comp. Math. Appl. 29 (1995) 53-76{]} and Schmidt and Yevick {[}J. Comput. Phys. 134 (1997) 96-107{]} to propagation methods based on arbitrary Pad\'e approximations to the two-dimensional one-way Helmholtz equation. Our approach leads to a recursive formula for the coefficients appearing in the nonlocal condition which then yields an unconditionally stable propagation method.

Beschreibung: We present nonlocal discrete transparent boundary conditions for a fourth-order wide-angle approximation of the two-dimensional Helmholtz equation. The boundary conditions are exact in the sense that they supply the same discrete solution on a bounded interior domain as would be obtained by considering the problem on the entire unbounded domain with zero boundary conditions at infinity. The proposed algorithm results in an unconditionally stable propagation method. Numerical examples from optics illustrate the efficiency of our approach.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Beschreibung: {\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.}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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