Computational techniques and data structures of the sparse underdetermined systems with using graph theory

Abstract

For constructing of the solutions of the sparse linear systems we propose effective methods, technologies and their implementation in Wolfram Mathematica. Sparse systems of these types appear in generalized network flow programming problems in the form of restrictions and can be characterized as systems with a large sparse sub-matrix representing the embedded network structure. In addition, such systems arise in estimating traffic in the generalized graph or multigraph on its unobservable part. For computing of each vector of the basis solution space with linear estimate in the worst case we propose effective algorithms and data structures in the case when a support of the multigraph or graph for the sparse systems contains a cycles.