Delaunay triangulation in three dimensions

Triangulation in two and higher dimensions began with Dirichlet, Voronoi, Thiessen, and Delaunay. A number of textbooks and papers have extensively covered the properties of triangulations and algorithms for their construction. Most dealt with theoretical aspects of the algorithms and gave upper bounds on their complexity. Here we present a new algorithm and its implementation. Instead of providing a theoretical analysis, we present implementation details, and tests and examples. The algorithm is a generalization of our previous method     

Parallel dynamic and kinetic regular triangulation in three dimensions

A parallel algorithm for regular triangulations is presented. For the purpose of fully dynamic and kinetic particle simulations it allows vertex insertion, deletion, movement, and weight changes. We describe new algorithms for incremental construction of regular triangulations, parallel vertex deletion and insertion. Finally, a parallel Lawson flip algorithm for vertex displacements is presented. The performance analysis demonstrates a significant parallel efficiency for various system sizes and performed changes.     

Break of information-investment flows in the process of switching over intermittency in the change of the trend of development of the dynamic system

Studies are made of basic regularities of the process of switching over intermittency in the change of the trend of development of the cascade-hierarchical system. It is shown that the transition from the section of growth to the section of fall can be explained as a result of the change of the sign of the feedback (from the positive to the negative one) between the increment of the intermittency exponent Δμ and the increment of the fractal dimension Δd _f (the expansion of the “channel” of attraction) for the most rapidly orienting (short-term) dynamic substructures. The subsequent break of the information-investment flow (the flow of commands) from the long-term to short-term substructures makes it impossible to support the dynamic equilibrium in the cascade-hierarchical system, which leads to the bifurcation transition to a new section of the channel of attraction. Original Russian Text ? V.G. Kleparskii, 2007, published in Avtomatika i Telemekhanika, 2007, No. 4, pp. 92–100.     

Routing control in IP-networks with the variable performance criterion

For routing control in backbone IP-networks, we propose to part the control time interval into two segments and to use different performance criteria on them. It is assumed that distribution of flows is realized at the first step by the Dijkstra algorithm which is included in OSPF and is used in Sisco routers. The minimax criterion is proposed at the second step; it is realized in the robust algorithm of data incoming flows distribution adjustment. The object of the adjustment algorithm is to prevent or lower the probability of networks congestion. Characteristics of the proposed algorithm are studied. Efficiency of the adjustment algorithm application for network controlling is demonstrated by the Monte Carlo method. Speed characteristics of the proposed algorithm are compared with some optimal algorithms.     

Investigation and application of Laplace spectra of orgraphs with the ring structure

The Laplace matrix is a square matrix L = (? _ij ) ∈ ? ^n×n in which all nondiagonal elements are nonpositive and all row sums are equal to zero. Each Laplace matrix corresponds to a weighted orgraph with positive arc weights. The problem of reality of Laplace matrix spectrum for orgraphs of a special type consisting of two “counter” Hamiltonian cycles in one of which one or two arcs are removed is studied. Characteristic polynomials of Laplace matrices of these orgraphs are expressed through polynomials Z _n (x) that can be obtained from Chebyshev second-kind polynomials P _2n (y) by the substitution of y ² = x. The obtained results relate to properties of the product of Chebyshev second-kind polynomials. A direct method for computing the spectrum of Laplace circuit matrix is given. The obtained results can be used for computing the number of spanning trees in orgraphs of the studied type. One of the possible practical applications of these results is the investigation of topology and development of new Internet protocols.     

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.     

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.     

Computing the Baker-Campbell-Hausdorff series and the Zassenhaus product

The Baker-Campbell-Hausdorff (BCH) series and the Zassenhaus product are of fundamental importance for the theory of Lie groups and their applications in physics and physical chemistry. Standard methods for the explicit construction of the BCH and Zassenhaus terms yield polynomial representations, which must be translated into the usually required commutator representation. We prove that a new translation proposed recently yields a correct representation of the BCH and Zassenhaus terms. This representation entails fewer terms than the well-known Dynkin-Specht-Wever representation, which is of relevance for practical applications. Furthermore, various methods for the computation of the BCH and Zassenhaus terms are compared, and a new efficient approach for the calculation of the Zassenhaus terms is proposed. Mathematica implementations for the most efficient algorithms are provided together with comparisons of efficiency.     

Markov property in quantum logic: A reflection

A possible way of the Markov property introduction within the framework of the orthomodular quantum logic, which is commonly used as the calculus model for quantum mechanics is presented in this paper. The presented work follows the logical line rather than any physical interpretation in the framework of quantum mechanics. The basic algebraic structure, which is used as a model for noncompatible random events is an orthomodular lattice. On the orthomodular lattice, a dynamical structure is introduced coupled with mappings which have similar properties as s_n-maps on the orthomodular lattice. This construction leads to the definition of an L-process with the Markov property on the orthomodular lattice.     

Decay chain differential equations: Solution through matrix algebra

A matricial method to solve the decay chain differential equations system is presented. The quantity of each nuclide in the chain at a time t may be evaluated by analytical expressions obtained in a simple way using recurrence relations. This method may be applied to problems of radioactive buildup and decay and can be easily implemented computationally.     

Algebraic decomposition of discrete functions

Consideration was given to the functional decomposition of the discrete systems which is reducible to the functional decomposition of the discrete functions, where by the decomposition is meant the representation of a function by a formula in the basis of unary and binary operations. The algebraic decomposition in an algebra consisting of two binary operations and functions of two variables was studied. A procedure of formula design on the basis of composition of repetition-free subformulas was substantiated. Both exact and asymptotic complexity estimates of the designed formulas were given.     

HPL, a Mathematica implementation of the harmonic polylogarithms

In this paper, we present an implementation of the harmonic polylogarithm of Remiddi and Vermaseren [E. Remiddi, J.A.M. Vermaseren, Int. J. Modern Phys. A 15 (2000) 725, hep-ph/9905237] for Mathematica. It contains an implementation of the product algebra, the derivative properties, series expansion and numerical evaluation. The analytic continuation has been treated carefully, allowing the user to keep the control over the definition of the sign of the imaginary parts. Many options enables the user to adapt the behavior of the package to his specific problem.

Program summary

Program title: HPLCatalogue identifier:ADWXProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWXProgram obtained from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:noneProgramming language: MathematicaNo. of lines in distributed program, including test data, etc.:13 310No. of bytes in distributed program, including test data, etc.: 1 990 584Distribution format: tar.gzComputer:all computers running MathematicaOperating systems:operating systems running MathematicaNature of problem: Computer algebraic treatment of the harmonic polylogarithms which appear in the evaluation of Feynman diagramsSolution method: Mathematica implementation     

HypExp 2, Expanding hypergeometric functions about half-integer parameters

In this article, we describe a new algorithm for the expansion of hypergeometric functions about half-integer parameters. The implementation of this algorithm for certain classes of hypergeometric functions in the already existing Mathematica package HypExp is described. Examples of applications in Feynman diagrams with up to four loops are given.

New version program summary

Program title:HypExp 2Catalogue identifier:ADXF_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXF_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.:106 401No. of bytes in distributed program, including test data, etc.:2 668 729Distribution format:tar.gzProgramming language:MathematicaComputer:Computers running MathematicaOperating system:Linux, Windows, MacRAM:Depending on the complexity of the problemSupplementary material:Library files which contain the expansion of certain hypergeometric functions around their parameters are availableClassification:4.7, 5Does the new version supersede the previous version?:YesNature of problem:Expansion of hypergeometric functions about parameters that are integer and/or half-integer valued.Solution method:New algorithm implemented in Mathematica.Reasons for new version:Expansion about half-integer parameters.Summary of revisions:Ability to expand about half-integer valued parameters added.Restrictions:The classes of hypergeometric functions with half-integer parameters that can be expanded are listed below.Additional comments:The package uses the package HPL included in the distribution.Running time:Depending on the expansion.     

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 iterative algorithm for least squares problem in quaternionic quantum theory

Quaternionic least squares (QLS) problem is one method of solving overdetermined sets of quaternion linear equations AXB=E that is appropriate when there is error in the matrix E. In this paper, by means of real representation of a quaternion matrix, we introduce a concept of norm of quaternion matrices, which is different from that in [T. Jiang, L. Chen, Algebraic algorithms for least squares problem in quaternionic quantum theory, Comput. Phys. Comm. 176 (2007) 481-485; T. Jiang, M. Wei, Equality constrained least squares problem over quaternion field, Appl. Math. Lett. 16 (2003) 883-888], and derive an iterative method for finding the minimum-norm solution of the QLS problem in quaternionic quantum theory.     

Insert and delete algorithms for maintaining dynamic Delaunay triangulations

We recall that optimal condensing of nearest neighbor data requires the construction of the Delaunay triangulation of the training set. We argue that, from the viewpoint of computational complexity, an iterative approach using a dynamic triangulation is most desirable. We describe two algorithms, Insert and Delete, which permit to maintain a dynamic Delaunay triangulation.     

Algebraic algorithms for least squares problem in quaternionic quantum theory

Quaternionic least squares (QLS) problem is one method of solving overdetermined sets of quaternion linear equations AX≈B that is appropriate when there is error in the matrix B. In this paper, by means of complex representation of a quaternion matrix, we introduce a concept of norm of quaternion matrices, discuss singular values and generalized inverses of a quaternion matrix, study the QLS problem and derive two algebraic methods for finding solutions of the QLS problem in quaternionic quantum theory.     

Practical kriging in three dimensions

Little has been published to date on the practical difficulties of ore reserve estimation in three-dimensional deposits. Some authors have suggested condensing the problem into two dimensions, but this is not always practicable or desirable. A suggestion and a FORTRAN IV Function Segment are provided which may alleviate some of these difficulties.