Library

Description: Line integral convolution (LIC) has become a well-known and popular method for visualizing vector fields. The method works by convolving a random input texture along the integral curves of the vector field. In order to accelerate image synthesis significantly, an efficient algorithm has been proposed that utilizes pixel coherence in field line direction. This algorithm, called ``fast LIC'', originally was restricted to simple box-type filter kernels. Here we describe a generalization of fast LIC for piecewise polynomial filter kernels. Expanding the filter kernels in terms of truncated power functions allows us to exploit a certain convolution theorem. The convolution integral is expressed as a linear combination of repeated integrals (or repeated sums in the discrete case). Compared to the original algorithm the additional expense for using higher order filter kernels, e.g.\ of B-spline type, is very low. Such filter kernels produce smoother, less noisier results than a box filter. This is evident from visual investigation, as well as from analysis of pixel correlations. Thus, our method represents a useful extension of the fast LIC algorithm for the creation of high-quality LIC images.

Description: Three different approaches for the determination of conservation laws of differential equations are presented. For three corresponding REDUCE computer algebra programs CONLAW1/2/3 the necessary subroutines are discribed. One of them simplifies general solutions of overdetermined PDE systems so that all remaining free functions and constants correspond to independent conservation laws. It determines redundant functions and constants in differential expressions and is equally useful for the determination of symmetries or the fixing of gauge freedom in differential expressions.

Description: A wide range of free boundary problems occurring in engineering andindustry can be rewritten as a minimization problem for astrictly convex, piecewise smooth but non--differentiable energy functional.The fast solution of related discretized problemsis a very delicate question, because usual Newton techniquescannot be applied. We propose a new approach based on convex minimization and constrained Newton type linearization. While convex minimization provides global convergence of the overall iteration, the subsequent constrained Newton type linearization is intended to accelerate the convergence speed. We present a general convergence theory and discuss several applications.

Description: We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data.

Description: We derive the fourth order $q$-difference equation satisfied by the first associated of the $q$-classical orthogonal polynomials. The coefficients of this equation are given in terms of the polynomials $\; \sigma\;$ and $\;\tau\;$ which appear in the $q$-Pearson difference equation $\;\; D_q(\sigma\,\rho)=\tau\,\rho\;$ defining the weight $\rho$ of the $q$-classical orthogonal polynomials inside the $q$-Hahn tableau.

Description: KARDOS solves nonlinear evolution problems in 1, 2, and 3D. An adaptive multilevel finite element algorithm is used to solve the spatial problems arising from linearly implicit discretization methods in time. Local refinement and derefinement techniques are used to handle the development of the mesh over time. The software engineering techniques used to implement the modules of the KASKADE toolbox are reviewed and their application to the extended problem class is described. A notification system and dynamic construction of records are discussed and their values for the implementation of a mesh transfer operation are shown. The need for low-level and high--level interface elements of a module is discussed for the assembling procedure of KARDOS. At the end we will summarize our experiences.

Description: Dynamical systems with two well-separated time-scales are investigated using normal form theory. Exponential estimates for the normal form truncation error are derived and applied to the numerical integration of differential equations (backward error analysis) and the reduction of highly oscillatory Hamiltonian systems (constrained dynamics and correcting potentials). The theoretical results are used to formulate new algorithms for the time integration of conservative Hamiltonian systems (projected multiple time stepping, soft constraints, rigid bodies, symplectic variable step-size methods).

Description: We consider a $s$-server system with two FCFS queues, where the arrival rates at the queues and the service rate may depend on the number $n$ of customers being in service or in the first queue, but the service rate is assumed to be constant for $n〉s$. The customers in the first queue are impatient. If the offered waiting time exceeds a random maximal waiting time $I$, then the customer leaves the first queue after time $I$. If $I$ is less than a given deterministic time then he leaves the system else he transits to the end of the second queue. The customers in the first queue have priority. The service of a customer from the second queue will be started if the first queue is empty and more than a given number of servers become idle. For the model being a generalization of the $M(n)/M(n)/s\!+\!GI$ system balance conditions for the density of the stationary state process are derived yielding the stability conditions and the probabilities that precisely $n$ customers are in service or in the first queue. For obtaining performance measures for the second queue a system approximation basing on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server. For an important special case a stochastic decomposition is derived illuminating the connection to the dynamics of the $M(n)/M(n)/s\!+\!GI$ system.

Description: Let $G=(V,E)$ be a simple graph and $s$ and $t$ be two distinct vertices of $G$. A path in $G$ is called $\ell$-bounded for some $\ell\in\mathbb{N}$, if it does not contain more than $\ell$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint $\ell$-bounded $s,t$-paths in $G$. First, we show that computing the maximum number of vertex-disjoint $\ell$-bounded $s,t$-paths is $\mathcal{AP\kern-1pt X}$--complete for any fixed length bound $\ell\geq 5$. Second, for a given number $k\in\mathbb{N}$, $1\leq k \leq |V|-1$, and non-negative weights on the edges of $G$, the problem of finding $k$ vertex-disjoint $\ell$-bounded $s,t$-paths with minimal total weight is proven to be $\mathcal{NPO}$--complete for any length bound $\ell\geq 5$. Furthermore, we show that, even if $G$ is complete, it is $\mathcal{NP}$--complete to approximate the optimal solution value of this problem within a factor of $2^{\langle\phi\rangle^\epsilon}$ for any constant $0〈\epsilon〈1$, where $\langle\phi\rangle$ denotes the encoding size of the given problem instance $\phi$. We prove that these results are tight in the sense that for lengths $\ell\leq 4$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to $\ell$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results.

Description: We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems.

Description: We develop a two-stage stochastic programming model with integer first-stage and mixed-integer recourse for solving the unit commitment problem in power generation in the presence of uncertainty of load profiles. The solution methodology rests on a novel scenario decomposition method for stochastic integer programming. This method combines Lagrangian relaxation of non-anticipativity constraints with branch-and-bound. It can be seen as a decomposition algorithm for large-scale mixed-integer linear programs with block-angular structure. With realistic data from a German utility we validate our model and carry out test runs. Sizes of these problems go up to 20.000 integer and 150.000 continuous variables together with up to 180.000 constraints.

Description: The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve.

Description: A variable step-size, semi-explicit variant of the explicit Störmer-Verlet method has been proposed for the time-reversible integration of Newton's equations of motion by Huang & Leimkuhler. Here we propose a fully explicit version of this approach applicable to explicit and symmetric integration methods for general time-reversible differential equations. As applications, we discuss the variable step-size, time-reversible, and fully explicit integration of rigid body motion and reversible Nos\'e-Hoover dynamics.

Description: The paper surveys recent progress in a joint mathematical-medical project on cancer therapy planning. Within so-called regional hyperthermia the computational task is to tune a set of coupled radiofrequency antennas such that a carefully measured tumor is locally heated, but any outside hot spots are avoided. A mathematical model of the whole clinical system -- air, applicator with antennas, water bolus, individual patient body -- involves Maxwell's equations in inhomogeneous media and a parabolic bioheat transfer equation, which represents a simplified model of heat transfer in the human body (ignoring strong blood vessel heat transport). Both PDEs need to be computed fast and to medical reliability (!) on a workstation within a clinical environment. This requirement triggered a series of new algorithmic developments to be reported here, among which is an adaptive multilevel FEM for Maxwell's equations, which dominates the numerical simulation time. In total, however, the main bulk of computation time (see Table 3 in Section 4 below) still goes into segmentation -- a necessary preprocessing step in the construction a 3D virtual patient from the input of a stack of 2D computed tomograms (left out here).

Description: When attempting to compute unsteady, variable density flows at very small or zero Mach number using a standard finite volume compressible flow solver one faces at least the following difficulties: (i) Spatial pressure variations vanish as the Mach number $M \rightarrow 0$, but they do affect the velocity field at leading order; (ii) the resulting spatial homogeneity of the leading order pressure implies an elliptic divergence constraint for the energy flux; (iii) violation of this constraint would crucially affect the transport of mass, thereby disabling a code to properly advect even a constant density distribution. A previous companion paper derived the above observations from a single time - multiple length scale asymptotic analysis for $M \ll 1$, applied to the conservation form of the governing equations and assuming an ideal gas with constant specific heats. The paper then restricted to weakly compressible one-dimensional flows and introduced a semi-implicit extension of a compressible flow solver, designed to handle the interaction of long wavelength acoustics with small scale, large amplitude density fluctuations. In the present paper we concentrate on the limit of zero Mach number for multi-dimensional, variable density flows. The construction of numerical fluxes for all conserved quantities involves: An explicit upwind step (1) yielding predictions for the nonlinear convective flux components. This procedure still neglects the influence of pressure gradients on the convective fluxes during the time step. Suitable corrections are applied in step (2), which guarantees compliance of the convective fluxes with the divergence constraint. This step requires the solution of a Poisson-type equation to obtain the relevant pressure gradients. Step (3), which requires the solution of a second Poisson-type equation, yields the yet unknown (non-convective) pressure contribution to the total flux of momentum. The final, cell centered velocity field exactly satisfies a discrete divergence constraint consistent with the asymptotic limit. Notice that step (1) can be done by any standard finite volume compressible flow solver and that the input to steps (2) and (3) involves solely the fluxes from step (1), but is independent on how these were obtained. Thus, we claim that our approach allows any such solver to be extended to simulate incompressible flows. Extensions to the weakly compressible regime $0 〈 M \ll 1$, reactive flows and more complex equations of state will be addressed in follow-up publications.

Description: In the clinical cancer therapy of regional hyperthermia nonlinear perfusion effects inside and outside the tumor seem to play a not negligible role. A stationary model of such effects leads to a nonlinear Helmholtz term within an elliptic boundary value problem. The present paper reports about the application of a recently designed adaptive multilevel FEM to this problem. For several 3D virtual patients, nonlinear versus linear model is studied. Moreover, the numerical efficiency of the new algorithm is compared with a former application of an adaptive FEM to the corresponding instationary model PDE.

Description: In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.

Description: The paper presents a new algorithmic approach for multistage stochastic programs which are seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within a primal-dual interior point method. Convergence is drastically enhanced by a successive refinement technique providing both primal and dual initial estimates. Test runs on a multistage portfolio selection problem demonstrate the performance of the method.

Description: This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} .

Description: This report presents a fast data assimilation method to produce an interpolating time and space temperature distribution for steel members subject to fire testing. The method assimilates collected temperature data into the numerical integration of the heat equation. This physically based method also allows the computation of lateral and axial heat flux into and inside the member.

Description: In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service.

Description: Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide.

Description: Segmentation tools in medical imaging are either based on editing geometric curves or on the assignment of region labels to image voxels. While the first approach is well suited to describe smooth contours at subvoxel accuracy, the second approach is conceptually more simple and guarantees a unique classification of image areas. However, contours extracted from labeled images typically exhibit strong staircase artifacts and are not well suited to represent smooth tissue boundaries. In this paper we describe how this drawback can be circumvented by supplementing region labels with additional weights. We integrated our approach into an interactive segmentation system providing a well-defined set of manual and semi-automatic editing tools. All tools update both region labels as well as the corresponding weights simultaneously, thus allowing one to define segmentation results at high resolution. We applied our techniques to generate 3D polygonal models of anatomical structures.

Description: The Monte Carlo simulation of the dynamics of complex molecules produces trajectories with a large number of different configurations to sample configuration space. It is expected that these configurations can be classified into a small number of conformations representing essential changes in the shape of the molecule. We present a method to visualize these conformations by point sets in the plane based on a geometrical distance measure between individual configurations. It turns out that different conformations appear as well-separated point sets. The method is further improved by performing a cluster analysis of the data set. The point-cluster representation is used to control a three-dimensional molecule viewer application to show individual configurations and conformational changes. The extraction of essential coordinates and visualization of molecular shape is discussed.

Description: iTe is an easy to use, interactive authoring tool for LaTeX and TeX documents. With iTe, it is possible to select arbitrary display fragments such as figures, equations, labels, captions, etc. These fragments can then be freely moved, rotated and scaled.

Description: The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far.

Description: \noindent An immediate generalization of the classical McKay correspondence for Gorenstein quotient spaces $\Bbb{C}^{r}/G$ in dimensions $r\geq 4$ would primarily demand the existence of projective, crepant, full desingularizations. Since this is not always possible, it is natural to ask about special classes of such quotient spaces which would satisfy the above property. In this paper we give explicit necessary and sufficient conditions under which 2-parameter series of Gorenstein cyclic quotient singularities have torus-equivariant resolutions of this specific sort in all dimensions.

Description: Fully adaptive solutions of imcompressible flow problems employing the discretization sequence first in time then in space are presented. The time discretization is done by linearly implicit one--step methods possibly of high order with automatic step size control. A posteriori error estimates for the stabilized finite element discretization in space are obtained by solving local Dirichlet problems with higher accuracy. Once those estimates have been computed, we are able to control time and space grids with respect to required tolerances and necessary computational work. The devised method is applied to two benchmark problems in 2D.

Description: This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view.

Description: Multistage stochastic programs can be seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm.

Description: The transient heating in an unsymmetrical coated hot--strip sensor was simulated with a self--adaptive finite element method. The first tests of this model show that it can determine with a small error the thermal conductivity of liquids, from the transient temperature rise in the hot--strip, deposited in a substrate and coated by an alumina spray.

Description: For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed.

Description: Two polynomial expansions of the time-evolution superoperator to directly integrate Markovian Liouville-von Neumann (LvN) equations for quantum open systems, namely the Newton interpolation and the Faber approximation, are presented and critically compared. Details on the numerical implementation including error control, and on the performance of either method are given. In a first physical application, a damped harmonic oscillator is considered. Then, the Faber approximation is applied to compute a condensed phase absorption spectrum, for which a semi--analytical expression is derived. Finally, even more general applications are discussed. In all applications considered here it is found that both the Newton and Faber integrators are fast, general, stable, and accurate.

Description: Mixed quantum--classical models have attracted considerable interest due to the expectation that they correctly describe non--adiabatic processes of full quantum dynamics. One of these models, the so--called QCMD model, represents most degrees of freedom of the molecular system by the means of classical mechanics but an important, small portion of the system is modeled by a wavefunction: the wavefunction is nonlinearly coupled to the classical motion via a singularly perturbed Schrödinger equation. In extension to the analysis given by F.A.~Bornemann [{\em Homogenization in Time of Singularly Perturbed Mechanical Systems}, Lecture Notes in Mathematics, no.~1687, 1998, Springer, Berlin], the article presents an asymptotic expansion up to second order in the perturbation parameter. This result allows for the construction of new models and numerical integration schemes.

Description: In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The article is concerned with the so-called QCMD model. This model describes most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of a wavefunction. We review the conditions under which the QCMD model is known to approximate the full quantum dynamical evolution of the system. In most quantum-classical simulations the {\em Born-Oppenheimer model} (BO) is used. In this model, the wavefunction is adiabatically coupled to the classical motion which leads to serious approximation deficiencies with respect to non-adiabatic effects in the fully quantum dynamical description of the system. In contrast to the BO model, the QCMD model does include non-adiabatic processes, e.g., transitions between the energy levels of the quantum system. It is demonstrated that, in mildly non-adiabatic scenarios, so-called {\em surface hopping} extensions of QCMD simulations yield good approximations of the non-adiabatic effects in full quantum dynamics. The algorithmic strategy of such extensions of QCMD is explained and the crucial steps of its realization are discussed with special emphasis on the numerical problems caused by highly oscillatory phase effects.

Description: In this thesis we develop new methods for visualizing vector fields which specifically address three design goals: accuracy, performance, and cognition. Our methods will be general-purpose and can be applied to arbitrary vector fields in two- and three-dimensional space. The methodology behind our approach is {\em texture-based visualization}. Texture-based visualization methods imitate techniques known from experimental flow visualization, namely, the observation of randomly dispersed particles or dye injection patterns. Instead of depicting individual lines or symbols, a contiguous high-resolution image or texture is generated. This texture clearly reveals the directional structure of the field. In this way intuitive insight can be obtained and even small details of the field become visible. However, it remains unclear what kind of textures are best suited for our purpose. How do we generate them? Can we apply these methods in three-dimensional space? In particular, we focus on a technique known as {\em line integral convolution} or LIC. This method turns out to be quite versatile and well-suited for visualizing many interesting vector fields. LIC images display the integral curves or field lines of a vector field at high spatial resolution. Although conceptually quite simple, line integral convolution implies a number of interesting mathematical and algorithmic questions.

Description: Diese Dissertation befaßt sich mit ganzzahligen Programmen mit 0/1 Systemen: SetPacking-, Partitioning- und Covering-Probleme. Die drei Teile der Dissertation behandeln polyedrische, algorithmische und angewandte Aspekte derartiger Modelle.

Description: Starting from the $ D_{ \omega}$-Riccati Difference equation satisfied by the Stieltjes function of a linear functional, we work out an algorithm which enables us to write the unique fourth-order difference equation satisfied by the associated of any integer order of orthogonal polynomials of the $ \Delta$-Laguerre-Hahn class. Moreover, in classical situations (Meixner, Charlier, Kravtchouk and Hahn), we give explicitely these difference equations; and from Hahn difference equation, we recover by limit process the difference equations satisfied by the associated of classical discrete orthogonal polynomials and differential equations satisfied by the associated of classical continuous orthogonal polynomials.

Description: The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.

Description: We describe an optimization process specially designed for regional hyperthermia of deep seated tumors in order to achieve desired steady--state temperature distributions. A nonlinear three--dimensional heat transfer model based on temperature--dependent blood perfusion is applied to predict the temperature. Using linearly implicit methods in time and adaptive multilevel finite elements in space, we are able to integrate efficiently the instationary nonlinear heat equation with high accuracy. Optimal heating is obtained by minimizing an integral object function which measures the distance between desired and model predicted temperatures. A sequence of minima is calculated from successively improved constant--rate perfusion models employing a damped Newton method in an inner iteration. We compare temperature distributions for two individual patients calculated on coarse and fine spatial grids and present numerical results of optimizations for a Sigma 60 Applicator of the BSD 2000 Hyperthermia System.

Description: We derive the fourth order difference equation satisfied by the associated of order $\;r\;$ of the classical orthogonal polynomials of a discrete variable.\\The coefficients of this equation are given in terms of the polynomials $\; \sigma\;$ and $\;\tau\;$ which appear in the discrete Pearson equation $\;\;\Delta(\sigma\;\rho)=\tau\;\rho\;\;$ defining the weight $\;\rho(x)\;$ of the classical discrete orthogonal polynomials.

Description: In this paper we present a short description of $q$-analogues of Gosper's, Zeilberger's, Petkov\v{s}ek's and related algorithms. Furthermore we introduce our corresponding MAPLE implementations and show how they can be applied to prove or even derive identities associated with $q$-series.

Description: The topic of the present paper bas been motivated by a recent computational approach to identify chemical conformations and conformational changes within molecular systems. After proper discretization, the conformations show up as almost invariant aggregates in reversible nearly uncoupled Markov chains. Most of the former work on this subject treated the direct problem: given the aggregates, analyze the loose coupling in connection with the computation of the stationary distribution (aggregation/disaggregation techniques). In contrast to that the present paper focuses on the inverse problem: given the system as a whole, identify the almost invariant aggregates together with the associated transition probabilites. A rather simple and robust algorithm is suggested and illustrated by its application to the n-pentane molecule.

Description: Recently, a novel concept for the computation of essential features of Hamiltonian systems (such as those arising in molecular dynamics) has been proposed. The realization of that concept was based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept based on statistical mechanics, which allows to attack realistic molecular systems. 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 hybrid Monte Carlo techniques (based on short term subtrajectories only) is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable (to be presented elsewhere). Numerical results for the n-pentane molecule are given and interpreted.

Description: This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems.

Description: Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.

Description: Representing scientific data sets efficiently on external storage usually involves converting them to a byte string representation using specialized reader/writer routines. The resulting storage files are frequently difficult to interpret without these specialized routines as they do not contain information about the logical structure of the data. Avoiding such problems usually involves heavy-weight data format libraries or data base systems. We present a simple C++ library that allows to create and access data files that store structured data. The structure of the data is described by a data type that can be built from elementary data types (integer and floating-point numbers, byte strings) and composite data types (arrays, structures, unions). An abstract data access class presents the data to the application. Different actual data file structures can be implemented under this layer. This method is particularly suited to applications that require complex data structures, e.g. molecular dynamics simulations. Extensions such as late type binding and object persistence are discussed.

Description: The paper supplies an alternative derivation of the exact boundary conditions needed for the solution of time-harmonic acoustic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior domain problem as an initial value problem with initial data given on the boundary of a disc or sphere. The solution of the exterior domain problem is obtained via Laplace transformation techniques, where the asymptotic Sommerfeld radiation condition is reformulated accordingly.