A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes

A partially structure-preserving method for sparse symmetric matrices is proposed. Computational results on the permanents of adjacency matrices arising from molecular chemistry are presented. The largest adjacency matrix of fullerenes computed before is that of C₆₀ with a cost of several hours on supercomputers, while only about 6 min on an Intel Pentium PC (1.8 GHz) with our method. Further numerical computations are given for larger fullerenes and other adjacency matrices with n=60,80. This shows that our method is promising for problems from molecular chemistry.     

Application of the majority connectedness carrier for computing the reliability of complex systems

A computational method for probability of majority connectedness of the two-pole network of a random graph is stated when the union of circuits is used as a connectedness carrier of node-poles. Formal rules for calculations of this type illustrated by the corresponding examples are given.     

Enhanced-robustness Dijkstra algorithm for control of routing in the IP-networks

A modified Dijkstra algorithm which is an efficient tool for allocation of the input data flows in the backbone IP-networks using the OSPF protocol was proposed. The purpose of modification was to improve the algorithm robustness to the overloads in the data networks. Numerous experimental comparisons of the performance of the proposed algorithm and the linear programming-based algorithm of robust load correction and allocation in the IP-networks demonstrated that the proposed algorithm is highly efficient.     

An optimal management hierarchy for given groups of executives

An important problem in economics is the construction of an effective minimal-cost management hierarchy for an economic system. A model for optimization of a management hierarchy is designed, a cost function is defined on a set of hierarchies consisting of exogenically given subdivisions (managers for supervising given groups), whereas other parts of a hierarchy may be formed arbitrarily and contain multiple subordination, etc. The optimal hierarchy for certain classes of cost functions is determined.     

JADAMILU: a software code for computing selected eigenvalues of large sparse symmetric matrices

A new software code for computing selected eigenvalues and associated eigenvectors of a real symmetric matrix is described. The eigenvalues are either the smallest or those closest to some specified target, which may be in the interior of the spectrum. The underlying algorithm combines the Jacobi-Davidson method with efficient multilevel incomplete LU (ILU) preconditioning. Key features are modest memory requirements and robust convergence to accurate solutions. Parameters needed for incomplete LU preconditioning are automatically computed and may be updated at run time depending on the convergence pattern. The software is easy to use by non-experts and its top level routines are written in FORTRAN 77. Its potentialities are demonstrated on a few applications taken from computational physics.

Program summary

Program title: JADAMILUCatalogue identifier: ADZT_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADZT_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.: 101 359No. of bytes in distributed program, including test data, etc.: 7 493 144Distribution format: tar.gzProgramming language: Fortran 77Computer: Intel or AMD with g77 and pgf; Intel EM64T or Itanium with ifort; AMD Opteron with g77, pgf and ifort; Power (IBM) with xlf90.Operating system: Linux, AIXRAM: problem dependentWord size: real:8; integer: 4 or 8, according to user's choiceClassification: 4.8Nature of problem: Any physical problem requiring the computation of a few eigenvalues of a symmetric matrix.Solution method: Jacobi-Davidson combined with multilevel ILU preconditioning.Additional comments: We supply binaries rather than source code because JADAMILU uses the following external packages:

•

MC64. This software is copyrighted software and not freely available. COPYRIGHT (c) 1999 Council for the Central Laboratory of the Research Councils.

•

AMD. Copyright (c) 2004-2006 by Timothy A. Davis, Patrick R. Amestoy, and Iain S. Duff. All Rights Reserved. Source code is distributed by the authors under the GNU LGPL licence.

•

BLAS. The reference BLAS is a freely-available software package. It is available from netlib via anonymous ftp and the World Wide Web.

•

LAPACK. The complete LAPACK package or individual routines from LAPACK are freely available on netlib and can be obtained via the World Wide Web or anonymous ftp.

•

For maximal benefit to the community, we added the sources we are proprietary of to the tar.gz file submitted for inclusion in the CPC library. However, as explained in the README file, users willing to compile the code instead of using binaries should first obtain the sources for the external packages mentioned above (email and/or web addresses are provided).

Running time: Problem dependent; the test examples provided with the code only take a few seconds to run; timing results for large scale problems are given in Section 5.     

Clustering in random line graphs

We investigate the degree distribution P(k) and the clustering coefficient C of the line graphs constructed on the Erdös-Rényi networks, the exponential and the scale-free growing networks. We show that the character of the degree distribution in these graphs remains Poissonian, exponential and power law, respectively, i.e. the same as in the original networks. When the mean degree 〈k〉 increases, the obtained clustering coefficient C tends to 0.50 for the transformed Erdös-Rényi networks, to 0.53 for the transformed exponential networks and to 0.61 for the transformed scale-free networks. These results are close to theoretical values, obtained with the model assumption that the degree-degree correlations in the initial networks are negligible.     

An efficient swap algorithm for the lattice Boltzmann method

During the last decade, the lattice-Boltzmann method (LBM) as a valuable tool in computational fluid dynamics has been increasingly acknowledged. The widespread application of LBM is partly due to the simplicity of its coding. The most well-known algorithms for the implementation of the standard lattice-Boltzmann equation (LBE) are the two-lattice and two-step algorithms. However, implementations of the two-lattice or the two-step algorithm suffer from high memory consumption or poor computational performance, respectively. Ultimately, the computing resources available decide which of the two disadvantages is more critical. Here we introduce a new algorithm, called the swap algorithm, for the implementation of LBE. Simulation results demonstrate that implementations based on the swap algorithm can achieve high computational performance and have very low memory consumption. Furthermore, we show how the performance of its implementations can be further improved by code optimization.     

Sewing algorithm

We present a procedure that in many cases enables the Monte Carlo sampling of states of a large system from the sampling of states of a smaller system. We illustrate this procedure, which we call the sewing algorithm, for sampling states from the transfer matrix of the two-dimensional Ising model.     

Parallelization issues of a code for physically-based simulation of fabrics

The simulation of fabrics, clothes, and flexible materials is an essential topic in computer animation of realistic virtual humans and dynamic sceneries. New emerging technologies, as interactive digital TV and multimedia products, make necessary the development of powerful tools to perform real-time simulations. Parallelism is one of such tools. When analyzing computationally fabric simulations we found these codes belonging to the complex class of irregular applications. Frequently this kind of codes includes reduction operations in their core, so that an important fraction of the computational time is spent on such operations. In fabric simulators these operations appear when evaluating forces, giving rise to the equation system to be solved. For this reason, this paper discusses only this phase of the simulation. This paper analyzes and evaluates different irregular reduction parallelization techniques on ccNUMA shared memory machines, applied to a real, physically-based, fabric simulator we have developed. Several issues are taken into account in order to achieve high code performance, as exploitation of data access locality and parallelism, as well as careful use of memory resources (memory overhead). In this paper we use the concept of data affinity to develop various efficient algorithms for reduction parallelization exploiting data locality.     

A new algorithm for fast simulation of optical spectra generated in a nonlinear media

A new and highly efficient algorithm developed under MATLAB for calculating the optical spectra generated by non-resonant optical parametric fluorescence is presented. This algorithm, which allows quick simulation of the spectra, is shown to be much more rapid than standard ones. The ways to modify the algorithm for other environments are discussed.

Program summary

Title of the program:OPFSpectraFinderCatalogue number: ADTKProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADTKProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions: Persons requesting the program must sign the standard CPC non-profit use licenseComputers on which the program has been tested: Intel Pentium, SUN HPC3500Operating system under which the program, has been tested: Microsoft Windows 2000, Unix Solaris 7.0Programming language used: MATLAB 6.0Memory required to execute with typical data: 256 M (the total computer memory)No. of processors used: 1No. of bytes in distributed program, including test data, etc.: 935 376No. of lines in distributed program, including test data, etc.: 6667Distribution format: tar gzip fileNature of physical problem: Obtaining the form of optical spectra of light generated in the process of optical parametric fluorescence in a periodically poled quadratically nonlinear mediumMethod of solution: Linearization of the set of nonlinear equations, obtaining the set of equations with constant coefficients, finding the solution as the matrix exponentialRestrictions on the complexity of the problem: not knownTypical running time: 80 seconds for obtaining the data for data set by default in the files submitted on a PC mentioned aboveReferences: The physical discussion is given in V. Beskrovnyy, P. Baldi, Optical parametric fluorescence spectra in periodically poled media, Optics Express 10 (2002) 990     

xPerm: fast index canonicalization for tensor computer algebra

We present a very fast implementation of the Butler-Portugal algorithm for index canonicalization with respect to permutation symmetries. It is called xPerm, and has been written as a combination of a Mathematica package and a C subroutine. The latter performs the most demanding parts of the computations and can be linked from any other program or computer algebra system. We demonstrate with tests and timings the effectively polynomial performance of the Butler-Portugal algorithm with respect to the number of indices, though we also show a case in which it is exponential. Our implementation handles generic tensorial expressions with several dozen indices in hundredths of a second, or one hundred indices in a few seconds, clearly outperforming all other current canonicalizers. The code has been already under intensive testing for several years and has been essential in recent investigations in large-scale tensor computer algebra.

Program summary

Program title: xPermCatalogue identifier: AEBH_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBH_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.: 93 582No. of bytes in distributed program, including test data, etc.: 1 537 832Distribution format: tar.gzProgramming language: C and Mathematica (version 5.0 or higher)Computer: Any computer running C and Mathematica (version 5.0 or higher)Operating system: Linux, Unix, Windows XP, MacOSRAM:: 20 MbyteWord size: 64 or 32 bitsClassification: 1.5, 5Nature of problem: Canonicalization of indexed expressions with respect to permutation symmetries.Solution method: The Butler-Portugal algorithm.Restrictions: Multiterm symmetries are not considered.Running time: A few seconds with generic expressions of up to 100 indices. The xPermDoc.nb notebook supplied with the distribution takes approximately one and a half hours to execute in full.     

An efficient analytical approach for solving fourth order boundary value problems

Based on the homotopy analysis method (HAM), an efficient approach is proposed for obtaining approximate series solutions to fourth order two-point boundary value problems. We apply the approach to a linear problem which involves a parameter c and cannot be solved by other analytical methods for large values of c, and obtain convergent series solutions which agree very well with the exact solution, no matter how large the value of c is. Consequently, we give an affirmative answer to the open problem proposed by Momani and Noor in 2007 [S. Momani, M.A. Noor, Numerical comparison of methods for solving a special fourth-order boundary value problem, Appl. Math. Comput. 191 (2007) 218-224]. We also apply the approach to a nonlinear problem, and obtain convergent series solutions which agree very well with the numerical solution given by the Runge-Kutta-Fehlberg 4-5 technique.     

Model-Driven Development for scientific computing. An upgrade of the RHEEDGr program

Model-Driven Engineering (MDE) is the software engineering discipline, which considers models as the most important element for software development, and for the maintenance and evolution of software, through model transformation. Model-Driven Architecture (MDA) is the approach for software development under the Model-Driven Engineering framework. This paper surveys the core MDA technology that was used to upgrade of the RHEEDGR program to C++0x language standards.

New version program summary

Program title: RHEEDGR-09Catalogue identifier: ADUY_v3_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADUY_v3_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.: 21 263No. of bytes in distributed program, including test data, etc.: 1 266 982Distribution format: tar.gzProgramming language: Code Gear C++ BuilderComputer: Intel Core Duo-based PCOperating system: Windows XP, Vista, 7RAM: more than 1 MBClassification: 4.3, 7.2, 6.2, 8, 14Does the new version supersede the previous version?: YesNature of problem: Reflection High-Energy Electron Diffraction (RHEED) is a very useful technique for studying growth and surface analysis of thin epitaxial structures prepared by the Molecular Beam Epitaxy (MBE). The RHEED technique can reveal, almost instantaneously, changes either in the coverage of the sample surface by adsorbates or in the surface structure of a thin film.Solution method: The calculations are based on the use of a dynamical diffraction theory in which the electrons are taken to be diffracted by a potential, which is periodic in the dimension perpendicular to the surface.Reasons for new version: Responding to the user feedback the graphical version of the RHEED program has been upgraded to C++0x language standards. Also, functionality and documentation of the program have been improved.Summary of revisions:

1.

Model-Driven Architecture (MDA) is the approach defined by the Object Management Group (OMG) for software development under the Model-Driven Engineering framework [1]. The MDA approach shifts the focus of software development from writing code to building models. By adapting a model-centric approach, the MDA approach hopes to automate the generation of system implementation artifacts directly from the model. The following three models are the core of the MDA: (i) the Computation Independent Model (CIM), which is focused on basic requirements of the system, (ii) the Platform Independent Model (PIM), which is used by software architects and designers, and is focused on the operational capabilities of a system outside the context of a specific platform, and (iii) the Platform Specific Model (PSM), which is used by software developers and programmers, and includes details relating to the system for a specific platform. Basic requirements for the calculation of the RHEED intensity rocking curves in the one-beam condition have been described in Ref. [2]. Fig. 1 shows the PIM for the present version of the program. Fig. 2 presents the PSM for the program.

2.

The TGraph2D.bpk package has been recompiled to Graph2D0x.bpl and upgraded according to C++0x language standards. Fig. 3 shows the PSM of the Graph2D component, which is manifested by the Graph2D0x.bpl package presently. This diagram is a graphic presentation of the static view, which shows a collection of declarative model elements and their relationships. Installation instructions of the Graph2D0x package can be found in the new distribution.

3.

The program requires the user to provide the appropriate parameters for the crystal structure under investigation. These parameters are loaded from the parameters.ini file at run-time. Instructions for the preparation of the .ini files can be found in the new distribution.

4.

The program enables carrying out one-dimensional dynamical calculations for the fcc lattice, with a two-atoms basis and fcc lattice, with one atom basis but yet the zeroth Fourier component of the scattering potential in the TRHEED1D::crystPotUg() function can be modified according to users' specific application requirements.

5.

A graphical user interface (GUI) for the program has been reconstructed.

6.

The program has been compiled with English/USA regional and language options.

Unusual features: The program is distributed in the form of main projects RHEEDGr_09.cbproj and Graph2D0x.cbproj with associated files, and should be compiled using Code Gear C++ Builder 2009 compilers.Running time: The typical running time is machine and user-parameters dependent.References:

[1]

OMG, Model Driven Architecture Guide Version 1.0.1, 2003, http://www.omg.org/cgi-bin/doc?omg/03-06-01.

[2]

A. Daniluk, Comput. Phys. Comm. 166 (2005) 123.

     

Existence of states on quantum structures

Orthomodular lattices occurred as generalized event structures in the models of probability for quantum mechanics. Here we contribute to the question of existence of states (=probability measures) on orthomodular lattices. We prove that known techniques do not allow to find examples with less than 19 blocks (=maximal Boolean subalgebras). This bound is achieved by the example by Mayet [R. Mayet, Personal communication, 1993]. Although we do not finally exclude the existence of other techniques breaking this bound, existence of smaller examples is highly unexpected.     

Combinatorial methods for constructing bipartite uniform minimal quasicomplete graphs (symmetrical block designs)

Consideration was given to a specific family of bipartite graphs consisting of two disjoint subsets X and Y of vertices and characterized by that each vertex in X (Y) is connected to each of the remaining vertices in X (Y) by a unique path of length two passing through some vertex in Y (X). The prefix “quasi” reflects the fact that complete connection of the vertices is realized by paths of length two rather than by edges. The problem of constructing uniform minimal graphs with identical cardinalities of the subsets X and Y which is of practical interest for complex communication networks was discussed. It belongs to the class of combinatorial problems of construction of the so-called symmetrical block designs.     

GenMin: An enhanced genetic algorithm for global optimization

A new method that employs grammatical evolution and a stopping rule for finding the global minimum of a continuous multidimensional, multimodal function is considered. The genetic algorithm used is a hybrid genetic algorithm in conjunction with a local search procedure. We list results from numerical experiments with a series of test functions and we compare with other established global optimization methods. The accompanying software accepts objective functions coded either in Fortran 77 or in C++.

Program summary

Program title: GenMinCatalogue identifier: AEAR_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAR_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.: 35 810No. of bytes in distributed program, including test data, etc.: 436 613Distribution format: tar.gzProgramming language: GNU-C++, GNU-C, GNU Fortran 77Computer: The tool is designed to be portable in all systems running the GNU C++ compilerOperating system: The tool is designed to be portable in all systems running the GNU C++ compilerRAM: 200 KBWord size: 32 bitsClassification: 4.9Nature of problem: A multitude of problems in science and engineering are often reduced to minimizing a function of many variables. There are instances that a local optimum does not correspond to the desired physical solution and hence the search for a better solution is required. Local optimization techniques are frequently trapped in local minima. Global optimization is hence the appropriate tool. For example, solving a nonlinear system of equations via optimization, employing a least squares type of objective, one may encounter many local minima that do not correspond to solutions (i.e. they are far from zero).Solution method: Grammatical evolution and a stopping rule.Running time: Depending on the objective function. The test example given takes only a few seconds to run.     

PANMIN: sequential and parallel global optimization procedures with a variety of options for the local search strategy

We present two sequential and one parallel global optimization codes, that belong to the stochastic class, and an interface routine that enables the use of the Merlin/MCL environment as a non-interactive local optimizer. This interface proved extremely important, since it provides flexibility, effectiveness and robustness to the local search task that is in turn employed by the global procedures. We demonstrate the use of the parallel code to a molecular conformation problem.

Program summary

Title of program: PANMINCatalogue identifier: ADSUProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSUProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which it has been tested: PANMIN is designed for UNIX machines. The parallel code runs on either shared memory architectures or on a distributed system. The code has been tested on a SUN Microsystems ENTERPRISE 450 with four CPUs, and on a 48-node cluster under Linux, with both the GNU g77 and the Portland group compilers. The parallel implementation is based on MPI and has been tested with LAM MPI and MPICHInstallation: University of Ioannina, GreeceProgramming language used: Fortran-77Memory required to execute with typical data: Approximately O(n²) words, where n is the number of variablesNo. of bits in a word: 64No. of processors used: 1 or manyHas the code been vectorised or parallelized?: Parallelized using MPINo. of bytes in distributed program, including test data, etc.: 147163No. of lines in distributed program, including the test data, etc.: 14366Distribution format: gzipped tar fileNature of physical problem: A multitude of problems in science and engineering are often reduced to minimizing a function of many variables. There are instances that a local optimum does not correspond to the desired physical solution and hence the search for a better solution is required. Local optimization techniques can be trapped in any local minimum. Global Optimization is then the appropriate tool. For example, solving a non-linear system of equations via optimization, one may encounter many local minima that do not correspond to solutions, i.e. they are far from zeroMethod of solution: PANMIN is a suite of programs for Global Optimization that take advantage of the Merlin/MCL optimization environment [1,2]. We offer implementations of two algorithms that belong to the stochastic class and use local searches either as intermediate steps or as solution refinementRestrictions on the complexity of the problem: The only restriction is set by the available memory of the hardware configuration. The software can handle bound constrained problems. The Merlin Optimization environment must be installed. Availability of an MPI installation is necessary for executing the parallel codeTypical running time: Depending on the objective functionReferences: [1] D.G. Papageorgiou, I.N. Demetropoulos, I.E. Lagaris, Merlin-3.0. A multidimensional optimization environment, Comput. Phys. Commun. 109 (1998) 227-249. [2] D.G. Papageorgiou, I.N. Demetropoulos, I.E. Lagaris, The Merlin Control Language for strategic optimization, Comput. Phys. Commun. 109 (1998) 250-275.     

An iterative method to compute the sign function of a non-Hermitian matrix and its application to the overlap Dirac operator at nonzero chemical potential

The overlap Dirac operator in lattice QCD requires the computation of the sign function of a matrix. While this matrix is usually Hermitian, it becomes non-Hermitian in the presence of a quark chemical potential. We show how the action of the sign function of a non-Hermitian matrix on an arbitrary vector can be computed efficiently on large lattices by an iterative method. A Krylov subspace approximation based on the Arnoldi algorithm is described for the evaluation of a generic matrix function. The efficiency of the method is spoiled when the matrix has eigenvalues close to a function discontinuity. This is cured by adding a small number of critical eigenvectors to the Krylov subspace, for which we propose two different deflation schemes. The ensuing modified Arnoldi method is then applied to the sign function, which has a discontinuity along the imaginary axis. The numerical results clearly show the improved efficiency of the method. Our modification is particularly effective when the action of the sign function of the same matrix has to be computed many times on different vectors, e.g., if the overlap Dirac operator is inverted using an iterative method.