Revised and extended Utilities for the Ratip package

During the last years, the Ratip package has been found useful for calculating the excitation and decay properties of free atoms. Based on the (relativistic) multiconfiguration Dirac-Fock method, this program is used to obtain accurate predictions of atomic properties and to analyze many recent experiments. The daily work with this package made an extension of its Utilities [S. Fritzsche, Comput. Phys. Comm. 141 (2001) 163] desirable in order to facilitate the data handling and interpretation of complex spectra. For this purpose, we make available an enlarged version of the Utilities which mainly supports the comparison with experiment as well as large Auger computations. Altogether 13 additional tasks have been appended to the program together with a new menu structure to improve the interactive control of the program.

Program summary

Title of program: RATIPCatalogue identifier: ADPD_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADPD_v2_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions: noneReference in CPC to previous version: S. Fritzsche, Comput. Phys. Comm. 141 (2001) 163Catalogue identifier of previous version: ADPDAuthors of previous version: S. Fritzsche, Department of Physics, University of Kassel, Heinrich-Plett-Strasse 40, D-34132 Kassel, GermanyDoes the new version supersede the original program?: yesComputer for which the new version is designed and others on which it has been tested: IBM RS 6000, PC Pentium II-IVInstallations: University of Kassel (Germany), University of Oulu (Finland)Operating systems: IBM AIX, Linux, UnixProgram language used in the new version: ANSI standard Fortran 90/95Memory required to execute with typical data: 300 kBNo. of bits in a word: All real variables are parameterized by a selected kind parameter and, thus, can be adapted to any required precision if supported by the compiler. Currently, the kind parameter is set to double precision (two 32-bit words) as used also for other components of the Ratip package [S. Fritzsche, C.F. Fischer, C.Z. Dong, Comput. Phys. Comm. 124 (2000) 341; G. Gaigalas, S. Fritzsche, Comput. Phys. Comm. 134 (2001) 86; S. Fritzsche, Comput. Phys. Comm. 141 (2001) 163; S. Fritzsche, J. Elec. Spec. Rel. Phen. 114-116 (2001) 1155]No. of lines in distributed program, including test data, etc.:231 813No. of bytes in distributed program, including test data, etc.: 3 977 387Distribution format: tar.gzip fileNature of the physical problem: In order to describe atomic excitation and decay properties also quantitatively, large-scale computations are often needed. In the framework of the Ratip package, the Utilities support a variety of (small) tasks. For example, these tasks facilitate the file and data handling in large-scale applications or in the interpretation of complex spectra.Method of solution: The revised Utilities now support a total of 29 subtasks which are mainly concerned with the manipulation of output data as obtained from other components of the Ratip package. Each of these tasks are realized by one or several subprocedures which have access to the corresponding modules of the main components. While the main menu defines seven groups of subtasks for data manipulations and computations, a particular task is selected from one of these group menus. This allows to enlarge the program later if technical support for further tasks will become necessary. For each selected task, an interactive dialog about the required input and output data as well as a few additional information are printed during the execution of the program.Reasons for the new version: The requirement for enlarging the previous version of the Utilities [S. Fritzsche, Comput. Phys. Comm. 141 (2001) 163] arose from the recent application of the Ratip package for large-scale radiative and Auger computations. A number of new subtasks now refer to the handling of Auger amplitudes and their proper combination in order to facilitate the interpretation of complex spectra. A few further tasks, such as the direct access to the one-electron matrix elements for some given set of orbital functions, have been found useful also in the analysis of data.Summary of revisions: extraction and handling of atomic data within the framework of Ratip. With the revised version, we now ‘add’ another 13 tasks which refer to the manipulation of data files, the generation and interpretation of Auger spectra, the computation of various one- and two-electron matrix elements as well as the evaluation of momentum densities and grid parameters. Owing to the rather large number of subtasks, the main menu has been divided into seven groups from which the individual tasks can be selected very similarly as before.Typical running time: The program responds promptly for most of the tasks. The responding time for some tasks, such as the generation of a relativistic momentum density, strongly depends on the size of the corresponding data files and the number of grid points.Unusual features of the program: A total of 29 different tasks are supported by the program. Starting from the main menu, the user is guided interactively through the program by a dialog and a few additional explanations. For each task, a short summary about its function is displayed before the program prompts for all the required input data.     

Approximation of min coloring by moderately exponential algorithms

We study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential space), better than those of exact computation. Study of approximation is performed with respect to optimality measures, the minimum number of used colors and the maximum number of unused colors.     

TiReX: Replica-exchange molecular dynamics using Tinker

We present a driver program for performing replica-exchange molecular dynamics simulations with the Tinker package. Parallelization is based on the Message Passing Interface, with every replica assigned to a separate process. The algorithm is not communication intensive, which makes the program suitable for running even on loosely coupled cluster systems. Particular attention is paid to the practical aspects of analyzing the program output.

Program summary

Program title: TiReXCatalogue identifier: AEEK_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEK_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 43 385No. of bytes in distributed program, including test data, etc.: 502 262Distribution format: tar.gzProgramming language: Fortran 90/95Computer: Most UNIX machinesOperating system: LinuxHas the code been vectorized or parallelized?: parallelized with MPIClassification: 16.13External routines: TINKER version 4.2 or 5.0, built as a libraryNature of problem: Replica-exchange molecular dynamics.Solution method: Each replica is assigned to a separate process; temperatures are swapped between replicas at regular time intervals.Running time: The sample run may take up to a few minutes.     

Proofs of randomized algorithms in Coq

Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions.We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.     

Gray codes for reflectable languages

We classify a type of language called a reflectable language. We then develop a generic algorithm that can be used to list all strings of length n for any reflectable language in Gray code order. The algorithm generalizes Gray code algorithms developed independently for k-ary strings, restricted growth strings, and k-ary trees, as each of these objects can be represented by a reflectable language. Finally, we apply the algorithm to open meandric systems which can also be represented by a reflectable language.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Range and Roots: Two common patterns for specifying and propagating counting and occurrence constraints

We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We design specialised propagation algorithms for these two patterns. Counting and occurrence constraints specified using these patterns thus directly inherit a propagation algorithm. To illustrate the capabilities of the Range and Roots constraints, we specify a number of global constraints taken from the literature. Preliminary experiments demonstrate that propagating counting and occurrence constraints using these two patterns leads to a small loss in performance when compared to specialised global constraints and is competitive with alternative decompositions using elementary constraints.     

A combinatorial property of the factor poset of a word

We prove the following interesting combinatorial property of the poset of the factors of a word. Let w be a word and n=G_w+2, where G_w is the maximal length of a repeated factor of w. If v is any word such that the posets of the factors of v and of w up to length n are isomorphic, then v can be obtained by renaming the letters of w or of the reversal of w.     

Pomwig: Herwig for diffractive interactions

We have modified the Herwig event generator to incorporate diffractive interactions. All standard Herwig hard subprocesses are available.     

Kanga(ROO): Handling the micro-DST of the BaBar experiment with ROOT

A system based on ROOT for handling the micro-DST of the BaBar experiment is described. The purpose of the Kanga system is to have micro-DST data available in a format well suited for data distribution within a world-wide collaboration with many small sites. The design requirements, implementation and experience in practice after three years of data taking by the BaBar experiment are presented.     

udkm1Dsim—A simulation toolkit for 1D ultrafast dynamics in condensed matter

The udkm1Dsim  toolbox is a collection of matlab (MathWorks Inc.) classes and routines to simulate the structural dynamics and the according X-ray diffraction response in one-dimensional crystalline sample structures upon an arbitrary time-dependent external stimulus, e.g. an ultrashort laser pulse. The toolbox provides the capabilities to define arbitrary layered structures on the atomic level including a rich database of corresponding element-specific physical properties. The excitation of ultrafast dynamics is represented by an N$N$-temperature model which is commonly applied for ultrafast optical excitations. Structural dynamics due to thermal stress are calculated by a linear-chain model of masses and springs. The resulting X-ray diffraction response is computed by dynamical X-ray theory. The udkm1Dsim  toolbox is highly modular and allows for introducing user-defined results at any step in the simulation procedure.     

-XSummer- Transcendental functions and symbolic summation in Form

Harmonic sums and their generalizations are extremely useful in the evaluation of higher-order perturbative corrections in quantum field theory. Of particular interest have been the so-called nested sums, where the harmonic sums and their generalizations appear as building blocks, originating for example, from the expansion of generalized hypergeometric functions around integer values of the parameters. In this paper we discuss the implementation of several algorithms to solve these sums by algebraic means, using the computer algebra system Form.

Program summary

Title of program:XSummerCatalogue identifier:ADXQ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXQ_v1_0Program obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandLicense:GNU Public License and Form LicenseComputers:allOperating system:allProgram language:FormMemory required to execute:Depending on the complexity of the problem, recommended at least 64 MB RAMNo. of lines in distributed program, including test data, etc.:9854No. of bytes in distributed program, including test data, etc.:126 551Distribution format:tar.gzOther programs called:noneExternal files needed:noneNature of the physical problem:Systematic expansion of higher transcendental functions in a small parameter. The expansions arise in the calculation of loop integrals in perturbative quantum field theory.Method of solution:Algebraic manipulations of nested sums.Restrictions on complexity of the problem:Usually limited only by the available disk space.Typical running time:Dependent on the complexity of the problem.     

A component- and push-based architectural style for ajax applications

A new breed of web application, dubbed ajax, is emerging in response to a limited degree of interactivity in large-grain stateless Web interactions. At the heart of this new approach lies a single page interaction model that facilitates rich interactivity. Also push-based solutions from the distributed systems are being adopted on the web for ajax applications. The field is, however, characterized by the lack of a coherent and precisely described set of architectural concepts. As a consequence, it is rather difficult to understand, assess, and compare the existing approaches. We have studied and experimented with several ajax frameworks trying to understand their architectural properties. In this paper, we summarize four of these frameworks and examine their properties and introduce the spiar architectural style which captures the essence of ajax applications. We describe the guiding software engineering principles and the constraints chosen to induce the desired properties. The style emphasizes user interface component development, intermediary delta-communication between client/server components, and push-based event notification of state changes through the components, to improve a number of properties such as user interactivity, user-perceived latency, data coherence, and ease of development. In addition, we use the concepts and principles to discuss various open issues in ajax frameworks and application development.     

Helac-Phegas: A generator for all parton level processes

The updated version of the Helac-Phegas¹ event generator is presented. The matrix elements are calculated through Dyson-Schwinger recursive equations using color connection representation. Phase-space generation is based on a multichannel approach, including optimization. Helac-Phegas generates parton level events with all necessary information, in the most recent Les Houches Accord format, for the study of any process within the Standard Model in hadron and lepton colliders.

New version program summary

Program title: HELAC-PHEGASCatalogue identifier: ADMS_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADMS_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 35 986No. of bytes in distributed program, including test data, etc.: 380 214Distribution format: tar.gzProgramming language: FortranComputer: AllOperating system: LinuxClassification: 11.1, 11.2External routines: Optionally Les Houches Accord (LHA) PDF Interface library (http://projects.hepforge.org/lhapdf/)Catalogue identifier of previous version: ADMS_v1_0Journal reference of previous version: Comput. Phys. Comm. 132 (2000) 306Does the new version supersede the previous version?: Yes, partlyNature of problem: One of the most striking features of final states in current and future colliders is the large number of events with several jets. Being able to predict their features is essential. To achieve this, the calculations need to describe as accurately as possible the full matrix elements for the underlying hard processes. Even at leading order, perturbation theory based on Feynman graphs runs into computational problems, since the number of graphs contributing to the amplitude grows as n!.Solution method: Recursive algorithms based on Dyson-Schwinger equations have been developed recently in order to overcome the computational obstacles. The calculation of the amplitude, using Dyson-Schwinger recursive equations, results in a computational cost growing asymptotically as 3n, where n is the number of particles involved in the process. Off-shell subamplitudes are introduced, for which a recursion relation has been obtained allowing to express an n-particle amplitude in terms of subamplitudes, with 1-, 2-, …  up to (n−1) particles. The color connection representation is used in order to treat amplitudes involving colored particles. In the present version HELAC-PHEGAS can be used to efficiently obtain helicity amplitudes, total cross sections, parton-level event samples in LHA format, for arbitrary multiparticle processes in the Standard Model in leptonic, and pp collisions.Reasons for new version: Substantial improvements, major functionality upgrade.Summary of revisions: Color connection representation, efficient integration over PDF via the PARNI algorithm, interface to LHAPDF, parton level events generated in the most recent LHA format, k_⊥ reweighting for Parton Shower matching, numerical predictions for amplitudes for arbitrary processes for phase-space points provided by the user, new user interface and the possibility to run over computer clusters.Running time: Depending on the process studied. Usually from seconds to hours.References:

[1]

A. Kanaki, C.G. Papadopoulos, Comput. Phys. Comm. 132 (2000) 306.

[2]

C.G. Papadopoulos, Comput. Phys. Comm. 137 (2001) 247.

     

Parallel and distributed local search in COMET

The availability of commodity multiprocessors and high-speed networks of workstations offer significant opportunities for addressing the increasing computational requirements of optimization applications. To leverage these potential benefits, it is important, however, to make parallel and distributed processing easily accessible to a wide audience of optimization programmers. This paper addresses this challenge by proposing parallel and distributed programming abstractions that keep the distance from sequential local search algorithms as small as possible. The abstractions, including parallel loops, interruptions, thread pools, and shared objects, are compositional and cleanly separate the optimization program and the parallel instructions. They have been evaluated experimentally on a variety of applications, including warehouse location and coloring, for which they provide significant speedups.     

A note on the online First-Fit algorithm for coloring k-inductive graphs

In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(klogn) colors for k-inductive graphs. In this note we provide a very short proof of this fact.