Bibliothek

Beschreibung: Zeitschriften und andere Medien werden in wachsendem Maße elektronisch publiziert. Hier entsteht für die Bibliotheken, welche diese Online-Publikationen ihren Lesern zur Verfügung stellen, ein neuer Bereich der Informationsvermittlung. Mit dem aufkommenden Standard der OpenURL ergeben sich neue Möglichkeiten, dem Benutzer weiterführende Links und Dienste anzubieten. Das Document-Linking-System SFX der Firma Ex Libris ist die erste und bekannteste Anwendung, die ein Managementsystem fr die Auswertung der OpenURL implementiert. Im Rahmen eines Projektes hat die Zentrale des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) eine Evaluation von SFX durchgeführt. Als Ergebnis der Evaluation sollten Einsatzmöglichkeiten von SFX für die KOBV-Suchmaschine und in den lokalen Bibliothekssystemen und Informationsportalen aufgezeigt werden. Im Verlauf des Projektes hat sich das Produkt SFX als eine stabile Anwendung erwiesen, die dem Benutzer interessante zusätzliche Dienste bieten kann.

Beschreibung: In this work we present an approach for the sensitivity analysis of linearly-implicit differential-algebraic equation systems. Solutions for both, states and sensitivities are obtained by applying an extrapolated linearly implicit Euler discretization scheme. This approach is compared to the widely used sensitivity extensions of multi-step BDF methods by means of case studies. Especially, we point out the benefit of this method in the context of dynamic optimization using the sequential approach.

Beschreibung: Decomposition of the high dimensional conformational space of bio-molecules into metastable subsets is used for data reduction of long molecular trajectories in order to facilitate chemical analysis and to improve convergence of simulations within these subsets. The metastability is identified by the Perron-cluster cluster analysis of a Markov process that generates the thermodynamic distribution. A necessary prerequisite of this analysis is the discretization of the conformational space. A combinatorial approach via discretization of each degree of freedom will end in the so called ''curse of dimension''. In the following paper we analyze Hybrid Monte Carlo simulations of small, drug-like biomolecules and focus on the dihedral degrees of freedom as indicators of conformational changes. To avoid the ''curse of dimension'', the projection of the underlying Markov operator on each dihedral is analyzed according to its metastability. In each decomposition step of a recursive procedure, those significant dihedrals, which indicate high metastability, are used for further decomposition. The procedure is introduced as part of a hierarchical protocol of simulations at different temperatures. The convergence of simulations within metastable subsets is used as an ''a posteriori'' criterion for a successful identification of metastability. All results are presented with the visualization program AmiraMol.

Beschreibung: The adaptive finite element code {\sc Kardos} solves nonlinear parabolic systems of partial differential equations. It is applied to a wide range of problems from physics, chemistry, and engineering in one, two, or three space dimensions. The implementation is based on the programming language C. Adaptive finite element techniques are employed to provide solvers of optimal complexity. This implies a posteriori error estimation, local mesh refinement, and preconditioning of linear systems. Linearely implicit time integrators of {\em Rosenbrock} type allow for controlling the time steps adaptively and for solving nonlinear problems without using {\em Newton's} iterations. The program has proved to be robust and reliable. The user's guide explains all details a user of {\sc Kardos} has to consider: the description of the partial differential equations with their boundary and initial conditions, the triangulation of the domain, and the setting of parameters controlling the numerical algorithm. A couple of examples makes familiar to problems which were treated with {\sc Kardos}. We are extending this guide continuously. The latest version is available by network: {\begin{rawhtml} 〈A href="http://www.zib.de/Numerik/software/kardos/"〉 〈i〉 Downloads.〈/i〉〈/a〉 \end{rawhtml}}

Beschreibung: This article studies the relation of the two scientific languages Chemistry and Mathematics via three selected comparisons: (a) QSSA versus dynamic ILDM in reaction kinetics, (b) lumping versus discrete Galerkin methods in polymer chemistry, and (c) geometrical conformations versus metastable conformations in drug design. The common clear message from these comparisons is that chemical intuition may pave the way for mathematical concepts just as chemical concepts may gain from mathematical precisioning. Along this line, significant improvements in chemical research and engineering have already been possible -- and can be further expected in the future from the dialogue between the two scientific languages.

Beschreibung: Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper, we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.

Beschreibung: Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.

Beschreibung: In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph $G=(V,E)$ together with a set of wavelengths~$W$ and a finite sequence $\sigma=r_1,r_2,\dots$ of calls which arrive in an online fashion. Each call~$r_j$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~$G$ together with a wavelength~$\lambda \in W$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.

Beschreibung: Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called $c$-competitive if on every input the solution it produces has cost'' at most $c$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.

Beschreibung: The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times but finite expectation. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing results recently obtained by Choi et al. in case of deterministic maximal waiting times. For deterministic maximal waiting times partially new explicit formulae are given.

Beschreibung: The bio-heat transfer equation is a macroscopic model for describing the heat transfer in microvascular tissue. So far the deduction of the Helmholtz term in the bio-heat transfer equation is not co role. In view of a future numerical application of this new mathematical model to treatment planning in hyperthermia we derive asymptotic estimates for first and second order correctors.

Beschreibung: Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy.

Beschreibung: We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.

Beschreibung: Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.

Beschreibung: Nachdem mit der KOBV-Suchmaschine die Online-Recherche in den wichtigsten Berliner und Brandenburgischen Bibliotheken realisiert ist, gehört der Aufbau der Online-Fernleihe als einer neuen, nutzerfreundlichen Dienstleistung zu den drängendsten Desideraten des KOBV. Dem Nutzer soll ein komfortabler Service geboten werden, der ihm im Anschluss an eine erfolgreiche Recherche die nahtlose - per Knopfdruck ausgelöste - Fernleih-Bestellung auf das gewünschte Medium erlaubt. Gleichzeitig trägt die Ablösung des traditionellen, per Post und Bücherauto versandten Roten Fernleihscheines durch eine sekundenschnelle Online-Kommunikation zu einer erheblichen Beschleunigung des Fernleih-Verfahrens bei. Der KOBV beteiligt sich an der Initiative der deutschen Bibliotheksverbünde zur Automatisierung und Beschleunigung der Fernleihe. Die Realisierung soll im KOBV in einem zweistufigen Verfahren erfolgen: (1) verbundinterne Fernleihe im KOBV und (2) verbundübergreifende Fernleihe in der Zusammenarbeit mit den anderen Verbünden. Eine Verbund-Fernleih-Software für den KOBV muss insbesondere den KOBV-spezifischen Gegebenheiten genügen, die in dieser Form in den anderen deutschen Verbünden nicht anzutreffen sind. Im Jahre 2001 hat eine KOBV-Arbeitsgruppe Spezifikationen für eine Verbund-Fernleih-Software erarbeitet, in der die Besonderheiten des KOBV mit berücksichtigt sind. Beim Aufbau der automatisierten Fernleihe als einer regulären KOBV-Dienstleistung geht es nicht allein darum, einen schnellen, komfortablen Service für Nutzer einzurichten, sondern darüber hinaus um eine weitreichende Rationalisierung innerhalb der Bibliotheken. Das vorliegende Spezifikationspapier zielt auf beide Faktoren ab, indem es die Fernleihe als integrierten Dienst entwirft, der von der Bestellung bis zur Bereitstellung des Mediums in der gebenden Bibliothek automatisiert - ohne manuelles Eingreifen der Fernleihstelle - abläuft: die jetzige manuell durchgeführte Fernleihe wird durch die automatisierte Fernleihe abgelöst.

Beschreibung: In the online traveling salesman problem $OLTSP$ requests for visits to cities arrive online while the salesman is traveling. We study the $F{\_max}-OLTSP$ where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortunately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algorithms. Not even resource augmentation which is helpful in scheduling works as a remedy. This unsatisfactory situation motivates the search for alternative analysis methods. We introduce a natural restriction on the adversary for the $F{\_max}-OLTSP$ on the real line. A \emph{non-abusive adversary} may only move in a direction if there are yet unserved requests on this side. Our main result is an algorithm which achieves a constant competitive ratio against the non-abusive adversary.

Beschreibung: While attribute-value pairs are a popular method to name objects, information retrieval from those attribute-based namespaces is not an easy task. The user has to recall correct attribute names and values and master the syntax and semantics of query formulation. This paper describes hierarchical structures in attribute-based namespaces, shows how to extract them efficiently and evaluates the quality of these structures in an user experiment. It proposes an user interface for browsing attribute-named object sets which makes this task resemble todays file-system browsers and compares the usability of this interface to normal form-based methods in an user study.

Beschreibung: In this paper, we quantify and discuss the physical and surface chemical processes leading to the formation, temporal evolution and sedimentation of dust grains in brown dwarf and giant gas planet atmospheres: nucleation, growth, evaporation and gravitational settling. Considering dust particles of arbitrary sizes in the different hydrodynamical regimes (free molecular flow, laminar flow, turbulent flow), we evaluate the equilibrium drift velocities (final fall speeds) and the growth rates of the particles due to accretion of molecules. We show that a depth-dependent maximum size of the order of $a_{\rm max}\!\approx\!1\,\mu{\rm m\,(upper\ regions)} \ldots 100\,\mu{\rm m\,(lower\ regions)}$ exists, which depends on the condensate and the stellar parameters, beyond which gravitational settling is faster than growth. Larger particles can probably not be formed and sustained in brown dwarf atmospheres. We furthermore argue that the acceleration towards equilibrium drift is always very fast and that the temperature increase of the grains due to the release of latent heat during the growth process is negligible. Based on these findings, we formulate the problem of dust formation coupled to the local element depletion/enrichment of the gas in brown dwarf atmospheres by means of a system of partial differential equations. These equations state an extension of the moment method developed by Gail\plus Sedlmayr\,(1988) with an additional advective term to account for the effect of size-dependent drift velocities of the grains. A dimensionless analysis of the new equations reveals a hierarchy of nucleation $\to$ growth $\to$ drift $\to$ evaporation, which characterises the life cycle of dust grains in brown dwarf atmospheres. The developed moment equations can be included into hydrodynamics or classical stellar atmosphere models. Applications of this description will be presented in a forthcoming paper of this series.

Beschreibung: Global grid environments do not only provide massive aggregated computing power but also an unprecedented amount of distributed storage space. Unfortunately, dynamic changes caused by component failures, local decisions, and irregular data updates make it difficult to efficiently use this capacity. In this paper, we address the problem of improving data availability in the presence of unreliable components. We present an analytical model for determining an optimal combination of distributed replica catalogs, catalog sizes, and replica servers. Empirical simulation results confirm the accuracy of our theoretical analysis. Our model captures the characteristics of highly dynamic environments like peer-to-peer networks, but it can also be applied to more centralized, less dynamic grid environments like the European {\em DataGrid}.

Beschreibung: Das Management von großen Datenmengen spielt eine immer wichtigere Rolle, wie aktuelle Entwicklungen in der Hochenergiephysik [2] zeigen. Für das DataGrid-Projekt zum Beispiel ist es notwendig, große Datenmengen auf mehrere Rechenzentren in Europa zu verteilen und die Daten untereinander zu synchronisieren. Auch innerhalb von Clustern gewinnen mit zunehmender Anzahl der Knoten Werkzeuge zur effizienten Synchronisation und Verteilung von Daten an Bedeutung. Im Rahmen dieser Arbeit wurde ein effizientes Verfahren zur Synchronisation von verteilten Verzeichnisstrukturen entwickelt und implementiert. Mit diesem Verfahren ist es möglich, unabhängige Änderungen an beliebigen Repositories gleichzeitig durchzuführen. Das Verfahren benötigt keine zentrale Instanz, wodurch eine gegenüber vielen existierenden Verfahren verbesserte Skalierbarkeit erreicht werden konnte. Dabei wurden Erkenntnisse aus der Graphentheorie eingesetzt und weiterentwickelt, um die Netzwerktopolo-gie und -handbreiten zwischen den Rechnern zu berücksichtigen. Durch die Verwendung einer Offline-Synchronisation werden Änderungen erst dann an andere Rechner propagiert, wenn der Nutzer dies anstößt. Das kann zum Beispiel nach einer abgeschlossenen Transaktion, die Änderungen an mehreren Dateien beinhaltet, angemessen sein.

Beschreibung: Current developments in high energy physics [2] show that the management of large datasets plays an important role. For the DataGrid project it is necessary to distribute large datasets over several computing centers all over Europe and to synchronize these datasets. Within clusters tools for efficient synchronization and distribution of data become more important, too. In this thesis, a method to synchronize distributed directory structures was developed and implemented which makes it possible to perform independent changes to arbitrary repositories simultaneously. This method needs no central instance and therefore the presented system achieves a better scalability than many existing systems. Knowledge from graph theory was used and improved to take the network topology and the network bandwidth between the computers into account. By using offline synchronization, changes will only be propagated when the user initiates it. This can be reasonable after a completed transaction which consists of changes on several files.

Beschreibung: An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.

Beschreibung: Hinter der für den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Dieser Artikel erläutert einige Aspekte der Theorie und erklärt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?

Beschreibung: The Cooperative Library Network Berlin-Brandenburg (KOBV) has set the development of a genuine library information portal for the two German Lander (federal states) Berlin and Brandenburg as its main task for the next years. This joined effort is driven by the vision of an user friendly Internet information portal which is accessible anytime, from anywhere in the world. The idea of a regional information portal can be understood as the logically consistent development of the basic ideas of the KOBV. Starting in 1997, the consortia has set the implementation of a virtual OPAC instead of a physical union catalogue as its goal. The result was the KOBV-Search Engine which already has some qualities of a portal itself. The paper begins with initial remarks about the German library world, which do form the background for the project and its initiator - the KOBV consortia. After this preliminary part, different types of portals are introduced. The basic features of the KOBV-Search Engine as one of the cornerstones of the future portal are discussed in the following. The information portal will be much richer in content and services for the end-user. Two aspects are focused on in more detail: the presentation of resources, which becomes a compelling requirement because of the broader range of content and the personalization of services, as one important feature to suit user's individual needs.

Beschreibung: The paper presents a particle method framework for resolving molecular dynamics. Error estimators for both the temporal and spatial discretization are advocated and facilitate a fully adaptive propagation. For time integration, the implicit trapezoidal rule is employed, where an explicit predictor enables large time steps. The framework is developed and exemplified in the context of the classical Liouville equation, where Gaussian phase-space packets are used as particles. Simplified variants are discussed shortly, which should prove to be easily implementable in common molecular dynamics codes. A concept is illustrated by numerical examples for one-dimensional dynamics in double well potential.

Beschreibung: The paper deals with three different Newton algorithms that have recently been worked out in the general frame of affine invariance. Of particular interest is their performance in the numerical solution of discretized boundary value problems (BVPs) for nonlinear partial differential equations (PDEs). Exact Newton methods, where the arising linear systems are solved by direct elimination, and inexact Newton methods, where an inner iteration is used instead, are synoptically presented, both in affine invariant convergence theory and in numerical experiments. The three types of algorithms are: (a) affine covariant (formerly just called affine invariant) Newton algorithms, oriented toward the iterative errors, (b) affine contravariant Newton algorithms, based on iterative residual norms, and (c) affine conjugate Newton algorithms for convex optimization problems and discrete nonlinear elliptic PDEs.

Beschreibung: In Analogie zu den Elektrizitätsnetzen electricity grid), von denen die technische Revolution ausging, wurde der Begriff Computational Grid (kurz Grid) geprägt. Ein wichtiger Bestandteil des Systems liegt im benutzerfreundlichen Zugang und der koordinierten Nutzung der weltweit verteilten Speicherressourcen und Rechnerkapazitäten. Bei der Entwicklung dazu notwendiger Technologien und Software (Middleware) profitiert man von Kenntnissen und Erfahrungen bei der Entwicklung verteilter Algorithmen, dem Software-Engineering und dem Supercomputing.

Beschreibung: In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer has to satisfy certain survivability and routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented.

Beschreibung: We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.

Beschreibung: Eine fremddatengestützte Katalogisierung bedeutet für die einzelne Bibliothek unbestritten eine Zeit- und Kostenersparnis. Dieser Report beleuchtet die unterschiedlichen Faktoren technischer und organisatorischer Natur, die die Fremddatennutzung in der dezentralen Struktur des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) beeinflussen. Die Ausführungen stützen sich im Wesentlichen auf eine Umfrage, die die Autoren im Mai / Juni 2002 unter KOBV-Mitgliedsbibliotheken zum Thema Fremddatennutzung durchgeführt haben. Dargelegt wird, wie komfortabel die in den KOBV-Bibliotheken eingesetzten Bibliotheksinformationssysteme eine fremddatengestützte Katalogisierung erlauben. Diskutiert wird zudem die Software ZACK, die sich als Alternative zu einem eigenen Z39.50-Client zur Datenübernahme anbietet. Erstmals seit Bestehen des Verbundes werden Zahlen veröffentlicht über den Anteil der Bibliotheken, die Fremddaten nutzen und denjenigen, die dieses Angebot nicht wahrnehmen. Dabei wird die Fremddatenutzung differenziert sowohl für den Bereich der Neuaufnahmen als auch für die Retrokatalogisierung. In der weiteren Analyse werden zusätzliche Aspekte betrachtet wie z.B. die verfügbaren bzw. gewünschten Datenbanken im Verhältnis zum sprachlichen Spektrum des erworbenen Katalogisierungsgutes. Eingegangen wird auch auf die von den Bibliotheken genannten Hauptproblemen und die gewünschten zusätzlichen Serviceleistungen auf Seiten der KOBV-Verbundzentrale. Als Ergebnis dieses Status-Quo-Berichts legt das Autorenteam eine Reihe von Empfehlungen vor, die darauf abzielen, auch für KOBV-Bibliotheken in Zukunft eine Fremddatennutzungsquote von 70 - 75 % zu erreichen.

Beschreibung: Substellar atmospheres are cool and dense enough that dust forms very efficiently. As soon as these particles are formed, they sizedependently precipitate due to the large gravity of the objects. Arriving in hot atmospheric layers, the dust evaporates and enriches the gas by those elements from which it has formed. The upper atmospheric layers are depleted by the same elements. Non-continuous and spatially inhomogeneous convective element replenishment, generating a turbulent fluid field, completes the circuit of dust. The formation of dust in substellar atmosphere is described by extending the classical theory of Gail\plus Sedlmayr for the case of different gas and dust velocities. Turbulence is modeled in different scale regimes which reveals turbulence as trigger for dust formation in hot environments. Both mechanisms cause the dust to be present in else wise dust-hostile region: precipitation transports the dust into hot regions, and turbulence allows the formation of dust in there.

Beschreibung: The talk given by the author at the CRM workshop on Superintegrability in Sep.\ 2002 and this related paper report on work in two subjects. One is the collaboration with Vladimir Sokolov and Takayuki Tsuchida in an effort to classify polynomial integrable vector evolution equations. The other is the computer algebra package {\sc Crack} which did the main computations in solving large bi-linear algebraic systems. Although originally designed to solve over-determined systems of partial differential equations a number of extensions made {\sc Crack} a powerful tool for solving systems of bi-linear algebraic equations. Such systems turn up in many different classification problems some of which were investigated by other participants of this workshop. Two additional applications are outlined. In the talk on which this article is based a method to reduce the length of equations was presented which proved to be useful in solving the bi-linear algebraic systems. Due to numerous asked questions about the computer program, a more complete overview is given in the appendix.

Beschreibung: Die KOBV-Suchmaschine hat seit ihrer Inbetriebnahme Ende 1999 entscheidend zur Verbesserung der Informationsinfrastruktur in Berlin und Brandenburg beigetragen. Auf der Basis der offenen Plattform KOBV-Suchmaschine wird die KOBV-Zentrale gemeinsam mit den Bibliotheken in den nächsten Jahren das Dienstleistungsangebot des KOBV und seiner Bibliotheken kontinuierlich erweitern. Dabei sollen die Prinzipien des KOBV - Offenheit, Heterogenität und Dezentralität auf technischer und organisatorischer Ebene - gewahrt bleiben. Die einzelnen KOBV-Bibliotheken werden sich mit ihren Angeboten in unterschiedlicher Weise im Web positionieren. Die Integration auf regionaler Ebene kann und soll die lokalen Angebote nicht künstlich vereinheitlichen. Das kooperative Portal, das in der Region aufgebaut wird, ist als System geplant, in dem zentrales Portal und lokale Portale nicht hierarchisch einander zugeordnet, sondern miteinander vernetzt sind. Das \glqq KOBV-Informationsportal \grqq soll in der KOBV-Zentrale im Rahmen eines wissenschaftlichen Projektes von Mitte 2001 bis Ende 2003 aufgebaut werden. Das vorliegende Papier gibt einen ersten allgemeinen Einblick, welche Funktionen das \glqq KOBV-Informationsporta \grqq umfassen soll und stellt die Teilprojekte der 1. Stufe vor.

Beschreibung: Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework.

Beschreibung: For all perfect graphs, the stable set polytope STAB$(G)$ coincides with the fractional stable set polytope QSTAB$(G)$, whereas STAB$(G) \subset$ QSTAB$(G)$ holds iff $G$ is imperfect. Padberg asked in the early seventies for ``almost'' perfect graphs. He characterized those graphs for which the difference between STAB$(G)$ and QSTAB$(G)$ is smallest possible. We develop this idea further and define three polytopes between STAB$(G)$ and QSTAB$(G)$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB$(G)$. The difference between QSTAB$(G)$ and the largest of the three polytopes coinciding with STAB$(G)$ gives some information on the stage of imperfectness of the graph~$G$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost'' perfect?

Beschreibung: Die Automatisierung von innerbetrieblicher Logistik erfordert -- über die physikalische Steuerung von Geräten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollständiges Wissen) sowie die Echtzeit-Problematik (beschränkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen Überblick über allgemeine Konstruktionsprinzipien für Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen für eine vorliegende Problemstellung geeignet sind.

Beschreibung: \We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect.

Beschreibung: \textsf{\itshape{GuiGen}} is a comprehensive set of tools for creating customized graphical user interfaces (GUIs). It draws from the concept of computing portals, which are here seen as interfaces to application-specific computing services for user communities. While \textsf{\itshape{GuiGen}} was originally designed for the use in computational grids, it can be used in client/server environments as well. Compared to other GUI generators, \textsf{\itshape{GuiGen}} is more versatile and more portable. It can be employed in many different application domains and on different target platforms. With \textsf{\itshape{GuiGen}}, application experts (rather than computer scientists) are able to create their own individually tailored GUIs.

Beschreibung: The purpose of the paper is to formulate and use syzygies for systems of linear PDEs. The computation of an equivalent of a GCD for linear partial differential operators will save us their factorization which is otherwise only possible algorithmically in special cases. After showing the computation with the new and the traditional method and comparing both in the next three sections, the algorithm is explained in general and an overview is given.

Beschreibung: Telekommunikation ist seit Jahren \glqq in\grqq. Zunächst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine überwältigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgelöst durch die UMTS-Lizenzversteigerungen, Rezessions- und Sättigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon überzeugt, dass technischer Fortschritt und nützliche Dienste demnächst die Stimmung wieder ändern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein Überblick über diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemadäquater Algorithmen erreichen kann.

Beschreibung: Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im öffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken für den Einsatz in den Planungssystemen MICROBUS II und DIVA.

Beschreibung: A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.

Beschreibung: Recently, a novel approach for the analysis of molecular dynamics on the basis of a transfer operator has been introduced. Therein conformations are considered to be disjoint metastable clusters within position space of a molecule. These clusters are defined by almost invariant characteristic functions that can be computed via {\em Perron Cluster} analysis. The present paper suggests to replace crisp clusters with {\em fuzzy} clusters, i.e. to replace characteristic functions with membership functions. This allows a more sufficient characterization of transiton states between different confor conformations and therefore leads to a better understanding of molecular dynamics. Fur thermore, an indicator for the uniqueness of metastable fuzzy clusters and a fast algorithm for the computation of these clusters are described. Numerical examples are included.

Beschreibung: The paper provides a detailed analysis of a short step interior point algorithm applied to linear control constrained optimal control problems. Using an affine invariant local norm and an inexact Newton corrector, the well-known convergence results from finite dimensional linear programming can be extended to the infinite dimensional setting of optimal control. The present work complements a recent paper of Weiser and Deuflhard, where convergence rates have not been derived. The choice of free parameters, i.e. the corrector accuracy and the number of corrector steps, is discussed.

Beschreibung: Pseudo--transient continuation methods are quite popular for the numerical solution of steady state problems, typically in PDEs. They are based on an embedding into a time dependent initial value problem. In the presence of dynamical invariants the Jacobian matrix of the nonlinear equation system is bound to be singular. The paper presents a convergence analysis which takes this property into account -- in contrast to known approaches. On the basis of the new analysis adaptive algorithms are suggested in detail. These include a variant with Jacobian approximations as well as inexact pseudo--transient continuation, both of which play an important role in discretized PDEs. Numerical experiments are left to future work.

Beschreibung: A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$.

Beschreibung: TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.

Beschreibung: A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.

Beschreibung: Computational drug design studies molecular recognition in the {\em virtual lab}. The arising Hamiltonian dynamics is known to be chaotic and ill-conditioned already after picoseconds, whereas times are $msec$ up to $min$. Classical molecular dynamics with long term trajectory computation gives, at best, information about time and statistical ensemble averages. The present paper surveys a recent new modeling approach called {\em conformational dynamics}, which is due to the author and Ch. Schütte. This approach achieves information about the dy time scales by telescoping a short term deterministic model with a statistical model. Examples of small biomolecules are included.

Beschreibung: Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.

Beschreibung: A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$.

Beschreibung: Die Bibliotheken des KOBV haben im Jahr 2001 die Entwicklung der KOBV-Suchmaschine zu einem gemeinsamen Informationsportal Berlin-Brandenburg und den Aufbau lokaler Bibliotheksportale als Hauptentwicklungsziele des KOBV definiert. Diese Informationsportale sollen mit Standardsoftware realisiert werden. Um die Auswahl eines Systems zu unterstützen, wurde in der Zentrale des KOBV ausgewählte Systeme untersucht. In der Arbeit werden zahlreiche Kriterien vorgestellt, auf Grund derer die betreffenden Systeme beurteilt werden. Die Kriterien umfassen sowohl Aspekte aus der Sicht der Benutzer als auch Kriterien aus der Sicht der Betreiber eines solchen Systems. Wesentliche Funktionen und die Realisierung von verschiedenen Merkmalen werden im Bericht ausführlich beschrieben. Daneben liefert eine Tabelle mit allen betrachteten Kriterien eine Übersicht über vorhandene Merkmale und der Art der Realisierung.

Beschreibung: In the cake cutting problem, $n\ge2$ players want to cut a cake into $n$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with $n-1$~cuts in which each player can enforce to get a share of at least~$1/(2n-2)$. Moreover we show that no protocol with $n-1$~cuts can guarantee a better fraction.

Beschreibung: We present a new efficient algorithm for the solution of direct time-harmonic scattering problems based on the Laplace transform. This method does not rely on an explicit knowledge of a Green function or a series representation of the solution, and it can be used for the solution of problems with radially symmetric potentials and problems with waveguides. The starting point is an alternative characterization of outgoing waves called \emph{pole condition}, which is equivalent to Sommerfeld's radiation condition for problems with radially symmetric potentials. We obtain a new representation formula, which can be used for a numerical evaluation of the exterior field in a postprocessing step. Based on previous theoretical studies, we discuss the numerical realization of our algorithm and compare its performance to the PML method.

Beschreibung: The aim of this paper is to develop fast methods for the solution of nonlinear Schrödinger type equations in fiber optics. Using the method of lines we have to solve a stiff system of ordinary differential equations where the eigenvalues of the Jacobian are close to the imaginary axis. This is usually done by a Split Step method. Here we consider the extrapolation of Split Step methods with adaptive order and step size control. For more complicated nonlinearities, in particular stimulated Raman scattering, Split Step methods are less efficient since symmetry is either destroyed or requires much additional effort. In this case we use implicit Runge Kutta formulas of Gauß type. The key point for the efficient implementation of these methods is that the system of nonlinear algebraic equations can be solved without setting up the Jacobian. The proposed methods are compared to other methods, in particular exponential integrators, the method of Marcuse, and the method of Blow and Wood.

Beschreibung: The work presents a new approach to the numerical solution of time-harmonic and time-dependent scattering problems. We replace Sommerfeld's radiation condition valid for the Helmholtz equation by a more general concept called pole condition. The pole condition is based on the Laplace transform of the exterior solution and allows a characterization of outgoing waves. Both new insight into the analysis of scattering problems as well as new numerical algorithms are obtained.

Beschreibung: The paper's main result is a simple derivation rule for the Jacobi polynomials with respect to their parameters, i.e. for $\partial_{\alpha} P_n^{\alpha,\beta}$, and $\partial_{\beta} P_n^{\alpha,\beta}$. It is obtained via relations for the Gaussian hypergeometric function concerning parameter derivatives and integer shifts in the first two arguments. These have an interest on their own for further applications to continuous and discrete orthogonal polynomials. The study is motivated by a Galerkin method with moving weight, presents all proofs in detail, and terminates in a brief discussion of the generated polynomials.

Beschreibung: We derive a simple accuracy matching strategy for inexact Gauss Newton methods and apply it to the numerical solution of boundary value problems of ordinary differential equations by collocation. The matching strategy is based on an affine contravariant convergence theorem, i. e. , the characteristic constants are invariant under affine transformations of the domain. The inexact Gauss Newton method is applied to an integral formulation of the BVP. As discretization for the arising linear subproblems we employ adaptive collocation at Gaussian nodes with varying local orders and stepsizes. The grids are chosen via adaptive refinement and order selection.

Beschreibung: In this article we present a method to implement orthogonal polynomials and many other special functions in Computer Algebra systems enabling the user to work with those functions appropriately, and in particular to verify different types of identities for those functions. Some of these identities like differential equations, power series representations, and hypergeometric representations can even dealt with algorithmically, i.\ e.\ they can be computed by the Computer Algebra system, rather than only verified. The types of functions that can be treated by the given technique cover the generalized hypergeometric functions, and therefore most of the special functions that can be found in mathematical dictionaries. The types of identities for which we present verification algorithms cover differential equations, power series representations, identities of the Rodrigues type, hypergeometric representations, and algorithms containing symbolic sums. The current implementations of special functions in existing Computer Algebra systems do not meet these high standards as we shall show in examples. They should be modified, and we show results of our implementations.

Beschreibung: {\newcommand{\R} {{\rm {\mbox{\protect\makebox[.15em][l]{I}R}}}} Given a list of $n$ numbers in $\R $, one wants to decide wether every number in the list occurs at least $k$ times. I will show that $(1-\epsilon)n\log_3(n/k)$ is a lower bound for the depth of a linear decision tree determining this problem. This is done by using the Björner-Lov\'asz method, which turns the problem into one of estimating the Möbius function for a certain partition lattice. I will also calculate the exponential generating function for the Möbius function of a partition poset with restricted block sizes in general.}

Beschreibung: Die Autoren sind sich dar{ü}ber im klaren, daß zahlreiche Imponderabilien die Ergebnisse der vorgelegten Modellrechnungen beeinflussen k{ö}nnen. Immerhin repräsentiert jedoch das vorgelegte mathematische Modell die Summe unserer derzeitigen Kenntnisse zur Fragestellung AIDS--Epidemie; neu hinzukommende Erkenntnisse lassen sich rasch einarbeiten und in ihren Konsequenzen überschauen. Die Entwicklung neuer effizienter numerischer Methoden spielte eine Schlüsselrolle bei der tatsächlichen Simulation dieses umfangreichen realitätsnahen mathematischen Modells.

Beschreibung: We present an adaptive Rothe method for two--dimensional problems combining an embedded Runge--Kutta scheme in time and a multilevel finite element discretization in space. The spatial discretization error is controlled by a posteriori error estimates based on interpolation techniques. A computational example for a thermodiffusive flame propagation model illustrates the high accuracy that is possible with the proposed method.

Beschreibung: The multicommodity linear formulation of the Fixed Charge Network Flow Design problem is known to have significantly sharp linear relaxation lower bounds. However the tradeoff is the introduction of a large amount of artificial variables. We exhibit a class of special instances for which the lower bound is tight. Further we completly describe the polyhedron in the space of the natural variables.

Beschreibung: Die von der DMV-Fachgruppe Scientific Computing in Kooperation mit dem gleichnamigen GAMM-Fachausschuss organisierte Tagung \glqq Scientific Computing in der Theoretischen Physik\grqq~fand vom 16. - 18. März 1994 am Fachbereich Mathematik und Informatik der Freien Universität Berlin statt. Ziel des Workshops war, die Kontakte zwischen den Fachleuten der Gebiete {\em Computational Physics} und {\em Scientific Computing} zu intensivieren. Schwerpunkte des Workshops waren numerische Simulation von Transportmodellen der Astrophysik und Halbleiterphysik, Multilevel-Methoden für partielle Differentialgleichungen sowie Monte-Carlo-Methoden und molekulardynamische Verfahren für Probleme der Statistischen Physik und Quantenfeldtheorie. Der Workshop fand ein äusserst positives Echo und führte über 70 Teilnehmer der verschiedenen Teilgebiete der Theoretischen Physik und ca. 50 Teilnehmer aus dem Bereich der Numerischen Mathematik zusammen. \originalTeX

Beschreibung: We give an overview of an approach on special functions due to Truesdell, and show how it can be used to develop certain type of identities for special functions. Once obtained, these identities may be verified by an independent algorithmic method for which we give some examples.

Beschreibung: {\newcommand{\N} {{\rm {\mbox{\protect\makebox[.15em][l]{I}N}}}} In several publications the first author published an algorithm for the conversion of analytic functions for which derivative rules are given into their representing power series $\sum\limits_{k=0}^{\infty}a_{k}z^{k}$ at the origin and vice versa, implementations of which exist in {\sc Mathematica}, {\sc Maple} and {\sc Reduce}. One main part of this procedure is an algorithm to derive a homogeneous linear differential equation with polynomial coefficients for the given function. We call this type of ordinary differential equations {\sl simple}. Whereas the opposite question to find functions satisfying given differential equations is studied in great detail, our question to find differential equations that are satisfied by given functions seems to be rarely posed. In this paper we consider the family $F$ of functions satisfying a simple differential equation generated by the rational, the algebraic, and certain transcendental functions. It turns out that $F$ forms a linear space of transcendental functions. % with polynomial function coefficients. Further $F$ is closed under multiplication and under the composition with rational functions and rational powers. These results had been published by Stanley who had proved them by theoretical algebraic considerations. In contrast our treatment is purely algorithmically oriented. We present algorithms that generate simple differential equation for $f+g$, $f\cdot g$, $f\circ r$ ($r$ rational), and $f\circ x^{p/q}$ ($p,q\in\N_0$), given simple differential equations for $f$, and $g$, and give a priori estimates for the order of the resulting differential equations. We show that all order estimates are sharp. After finishing this article we realized that in independent work Salvy and Zimmermann published similar algorithms. Our treatment gives a detailed description of those algorithms and their validity.}

Beschreibung: The power of the symbolic math system {\small REDUCE} for solving large and difficult problems in science and engineering is demonstrated by a set of model problems. These include algebraic equation solving, formal variable elimination, formal power series, symbolic treatment of differential equations and applications from theoretical physics.

Beschreibung: Results from finite-element-calculations are usually visualized by colored surface- and contour-line-plots or polygonal patches or simply displaced lines and grids. In computer graphics however more advanced techniques like texture-mapping and NURBS are well established and there exist efficient algorithms and implementations. We show that these techniques are not only easy to use, but form a very natural and far more efficient approach for visualization of higher order finite-element's solutions like in $p$- and $h$-$p$-version. Texture-mapping is useful for displaying vector-valued data, too.

Beschreibung: In Quantum Chemistry the field of Laser--Assisted Molecular Control'' has received a considerable amount of attention recently. One key problem in this new field is the simulation of the dynamical reaction of a molecule subjected to external radiation. This problem is described by the Schrödinger equation, which, after eigenfunction expansion, can be written in the form of a large system of ordinary differential equations, the solutions of which show a highly oscillatory behaviour. The oscillations with high frequencies and small amplitudes confine the stepsizes of any numerical integrator -- an effect, which, in turn, blows up the simulation time. Larger stepsizes can be expected by averaging these fast oscillations, thus smoothing the trajectories. Standard smoothing techniques (averaging, filtering) would kill the whole process and thus, lead to wrong numerical results. To avoid this unwanted effect and nevertheless speed up computations, this paper presents a quasiresonant smoothing algorithm (QRS). In QRS, a natural splitting parameter $\delta$ controls the smoothing properties. An adaptive QRS--version (AQRS) is presented which includes an error estimation scheme for choosing this parameter $\delta$ in order to meet a given accuracy requirement. In AQRS $\delta$ is permanently adapted to the solution properties for computing the chemically necessary information'' only. The performance of AQRS is demonstrated in several test problems from the field Laser--Assisted Selective Excitation of Molecules'' in which the external radiation is a picosecond laser pulse. In comparison with standard methods speedup factors of the order of $10^2$ are observed.

Beschreibung: This article describes the REDUCE package ZEILBERG implemented by Gregor Stölting and the author. The REDUCE package ZEILBERG is a careful implementation of the Gosper (The sum package contains also a partial implementation of the Gosper algorithm.) and Zeilberger algorithms for indefinite, and definite summation of hypergeometric terms, respectively. An expression $a_k$ is called a {\sl hypergeometric term} (or {\sl closed form}), if $a_{k}/a_{k-1}$ is a rational function with respect to $k$. Typical hypergeometric terms are ratios of products of powers, factorials, $\Gamma$ function terms, binomial coefficients, and shifted factorials (Pochhammer symbols) that are integer-linear in their arguments.

Beschreibung: We test the performance of the multicanonical approach for biological molecules. The simulated molecules are frustrated systems with a complicated energy landscape. The resulting slowing down in simulations is alleviated by our ansatz. We perform a multicanonical simulation of nonpolar amino acids and study their $\alpha$-helix propensities. The results are shown to be in agreement with recent experimental results.

Beschreibung: In an array of coupled oscillators {\em synchronous chaos} may occur in the sense that all the oscillators behave identically although the corresponding motion is chaotic. When a parameter is varied this fully symmetric dynamical state can lose its stability, and the main purpose of this paper is to investigate which type of dynamical behavior is expected to be observed once the loss of stability has occurred. The essential tool is a classification of Lyapunov exponents based on the symmetry of the underlying problem. This classification is crucial in the derivation of the analytical results but it also allows an efficient computation of the dominant Lyapunov exponent associated with each symmetry type. We show how these dominant exponents determine the stability of invariant sets possessing various instantaneous symmetries and this leads to the idea of {\em symmetry breaking bifurcations of chaotic attractors}. Finally the results and ideas are illustrated for several systems of coupled oscillators.

Beschreibung: We present new Monte Carlo results in non-compact lattice QED with staggered fermions down to $m_0 = 0.005$. This extends our previous investigations on the nature of the continuum limit of QED.

Beschreibung: The celebrated Zeilberger algorithm which finds holonomic recurrence equations for definite sums of hypergeometric terms $F(n,k)$ is extended to certain nonhypergeometric terms. An expression $F(n,k)$ is called hypergeometric term if both $F(n+1,k)/F(n,k)$ and $F(n,k+1)/F(n,k)$ are rational functions. Typical examples are ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are integer-linear with respect to $n$ and $k$ in their arguments. We consider the more general case of ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are rational-linear with respect to $n$ and $k$ in their arguments, and present an extended version of Zeilberger's algorithm for this case, using an extended version of Gosper's algorithm for indefinite summation. In a similar way the Wilf-Zeilberger method of rational function certification of integer-linear hypergeometric identities is extended to rational-linear hypergeometric identities. The given algorithms on definite summation apply to many cases in the literature to which neither the Zeilberger approach nor the Wilf-Zeilberger method is applicable. Examples of this type are given by theorems of Watson and Whipple, and a large list of identities (``Strange evaluations of hypergeometric series'') that were studied by Gessel and Stanton. It turns out that with our extended algorithms practically all hypergeometric identities in the literature can be verified. Finally we show how the algorithms can be used to generate new identities. REDUCE and MAPLE implementations of the given algorithms can be obtained from the author, many results of which are presented in the paper.

Beschreibung: We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework. \\{\bf Abstract: }We present a set of C++ classes that realize an abstract inexact Gauss Newton method in combination with a continuation process for the solution of parameter dependent nonlinear problems. The object oriented approach allows the continuation of different types of solutions within the same framework.

Beschreibung: We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes and similar linear programs with exponential decreasing paths. The analysis of two randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds conjectured in the literature. At the same time, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.

Beschreibung: We consider nested iterations, in which the multigrid method is replaced by some simple basic iteration procedure, and call them {\em cascadic iterations}. They were introduced by Deuflhard, who used the conjugate gradient method as basic iteration (CCG method). He demonstrated by numerical experiments that the CCG method works within a few iterations if the linear systems on coarser triangulations are solved accurately enough. Shaidurov subsequently proved multigrid complexity for the CCG method in the case of $H^2$-regular two-dimensional problems with quasi-uniform triangulations. We show that his result still holds true for a large class of smoothing iterations as basic iteration procedure in the case of two- and three-dimensional $H^{1+\alpha}$-regular problems. Moreover we show how to use cascadic iterations in adaptive codes and give in particular a new termination criterion for the CCG method.

Beschreibung: The results from invariant theory and the results for semi-invariants and equivariants are summarized in a way suitable for the combination with Gröbner basis computation. An algorithm for the determination of fundamental equivariants using projections and a Poincar\'{e} series is described. Secondly, an algorithm is given for the representation of an equivariant in terms of the fundamental equivariants. Several ways for the exact determination of zeros of equivariant systems are discussed

Beschreibung: We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.

Beschreibung: In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design.

Beschreibung: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set $N$ of items, a capacity $F \in \N$ and weights $a_i \in \N$, $i \in N$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{i \in N} a_i x_i \leq F.$$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where $a_i \in \{\mu,\lambda\}$ for all items $i \in N$ and $1 \leq \mu 〈 \lambda \leq b$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.}

Beschreibung: We compare a few variants of the recently proposed multicanonical method with the well known simulated annealing for the effectiveness in search of the energy global minimum of a biomolecular system. For this we study in detail Met-enkephalin, one of the simplest peptides. We show that the new method not only outperforms simulated annealing in the search of the energy groundstate but also provides more statistical-mechanical information about the system.

Beschreibung: We demonstrate the effectiveness of the multicanonical algorithm for the tertiary structure prediction of peptides and proteins. Unlike to simulated annealing the relationship to the canonical ensemble remains exactly controlled. Hence, the new method allows not only the prediction of the lowest-energy conformation, but also the calculation of thermodynamic quantities at various temperature from one run.

Beschreibung: Die enorme algorithmische Beschleunigung durch diskrete Galerkin-Methoden f{ü}r abz{ä}hlbare Differentialgleichungssysteme hat der Simulation von Polymerisationsprozessen neue, industriell relevante Problembereiche er{ö}ffnet, die mit den bis dahin verf{ü}gbaren Methoden nicht zug{ä}nglich waren.

Beschreibung: Large chemical computations show the need for full adaptivity supporting the development of robust and highly efficient programs. For solutions possessing sharp moving spatial transitions, as travelling wavefronts or emerging boundary and internal layers, an automatic adjustment of both the space and the time stepsize is generally accepted to be more successful in efficient resolving critical regions of high spatial and temporal activity. In contrast to the widespread discretization sequence first space then time the reversed sequence first time then space is employed. Full adaptivity of the proposed algorithm is realized by combining embedded time discretization and multilevel finite element space discretization. In this paper the algorithm is described for one--dimensional problems. The numerical results show the significantly new perspectives opened by this approach.

Beschreibung: An error controlled finite elemente method (FEM) for solving stationary Schrödinger equations in three space dimensions is proposed. The method is based on an adaptive space discretization into tetrahedra and local polynomial basis functions of order $p=1$--$5$ defined on these tetrahedra. According to a local error estimator the triangulation is automatically adapted to the solution. Numerical results for standard problems appearing in vibrational motion and molecular structure calculations are presented and discussed. Relative precisions better than 1e-8 are obtained. For equilateral H$_3^{++}$ the adaptive FEM turns out to be superior to global basis set expansions in the literature. Our precise FEM results exclude in a definite manner the stability or metastability of equilateral H$_3^{++}$ in its groundstate.

Beschreibung: {\def\NP{\hbox{$\cal N\kern-.1667em\cal P$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be $\NP$-hard in the strong sense. We show that the storage assignment problem is $\NP$-hard for {\sl bounded sizes and capacities}, even if the sizes have values $1$ and~$2$ and the capacities value~$2$ only, a case we encountered in practice. Moreover, we prove that no polynomial time $\epsilon$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}

Beschreibung: We consider the numerical treatment of Hamiltonian systems that contain a potential which grows large when the system deviates from the equilibrium value of the potential. Such systems arise, e.g., in molecular dynamics simulations and the spatial discretization of Hamiltonian partial differential equations. Since the presence of highly oscillatory terms in the solutions forces any explicit integrator to use very small step-size, the numerical integration of such systems provides a challenging task. It has been suggested before to replace the strong potential by a holonomic constraint that forces the solutions to stay at the equilibrium value of the potential. This approach has, e.g., been successfully applied to the bond stretching in molecular dynamics simulations. In other cases, such as the bond-angle bending, this methods fails due to the introduced rigidity. Here we give a careful analysis of the analytical problem by means of a smoothing operator. This will lead us to the notion of the smoothed dynamics of a highly oscillatory Hamiltonian system. Based on our analysis, we suggest a new constrained formulation that maintains the flexibility of the system while at the same time suppressing the high-frequency components in the solutions and thus allowing for larger time steps. The new constrained formulation is Hamiltonian and can be discretized by the well-known SHAKE method.

Beschreibung: We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.

Beschreibung: We consider periodic orbits of autonomous parameter dependent ODE's. Starting from a shooting algorithm for the numerical computation of periodic orbits via an adaptive Poincar\'e-section we develop a pathfollowing algorithm for periodic solutions based on a tangential continuation method with implicit reparametrization. For ODE's equivariant w.r.t. a finite group we show that spatial as well as spatio-temporal symmetries of periodic orbits can be exploited within the (multiple) shooting context. We describe how turning points, period doubling bifurcations and Hopf points along the branch of periodic solutions can be handled. Furthermore equivariant Hopf points and generic secondary bifurcations of periodic orbits with $ Z_m$-symmetry are treated. We tested the code with standard examples, e.g., the period doubling cascade in the Lorenz equations. To show the efficiency of the described methods we also used the program for an application from electronics, a ring oscillator with $n $ inverters. In this example the exploitation of symmetry reduces the amount of work for the continuation of periodic orbits from ${\cal O}(n^2)$ to ${\cal O}(n)$

Beschreibung: In this article algorithmic methods are presented that have been incorporated in computer algebra systems in the last five years. The methods can be used to identify transcendental functions. The essential idea due to Zeilberger is to represent the functions by systems of holonomic differential and recurrence equations, and the identification procedure utilizes algorithms of Stanley and Zeilberger. Also a noncommutative version of the Buchberger algorithm can be applied.

Beschreibung: In this paper we modify Buchberger's $S$-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established.

Beschreibung: Adopting a statistical approach for the computation of turbulent combustion flows an approximation for the probability density function (PDF) of the composition variables is often required to treat the highly non-linear reaction term in a satisfactory way. One class of methods currently being used are the moment methods which employ transport equations for low order statistical moments and use a parametrized shape of the PDF. A second class solves a transport equation for the joint PDF by a Monte Carlo method. In the present paper we develop an intermediate algorithm based on a Galerkin method for the PDF transport equation. The solution is developed in terms of an orthogonal or bi-orthogonal basis of a suitable Hilbert space. The unconventional use of the related weight function as a prefactor (moving weight approach) permits adaptivity and results in a generalization of the $\beta-$closure for bounded scalar quantities. We present the approximation procedure in detail and apply it to the evolution of the composition in a homogeneous well-stirred reactor. The extension to non-homogeneous flow simulations is straightforward.

Beschreibung: Combinatorial optimization problems pervade many areas of human problem solving especially in the fields of business, economics and engineering. Intensive mathematical research and vast increases in raw computing power have advanced the state of the art in exact and heuristic problem solving at a pace that is unprecedented in human history. We survey here in layman's terms some of the fundamental concepts and principles that have led this progress. (This article will appear -- possibly in modified form -- in a popular science magazine.)

Beschreibung: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set $N$ of items and a capacity $b \in \N$, and let $N_j$ be the set of items with weight $j$, $1 \leq j \leq b$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.$$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) $N_j = \emptyset$ for all $1 〈 j \leq \lfloor {b \over 2} \rfloor$ and (b) $N_j = \emptyset$ for all $1 〈 j \leq \lfloor {b \over 3} \rfloor$ and $N_j = \emptyset$ for all $j \geq \lfloor {b \over 2} \rfloor + 1$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.}

Beschreibung: In the field of deep regional hyperthermia, one of the most widely used devices is the BSD--2000 Hyperthermia System which employs the Sigma 60 applicator. The Sigma 60 consists of four independent sources, giving it the potential to control the energy pattern within the patient. The independent amplitudes and phases, as well as frequency selection and applicator position, present a large number of parameters for the operator to determine. Computer simulation has long been recognized as an attractive approach to optimizing these parameters. A treatment planning program was used in clinical practice at Stanford University Medical Center for two years. It demonstrated the feasibility of computer simulation for deep regional hyperthermia in a clinical situation. However, several parts of this system were written in a language specific to one workstation, which severely restricted the wider distribution of the program to other users of the Sigma 60. A new treatment planning system for the BSD 2000 has been developed and put into clinical practice at the Rudolf Virchow Clinic of the Free University of Berlin. The new method, which we will refer to as the Berlin system, has a simpler model construction program and a considerably better graphics capability. However, the most important feature is that all programs are written in FORTRAN, C, or the X Window graphics system. Therefore, the entire treatment planning system is completely portable to other workstations.

Beschreibung: In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.

Beschreibung: The aim of this paper is to compute all isolated solutions to symmetric polynomial systems. Recently, it has been proved that modelling the sparse structure of the system by its Newton polytopes leads to a computational breakthrough in solving the system. In this paper, it will be shown how the Lifting Algorithm, proposed by Huber and Sturmfels, can be applied to symmetric Newton polytopes. This symmetric version of the Lifting Algorithm enables the efficient construction of the symmetric subdivision, giving rise to a symmetric homotopy, so that only the generating solutions have to be computed. Efficiency is obtained by combination with the product homotopy. Applications illustrate the practical significance of the presented approach.

Beschreibung: In this paper we describe the convex hull of all solutions of the integer bounded knapsack problem in the special case when the weights of the items are divisible. The corresponding inequalities are defined via an inductive scheme that can also be used in a more general setting.

Beschreibung: Die Kombination von elektronischer Fachinformation mit den neuen Mitteln der Kommunikation eröffnet neue Perspektiven für die Mathematik in Deutschland. Aufbauend auf das laufende, BMFT-geförderte Projekt ``Fachinformation'' der Deutschen Mathematiker-Vereinigung (DMV) plant die DMV eine Querschnittsaktivität für die Mathematik. Diese soll nicht nur die mathematischen Fachbereiche und Forschungsinstitute einbeziehen, sondern auch mathematische Forschungslabors aus der Industrie und die Informationsversorger der Mathematik, insbesondere die wissenschaftlichen Verlage, die TIB Hannover, die Bibliotheken der Universitäten und \mbox{-- nicht zuletzt --} das FIZ Karlsruhe mit dem Zentralblatt für Mathematik. \noindent Auf der technischen Grundlage des Internet und seiner weltweit verbreiteten Informationsdienste (Gopher, WAIS, WorldWideWeb, Hyper-G, ftp und E-mail) soll ein verteiltes, mathematisches Informationssystem geschaffen werden, bei dem die Partner des gemeinsamen Vorhabens ihre örtlichen Ressourcen untereinander und zugleich weltweit verfügbar machen. Diese Ziele sind durch konsequenten Einsatz von Software erreichbar, die nach dem Client-Server-Modell strukturiert und die im Internet verbreitet bzw.~anerkannt ist. \noindent Die Bereitstellung von Technik reicht keineswegs aus. Ohne die Schaffung einer personellen, organisatorischen und technischen Infrastruktur ist die Durchführung eines solchen Projekts nicht möglich. Als Massnahmen sind - für alle Partner - geplant: \hspace*{2mm} * Schaffung der Funktion des Informationsbeauftragten \hspace*{2mm} * Einrichtung eines gemeinsamen ``Forums für mathematische Information'' \hspace*{2mm} * Errichtung und Betreuung von mathematischen Informationsstationen \hspace*{2mm} * Teilnahme an nationalen und internationalen Standardisierungsmassnahmen \hspace*{2mm} * Workshops und regelmässige Schulungen, Öffentlichkeitsarbeit \noindent Als Aktivitäten - mit Focus auf mathematische Fachinformation - sind folgende Teilaufgaben und Pilotvorhaben bei allen Partnern geplant: \hspace*{2mm} * Einrichtung von elektronischen Informationssystemen \hspace*{2mm} * Verteiltes elektronisches Angebot von Preprints und Skripten (Volltexte) \hspace*{2mm} * Verteiltes elektronisches Angebot von Software- und Datensammlungen \hspace*{2mm} * Zugriff auf globale Informationssysteme in der Mathematik \hspace*{2mm} * Organisation eines Lebenden Mathematischen Museums \hspace*{2mm} * Zugriff auf elektronische Kataloge von Bibliotheken, insbesondere Fachbereichsbibliotheken \hspace*{2mm} * Schaffung eines organisatorischen Rahmens für elektronische mathematische Journale \hspace*{2mm} * Elektronisches Angebot von eingescannten historischen Dokumenten und Büchern \hspace*{2mm} * Schaffung einer Organisationsform für elektronisches Reviewing \hspace*{2mm} * Erprobung von Verfahren zur elektronischen Lieferung von Dokumenten \hspace*{2mm} * Elektronische Projektorganisation \noindent Das Vorhaben zielt ab auf die Schaffung einer informationstechnischen Infrastruktur für Datenbank-Retrieval, E-mail, ``Electronic Conferencing'' und fachspezifische Informationsnetze in exemplarischer Form für Wissenschaft und Industrie - auch für andere Fachgebiete.