Finite-Volume-Particle Methods for Models of Transport of Pollutant in Shallow Water

We present a new hybrid numerical method for computing the transport of a passive pollutant by a flow. The flow is modeled by the Saint-Venant system of shallow water equations and the pollutant propagation is described by a transport equation. The idea behind the new finite-volume-particle (FVP) method is to use different schemes for the flow and the pollution computations: the shallow water equations are numerically integrated using a finite-volume scheme, while the transport equation is solved by a particle method. This way the specific advantages of each scheme are utilized at the right place. This results in a significantly enhanced resolution of the computed solution     

Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's tactile sensor. This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.Supported in part by the National Science Foundation Grant DMC-8519542.     

Compiling OR-parallelism into AND-parallelism

This paper suggests a general method for compiling OR-parallelism into AND-parallelism. An interpreter for an AND/OR-parallel language written in the AND-parallel subset of the language induces a source-to-source transformation from the full language into the AND-parallel subset. This transformation can be identified and implemented as a special purpose compiler or applied using a general purpose partial evaluator. The method is demonstrated to compile a variant of Concurrent Prolog into an AND-parallel subset of the language called Flat Concurrent Prolog (FCP). It is also shown applicable to the compilation of OR-parallel Prolog to FCP. The transformation identified is simple and efficient. The performance of the method is discussed in the context of programming examples. These compare well with conventionally compiled Prolog programs.     

Heuristics for rapidly four-coloring large planar graphs

We present several algorithms for rapidly four-coloring large planar graphs and discuss the results of extensive experimentation with over 140 graphs from two distinct classes of randomly generated instances having up to 128,000 vertices. Although the algorithms can potentially require exponential time, the observed running times of our more sophisticated algorithms are linear in the number of vertices over the range of sizes tested. The use of Kempe chaining and backtracking together with a fast heuristic which usually, but not always, resolves impasses gives us hybrid algorithms that: (1) successfully four-color all our test graphs, and (2) in practice run, on average, only twice as slow as the well-known, nonexact, simple to code, Θ(n) saturation algorithm of Brélaz.     

Superfluid density and critical current of3He in confined geometries

Superfluid³He in severely confined geometries is studied in the Ginzburg-Landau limit. Both A and B phases are analyzed in narrow slabs and in small cylinders. Physically measurable quantities include the superfluid density and the critical current, which are significantly suppressed by the boundaries. Related alterations in the phase diagram are also considered. For small lateral dimensions, the A phase can be favored even well below the polycritical pressure.     

Opening the AC-unification race

This note reports about the implementation of AC-unification algorithms, based on the variable-abstraction method of Stickel and on the constant-abstraction method of Livesey, Siekmann, and Herold. We give a set of 105 benchmark examples and compare execution times for implementations of the two approaches. This documents for other researchers what we consider to be the state-of-the-art performance for elementary AC-unification problems.     

Buchbesprechungen

Ohne Zusammenfassung     

Metacomputing in practice: a distributed compute server for pharmaceutical industry

We describe a distributed high-performance compute server that has been implemented for running compute-intensive applications on a mixture of HPC systems interconnected by Inter-and Intranet. With a practical industrial background, our work focusses on high availability, efficient job load balancing, security, and the easy integration of HPC computing into the daily work-flow at pharmaceutical companies.

The work was done in the course of the ESPRIT project P A Distributed Pharmaceutical Application Server The client software is implemented in Java. All results are displayed in a web browser and can be forwarded to the next stage of applications used in the drug design cycle. The server software handles the job load balancing between the participating HPC nodes and is capable of managing multi-site applications.

Our environment currently supports four key applications that are used in rational drug design and drug target identification. They range from the automatic functional annotation of protein sequences to three-dimensional protein structure prediction tools and protein comparison applications.