Matrix decomposition into clans

Motivation

The task of linear system solution is a classical task of linear algebra. There are a variety of known methods for linear system solution. The choice of the method depends essentially on the set of numbers used. More precise it depends on the algebraic structure of the variables and coefficients. The solution of system in fields and bodies, for example, in rational or real numbers is the most studied. These algebraic structures allow the everywhere defined operation of division. It is convenient to develop the simple and powerful methods. Precise and approximate methods are distinguished. The most popular is Gauss method consisting in consequent elimination of variables and obtaining the triangular form of the matrix.

Ring algebraic structures such as integer numbers require special methods, as the division is not the everywhere-defined operation in a ring. There is known the universal method using unimodular transformations of matrix to obtain Smith normal form. Result matrix has diagonal form and allow the simple representation of solutions. Unfortunately this method is exponential. Up to present time were suggested a few more complex but polynomial methods.

The development of such areas of computer science as Petri net theory, logic programming, artificial intellect require to solve integer systems over the set of nonnegative integer numbers. Nonnegative integer numbers form algebraic structure of monoid. In monoid even the operation of subtraction is not everywhere defined. All the known methods of integer system solution in nonnegative integer numbers are exponential.

Therefore, the task of the effective methods development for linear system solution, especially in nonnegative numbers, is enough significant. Decomposition into clans^[1] allows an essential acceleration of computations. In the case the exponential complexity of the source method of system solution the acceleration is exponential too.

Near relation

Two rows of a matrix are near if they contain a column with nonzero values of the same sign. Near relation is reflexive and symmetric.

Clan relation

Clan relation is a transitive closure of the near relation. Clan relation is reflexive, symmetric and transitive. Thus it is an equivalence relation and defines a partition of the set of matrix rows.

Decomposed matrix structure

The first block column is a matrix of clans' interconnections. The rest is a block diagonal matrix. Each contact column connects two clans and enter these clans with opposite signs.

Employing decomposition into clans

Linear system solution with decomposition into clans is efficient in the combination with methods of system solution more hard than a polynomial of third degree and in the case the system may be decomposed in more than one clan.

As a result of this technique application to various matrixes it may be concluded that a good opportunity to decomposition have sparse matrixes. This is realistic enough situation as large-scale real-life models contain well-localized interconnections of elements.

It should be noted also the relationship of technique proposed with the decomposition of Petri nets.^[2] We may construct the matrix of directions D for an arbitrary matrix A of linear system as D=sign(A). Matrix D may be considered further as incidence matrix of Petri net.

The most significant acceleration of computations was obtained for Diophantine (integer) systems especially solving over the set of nonnegative numbers. There are only exponential methods for solution of such systems. In this case the acceleration of computation obtained is exponential.

References

1. Zaitsev D.A. Solving Linear Systems via Composition of their Clans, Intelligent Information Management, 2009, 1, 73-80.
2. Zaitsev D.A. Clans of Petri Nets: Verification of protocols and performance evaluation of networks, LAP LAMBERT Academic Publishing, 2013, 292 p.