Dynamic multi-dimensional data structures based on quad- and k—d trees

Summary Quad-trees and k—d trees have been noted for their lack of dynamic properties as data structures for multi-dimensional point sets. We describe a method to insert points in a quad-tree while keeping the tree balanced that achieves an average time complexity of O(log² N) per insertion, where N is the number of updates performed on the quad-tree. We define a structure similar to a quad-tree, called a pseudo quad-tree, and show how it can be used to handle both insertions and deletions in O(log² N) average time. We also discuss how quad-trees and pseudo quadtrees can be extended for use in configurations of points in which more than one point may have a same value in some equal coordinate, without altering the earlier time bounds for insertions, deletions and queries. Similar algorithms are given for k—d trees and the same average time bounds for insertion and deletion are achieved.The work of this author was partially supported by the Netherlands Organization for the Advancement of Pure Research (ZWO).     

Regular Model Checking Using Inference of Regular Languages

Regular model checking is a method for verifying infinite-state systems based on coding their configurations as words over a finite alphabet, sets of configurations as finite automata, and transitions as finite transducers. We introduce a new general approach to regular model checking based on inference of regular languages. The method builds upon the observation that for infinite-state systems whose behaviour can be modelled using length-preserving transducers, there is a finite computation for obtaining all reachable configurations up to a certain length n. These configurations are a (positive) sample of the reachable configurations of the given system, whereas all other words up to length n are a negative sample. Then, methods of inference of regular languages can be used to generalize the sample to the full reachability set (or an overapproximation of it). We have implemented our method in a prototype tool which shows that our approach is competitive on a number of concrete examples. Furthermore, in contrast to all other existing regular model checking methods, termination is guaranteed in general for all systems with regular sets of reachable configurations. The method can be applied in a similar way to dealing with reachability relations instead of reachability sets too.     

A C-code for the double folding interaction potential of two spherical nuclei

We present a C-code designed to obtain the nucleus-nucleus potential by using the double folding model (DFM) and in particular to find the Coulomb barrier. The program calculates the nucleus-nucleus potential as a function of the distance between the centers of mass of colliding nuclei. The most important output parameters are the Coulomb barrier energy and the radius. Since many researchers use a Woods-Saxon profile for the nuclear term of the potential we provide an option in our code for fitting the DFM potential by such a profile.

Program summary

Program title: DFMSPHCatalogue identifier: AEFH_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEFH_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.: 5929No. of bytes in distributed program, including test data, etc.: 115 740Distribution format: tar.gzProgramming language: CComputer: PCOperating system: Windows XP (with the GCC-compiler version 2)RAM: Below 10 MbyteClassification: 17.9Nature of problem: The code calculates in a semimicroscopic way the bare interaction potential between two colliding spherical nuclei as a function of the center of mass distance. The height and the position of the Coulomb barrier are found. The calculated potential is approximated by a conventional Woods-Saxon profile near the barrier. Dependence of the barrier parameters upon the characteristics of the effective NN forces (like, e.g. the range of the exchange part of the nuclear term) can be investigated.Solution method: The nucleus-nucleus potential is calculated using the double folding model with the Coulomb and the effective M3Y NN interactions. For the direct parts of the Coulomb and the nuclear terms, the Fourier transform method is used. In order to calculate the exchange parts the density matrix expansion method is applied.Running time: Less than 1 minute using a PC with a 1.60 GHz processor.     

Fast agglomerative clustering using information of k-nearest neighbors

In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are found for them. The number of distance calculations for our method is O(N²), where N is the number of data points. To further reduce the computational complexity of the proposed algorithm, some available fast search approaches are used. Compared to available approaches, our proposed algorithm can reduce the computing time and number of distance calculations significantly. Compared to FPNN, our method can reduce the computing time by a factor of about 26.8 for the data set from a real image. Compared with PMLFPNN, our approach can reduce the computing time by a factor of about 3.8 for the same data set.     

Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

Molecular dynamics for long-range interacting systems on graphic processing units

We present implementations of the numerical integration of systems with long-range interactions on graphic processing units for three N$N$-body models with long-range interactions of general interest: the Hamiltonian Mean Field, Ring and two-dimensional self-gravitating models. We discuss the algorithms, speedups and errors using one and two GPU units. Speedups can be as high as 140 compared to a serial code, and the overall relative error in the total energy is of the same order of magnitude as for the CPU code. The number of particles used in the tests range from 10,000 to 50,000,000 depending on the model.     

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O(N ⁴) processors. Here we show that these problems can be solved in constant time using only O(N ²) processors on the BSR model (N is the number of vertices of the graph G). Therefore, our algorithms are more work-efficient. These new results suggest that many other problems in graph theory can be solved in constant time using the BSR model.     

Implementation of particle-in-cell stellar dynamics codes on the connection machine-2

The development of massively parallel supercomputers provides a unique opportunity to advance the state of the art inN-body simulations. TheseN-body codes are of great importance for simulations in stellar dynamics and plasma physics. For systems with long-range forces, such as gravity or electromagnetic forces, it is important to increase the number of particles toN 10⁷ particles. Significantly improved modeling ofN body systems can be expected by increasingN, arising from a more realistic representation of physical transport processes involving particle diffusion and energy and momentum transport. In addition, it will be possible to guarantee that physically significant portions of complex physical systems, such as Lindblad resonances of galaxies or current sheets in magnetospheres, will have an adequate population of particles for a realistic simulation. Particle-mesh (PM) and particle-particle particle-mesh (P³M) algorithms present the best prospects for the simulation of large-scaleN-body systems. As an example we present a two-dimensional PM simulation of a disk galaxy that we have developed on the Connection Machine-2, a massively parallel boolean hypercube supercomputer. The code is scalable to any CM-2 configuration available and, on the largest configuration, simulations withN = 128 M = 2²⁷ particles are possible in reasonable run times.     

The MOLDY short-range molecular dynamics package

We describe a parallelised version of the MOLDY molecular dynamics program. This Fortran code is aimed at systems which may be described by short-range potentials and specifically those which may be addressed with the embedded atom method. This includes a wide range of transition metals and alloys. MOLDY provides a range of options in terms of the molecular dynamics ensemble used and the boundary conditions which may be applied. A number of standard potentials are provided, and the modular structure of the code allows new potentials to be added easily. The code is parallelised using OpenMP and can therefore be run on shared memory systems, including modern multicore processors. Particular attention is paid to the updates required in the main force loop, where synchronisation is often required in OpenMP implementations of molecular dynamics. We examine the performance of the parallel code in detail and give some examples of applications to realistic problems, including the dynamic compression of copper and carbon migration in an iron–carbon alloy.

Program summary

Program title: MOLDYCatalogue identifier: AEJU_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEJU_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: GNU General Public License version 2No. of lines in distributed program, including test data, etc.: 382 881No. of bytes in distributed program, including test data, etc.: 6 705 242Distribution format: tar.gzProgramming language: Fortran 95/OpenMPComputer: AnyOperating system: AnyHas the code been vectorised or parallelized?: Yes. OpenMP is required for parallel executionRAM: 100 MB or moreClassification: 7.7Nature of problem: Moldy addresses the problem of many atoms (of order 10⁶) interacting via a classical interatomic potential on a timescale of microseconds. It is designed for problems where statistics must be gathered over a number of equivalent runs, such as measuring thermodynamic properities, diffusion, radiation damage, fracture, twinning deformation, nucleation and growth of phase transitions, sputtering etc. In the vast majority of materials, the interactions are non-pairwise, and the code must be able to deal with many-body forces.Solution method: Molecular dynamics involves integrating Newton?s equations of motion. MOLDY uses verlet (for good energy conservation) or predictor–corrector (for accurate trajectories) algorithms. It is parallelised using open MP. It also includes a static minimisation routine to find the lowest energy structure. Boundary conditions for surfaces, clusters, grain boundaries, thermostat (Nose), barostat (Parrinello–Rahman), and externally applied strain are provided. The initial configuration can be either a repeated unit cell or have all atoms given explictly. Initial velocities are generated internally, but it is also possible to specify the velocity of a particular atom. A wide range of interatomic force models are implemented, including embedded atom, Morse or Lennard-Jones. Thus the program is especially well suited to calculations of metals.Restrictions: The code is designed for short-ranged potentials, and there is no Ewald sum. Thus for long range interactions where all particles interact with all others, the order-N scaling will fail. Different interatomic potential forms require recompilation of the code.Additional comments: There is a set of associated open-source analysis software for postprocessing and visualisation. This includes local crystal structure recognition and identification of topological defects.Running time: A set of test modules for running time are provided. The code scales as order N. The parallelisation shows near-linear scaling with number of processors in a shared memory environment. A typical run of a few tens of nanometers for a few nanoseconds will run on a timescale of days on a multiprocessor desktop.     

Optimal replacement policy for a two-dissimilar-component cold standby system with different repair actions

In this paper, a cold standby repairable system consisting of two dissimilar components and one repairman is studied. When failures occur, the repair of both component 1 and component 2 are not ‘as good as new’. The consecutive operating times of component 1 after repair constitute a decreasing geometric process, while the repair times of component 1 are independent and identically distributed. For component 2, its failure is rectified by minimal repair, and the repair time is negligible. Component 1 has priority in use when both components are good. The replacement policy N is based on the failure number of component 1. Under policy N, we derive the explicit expression of the long-run average cost rate C(N) as well as the average number of repairs of component 2 before the system replaced. The optimal replacement policy N*, which minimises the long-run average cost rate C(N), is obtained theoretically. If the failure rate r(t) of component 2 is increasing, the existence and uniqueness of the optimal policy N* is also proved. Finally, a numerical example is given to validate the developed theoretical model. Some sensitivity analyses are provided to show the influence of some parameters, such as the costs for replacement and repair, and the parameters of the lifetime and repair time distributions of both components, to the optimal replacement policy N* and corresponding average cost rate C(N*).     

On the calculation of unperturbed amplitude scattering of a quantum particle on a complicated object

A model realizing a simple numerical solution algorithm of the direct quantum scattering problem for a neutral nonrelativistic particle, is suggested. The particle interacts with N ~ 10⁵–10⁷ disordered centers. The selected interval of the number N is some neighborhood of the application limit of iteration methods within the bounds of the suggested scheme. The model results in the linear algebraic system with a dimension that is 2–4 orders of magnitude lower than the number N.     

A geometric process model for M/PH(M/PH)/1/K queue with new service machine procurement lead time

In this article, we consider a geometric process model for M/PH(M/PH)/1/K queue with new service machine procurement lead time. A maintenance policy (N???1,?N) based on the number of failures of the service machine is introduced into the system. Assuming that a failed service machine after repair will not be ‘as good as new’, and the spare service machine for replacement is only available by an order. More specifically, we suppose that the procurement lead time for delivering the spare service machine follows a phase-type (PH) distribution. Under such assumptions, we apply the matrix-analytic method to develop the steady state probabilities of the system, and then we obtain some system performance measures. Finally, employing an important Lemma, the explicit expression of the long-run average cost rate for the service machine is derived, and the direct search method is also implemented to determine the optimal value of N for minimising the average cost rate.     

Diagonal stabilization of linear multivariable systems

A new procedure is presented for the synthesis of diagonal compensators for N × N linear multivariable systems that are free of fixed modes with respect to constant diagonal output feedbacks. The synthesis procedure employs simple polynomial algebra and it is in the form of an N-step algorithm. The geometric configurations 2N- and 2^N-cells in N-space are shown to be especially suitable for visualizing diagonal feedback and aiding the application of the synthesis algorithm.     

Generating heavy particles with energy and momentum conservation

We propose a novel algorithm, called REGGAE, for the generation of momenta of a given sample of particle masses, evenly distributed in Lorentz-invariant phase space and obeying energy and momentum conservation. In comparison to other existing algorithms, REGGAE is designed for the use in multiparticle production in hadronic and nuclear collisions where many hadrons are produced and a large part of the available energy is stored in the form of their masses. The algorithm uses a loop simulating multiple collisions which lead to production of configurations with reasonably large weights.

Program summary

Program title: REGGAE (REscattering-after-Genbod GenerAtor of Events)Catalogue identifier: AEJR_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEJR_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.: 1523No. of bytes in distributed program, including test data, etc.: 9608Distribution format: tar.gzProgramming language: C++Computer: PC Pentium 4, though no particular tuning for this machine was performed.Operating system: Originally designed on Linux PC with g++, but it has been compiled and ran successfully on OS X with g++ and MS Windows with Microsoft Visual C++ 2008 Express Edition, as well.RAM: This depends on the number of particles which are generated. For 10 particles like in the attached example it requires about 120 kB.Classification: 11.2Nature of problem: The task is to generate momenta of a sample of particles with given masses which obey energy and momentum conservation. Generated samples should be evenly distributed in the available Lorentz-invariant phase space.Solution method: In general, the algorithm works in two steps. First, all momenta are generated with the GENBOD algorithm. There, particle production is modeled as a sequence of two-body decays of heavy resonances. After all momenta are generated this way, they are reshuffled. Each particle undergoes a collision with some other partner such that in the pair center of mass system the new directions of momenta are distributed isotropically. After each particle collides only a few times, the momenta are distributed evenly across the whole available phase space. Starting with GENBOD is not essential for the procedure but it improves the performance.Running time: This depends on the number of particles and number of events one wants to generate. On a LINUX PC with 2 GHz processor, generation of 1000 events with 10 particles each takes about 3 s.     

Replacement problems for a cold standby repairable system

In this paper, a cold standby repairable system consisting of two identical components and one repairman is studied. Assume that each component after repair is not “as good as new”, by using a geometric process, we consider two kinds of repair replacement policy, one based on the working age T of component 1 under which the system is replaced when the working age of component 1 reaches T, and the other based on the failure number N of component 1 under which the system is replaced when the failure number of component 1 reaches N. Our problem is to choose optimal replacement policies T* and N* respectively such that the long-run average cost per unit time of the system is minimized. And we can prove under some mild conditions that the optimal policy N* is better than the optimal policy T*. Finally, a numerical example for policy N is given.     

(n,N) type maintenance policy for multi-component systems with failure interactions

This paper studies maintenance policies for multi-component systems in which failure interactions and opportunistic maintenance (OM) involve. This maintenance problem can be formulated as a Markov decision process (MDP). However, since an action set and state space in MDP exponentially expand as the number of components increase, traditional approaches are computationally intractable. To deal with curse of dimensionality, we decompose such a multi-component system into mutually influential single-component systems. Each single-component system is formulated as an MDP with the objective of minimising its long-run average maintenance cost. Under some reasonable assumptions, we prove the existence of the optimal (n, N) type policy for a single-component system. An algorithm to obtain the optimal (n, N) type policy is also proposed. Based on the proposed algorithm, we develop an iterative approximation algorithm to obtain an acceptable maintenance policy for a multi-component system. Numerical examples find that failure interactions and OM pose significant effects on a maintenance policy.     

‘Perfectly’ Scalable Data I/O

This paper describes and analyzes a new architecture for file systems in which ‘metadata’, lock control, etc., are distributed among diverse resources. The basic data structure is a segment, viz. a logical group of files, folders, or other objects. The file system requires only one root, and can be non-hierarchical without a complete tree structure within segments. For ‘embarrassingly parallel’ data distributions, scalability is trivially perfect for all N,where N is the number of servers. Even for random file access, a new extreme statistical mechanics is used to show that data I/O is ‘perfectly’ scalable with probability 1, with degradation from perfect scaling that is small and bounded by f ln N/ ln (ln N). Here f is the fraction of data that is metadata. In contrast, earlier solutions degrade much faster, like Nf. No structural changes in classical metadata are required.     

Interaction of agents in financial markets and informational method to quantify it

Abstact In this article, an informational method to quantify behavioral similarities of market participants is proposed regarding a financial market as a many-body system. An agent-based model of a financial market in which N market participants deal with M financial commodities is considered. In order to measure the agents’ interactions, the spectral distance defined by the Kullback-Leibler divergence between two normalized spectra of behavioral frequencies is introduced. The validity of the method is evaluated by using the behavioral frequencies obtained from the agent-based model. It is concluded that the perception and decision parameters of agents who treat two commodities tend to be similar when the behavioral frequencies are similar. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007