Эффективные алгоритмы декомпозиции линейных недоопределенных систем с матрицей инцидентности мультиграфа

Abstract

Рассматриваются неопределенные системы линейных алгебраических уравнений (СЛАУ) в которых наряду с уравнениями системы, составляющими вложенную сетевую структуру блочно-диагонального вида, содержится общая часть. При этом, каждый блок разреженной части системы является матрицей инцидентности графа. На основании результатов из теории сложности вычислений и теоретико-графовых свойств матрицы инцидентности графа получены эффективные методы декомпозиции линейных систем.