Some Method for Constructing Cycles in a Graph

Abstract

Multidimensional matrices are a powerful tool for solving various fundamental scientific problems and applied scientific and technical problems. As examples of the use of multidimensional matrices in various fields, one can cite the work of the creator of the theory of multidimensional matrices N.P. Sokolov and other works, including those performed by the authors. The problem of parallel implementation of the most complex operation of the algebra of multidimensional matrices, the (, )-convolution product, is one of the most important. It is no coincidence that many publications are devoted to the problem of parallel multiplication of ordinary two-dimensional matrices. In these works, the problems of choosing a method for distributing matrix elements between processors and developing architectures of software and hardware systems for the effective implementation of this operation are considered. For parallel multiplication of ordinary matrices, as a rule, two types of algorithms are used: band algorithms that implement element-wise matrix multiplication and block algorithms based on the Frobenius method. Many authors who have analyzed the efficiency of parallel matrix multiplication prefer block algorithms, arguing that the latter have a high degree of scalability. Taking into account the fact that scalability is the most important property of parallel algorithms and computing systems that implement them, in the future we will consider a parallel algorithm for block multiplication of multidimensional matrices. The paper considers a generalization of the Cannon algorithm to the (, )-convolution product of multidimensional matrices. It is proved that multidimensional matrices-operands can be represented as a set of sections by Scottish indices, the products of which allow one to obtain the required matrix-result. To split these sections into blocks and recalculate block indices during the execution of the algorithm, a method based on the use of specific number systems is proposed, and a method for calculating the bases of these number systems is determined. The process of executing the generalized Cannon algorithm is illustrated by block distribution tables at all stages of the algorithm execution. The proposed generalization method can be extended to other block matrix multiplication algorithms.

Keywords

• directed graphs
• cycles in a graph
• multidimensional matrices
• databases
• parallel programming