Sequential composition of linear systems’ clans

When using Petri nets to investigate deadlock control, structural analysis techniques are applied, which are based on solving systems of linear algebraic equations. To gain an extra computational speed-up when solving sparse linear systems, we examine a sequential clan-composition process, represented by a weighted graph. The system decomposition into clans is represented by a weighted graph. The comparative analysis of sequential composition for subgraphs and edges (pairwise) is presented. The task of constructing a sequence of systems of lower dimension is called an optimal collapse of a weighted graph; the question whether it is NP-complete remains open. Upper and lower bounds for the collapse width, corresponding to the maximal dimension of systems, are derived. A heuristic greedy algorithm of (quasi) optimal collapse is presented and validated statistically. The technique is applicable for solving sparse systems over arbitrary rings (fields) with sign.