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

Abstract

Последовательная композиция обеспечивает дополнительное ускорение вычислений за счёт решения последовательности систем меньшей размерности для подмножеств контактных позиций. Для формального представления декомпозиции на функциональные подсети использован мультиграф. Так как последовательная композиция сжимает граф в единственную вершину, задача названа коллапсом мультиграфа. Ширина коллапса соответствует размерности решаемых систем. Изучены свойства коллапса; получены оценки верхней и нижней границы ширины коллапса. Предложен простой и эффективный эвристический алгоритм коллапса. Результаты коллапса произвольных графов с помощью этого алгоритма показали, что он обеспечивает ширину коллапса, близ-кую к оптимальной.