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.     

Calculation of the permanent of a sparse positive matrix

The exact calculation of permanents of n×n matrices is a non-polynomial computational problem as a function of n. An efficient deterministic algorithm is presented that allows for the approximate calculation of permanents obtained from sparse positive matrices within controllable precision bounds. The upper and lower bounds can be made arbitrarily close to each other and the algorithm outperforms existing ones for sufficiently large matrices.     

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.     

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.     

An efficient algorithm for computing permanental polynomials of graphs

An efficient numerical method for computing permanental polynomials of graphs is proposed. It adapts multi-entry expansion of FFT, and is parallel in nature. It is applied to fullerene-type graphs, and works for C₅₆, while the largest fullerene computed before is C₄₀. Extensive numerical computations show that the algorithm is fast and stable.     

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.     

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.     

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.     

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.     

On novel magnetic probe for fullerene characterization: Theoretical studies on NMR parameters of free and confined in fullerenes HD and H2 molecules

Chemical characterization and separation of individual fullerenes from a raw reaction mixture need new and efficient tools, including rapid spectroscopic techniques. Recent “molecular surgery” synthesis of endohedral complexes of fullerenes with selected atoms and small molecules has opened a new path for experimental and theoretical studies on structural and spectroscopic properties of these molecular systems. Among them are fullerenes with molecular hydrogen confined within a nanoscale cavity.In this work we report on quantum-chemical prediction of nuclear magnetic shielding (and chemical shift) and indirect spin–spin coupling constant in free HD and H₂ molecules, as well as models of confined dihydrogen using the coupled cluster with single and double excitations (CCSD) and density functional theory (DFT) levels of theory. Inspired with the recent experimental NMR studies on HD and H₂ molecules confined inside C₆₀ fullerene we systematically investigated the sensitivity of ¹H nuclear magnetic shielding of H₂ and indirect spin–spin coupling constant ¹J_HD in HD molecules to the interatomic separation in the gas phase, in the presence of benzene and inside fullerene cages of different size. The sensitivity of both NMR parameters to confinement is discussed in terms of very weak non-covalent interactions of HD and H₂ with fullerene cage.     

HypExp, a Mathematica package for expanding hypergeometric functions around integer-valued parameters

We present the Mathematica package HypExp which allows to expand hypergeometric functions around integer parameters to arbitrary order. At this, we apply two methods, the first one being based on an integral representation, the second one on the nested sums approach. The expansion works for both symbolic argument z and unit argument. We also implemented new classes of integrals that appear in the first method and that are, in part, yet unknown to Mathematica.

Program summary

Title of program:HypExpCatalogue identifier:ADXF_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXF_v1_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicence:noneComputers:Computers running Mathematica under Linux or WindowsOperating system:Linux, WindowsProgram language:MathematicaNo. of bytes in distributed program, including test data, etc.:739 410No. of lines in distributed program, including test data, etc.:89 747Distribution format:tar.gzOther package needed:the package HPL, included in the distributionExternal file required:noneNature of the physical problem:Expansion of hypergeometric functions around integer-valued parameters. These are needed in the context of dimensional regularization for loop and phase space integrals.Method of solution:Algebraic manipulation of nested sums and integral representation.Restrictions on complexity of the problem:Limited by the memory availableTypical running time:Strongly depending on the problem and the availability of libraries.     

Hypergraph products for structural mechanics

In this paper Cartesian, direct and strong Cartesian product of hypergraphs are investigated. A new concept named the adjacency function is defined on hypergraphs. This definition leads to distinct adjacency and Laplacian matrices for a hypergraph and makes it possible to express it in an algebraic form. Variable adjacency functions on hypergraphs result in generation of dynamic graph products which are applied to dynamic systems. For further clarity, some examples from structural mechanics are provided. The generality of the approach is shown through some examples, indicating this fact that the hypergraph products can encompass most of the available developments on the graph products in the literature.     

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     

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.     

基于自适应层级图卷积的多站点空气质量预测模型

时空预测任务在污染治理、交通、能源、气象等领域应用广泛. PM_2.5浓度预测作为典型的时空预测任务, 需要对空气质量数据中的时空依赖关系进行分析和利用. 现有时空图神经网络(ST-GNNs)研究所使用的邻接矩阵使用启发式规则预定义, 无法准确表示站点之间的真实关系. 本文提出了一种自适应分层图卷积神经网络(AHGCNN)用于PM_2.5预测. 首先, 引入了一种分层映射图卷积架构, 在不同层级上使用不同的自学习邻接矩阵, 以有效挖掘不同站点之间独特的时空依赖. 其次, 以基于注意力的聚合机制连接上下层邻接矩阵, 加速收敛过程. 最后, 将隐藏的空间状态与门控循环单元相结合, 形成一个统一的预测架构, 同时捕捉多层次的空间依赖关系和时间依赖关系, 提供最终的预测结果. 实验中, 我们与7种主流预测模型进行对比, 结果表明该模型可以有效获取空气监测站点之间的时空依赖, 提高预测精确度.     

A selected tour of the theory of identification matrices

A selected tour of the theory of identification matrices is offered here. We show that, among other things, shortest-path adjacency matrices are identification matrices for all simple graphs and adjacency matrices are identification matrices for all bipartite graphs. Additionally, we provide an improved proof that augmented adjacency matrices satisfying the circular 1's property are identification matrices. We also present a characterization of doubly convex bipartite graphs by identification matrices. Based on the theory of identification matrices, we describe an improved method for testing isomorphism between Γ circular arc graphs. The sequential algorithm can be implemented to run in O(n²) time and is optimal if the graphs are given as (augmented) adjacency matrices, so to speak.     

3D CAD model retrieval based on the softassign quadratic assignment algorithm

A retrieval method for 3D CAD models based on the softassign quadratic assignment algorithm is presented in this paper. Firstly, retrieval models and target models are expressed as face adjacency graphs (FAGs) and thus 3D CAD model retrieval is turned to a graph matching problem. Secondly, vertex and edge compatibility matrices between the FAGs of a retrieval model and a target model are calculated. Then, an optimization objective function is created from compatibility matrices of a retrieval model and a target model, which serves as the similar metric for choosing vertex mapping matrix M of two models. Finally, the softassign quadratic assignment algorithm is introduced to find the optimal vertex mapping matrix M. Experimental results have shown that the proposed method supports 3D CAD model retrieval, and it is promising to meet the requirement of engineering applications.     

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.     

Impact of sea ice on the retrieval of water-leaving reflectance, chlorophyll a concentration and inherent optical properties from satellite ocean color data

Two physical phenomena by which satellite remotely sensed ocean color data are contaminated by sea ice at high latitudes are described through simulations and observations: (1) the adjacency effect that occurs along sea ice margins and (2) the sub-pixel contamination by a small amount of sea ice within an ocean pixel. The signal at the top of the atmosphere (TOA) was simulated using the 6S radiative transfer code that allows modeling of the adjacency effect for various types of sea ice surrounding an open water area. In situ sea ice reflectance spectra used in the simulations were measured prior to and during the melt period as part of the 2004 Canadian Arctic Shelf Exchange Study (CASES). For sub-pixel contamination, the TOA signal was simulated for various surface reflectances obtained by linear mixture of both sea ice and water-leaving reflectances (ρ_w). The standard atmospheric correction algorithm was then applied to the simulated TOA spectra to retrieve ρ_w spectra from which chlorophyll a concentrations (CHL) and inherent optical properties (IOPs) were derived. The adjacency effect was associated with large errors (> 0.002) in the retrieval of ρ_w as far as 24 km from an ice edge in the blue part of the spectrum (443 nm). Therefore, for moderate to high CHL (> 0.5 mg m^− 3), any pixel located within a distance of ∼ 10-20 km from the ice edge were unreliable. It was also found necessary to consider the adjacency effect when the total absorption coefficient (a_t) was to be retrieved using a semi-analytical algorithm. a_t(443) was underestimated by more than 35% at a distance of 20 km from an ice edge for CHL > 0.5 mg m^− 3. The effect on the retrieval of the particle backscattering coefficient (b_bp) was important only for clear waters (CHL ∼ 0.05 mg m^− 3). In contrast, sub-pixel contamination by a small amount of sea ice produced systematic underestimation of ρ_w in the blue because of incorrect interpretation of enhanced reflectance in the near infrared that is attributed to higher concentrations of atmospheric aerosols. In general, sub-pixel contamination was found to result in overestimations of CHL and a_t, and underestimations of b_bp. A simple method was proposed to flag pixels contaminated by adjacency effect.