TECHNICAL REPORT BU-CE-0016, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING

TITLE: Stochastic Automata Networks and Near Complete Decomposability

AUTHORS: Oleg Gusak, Tugrul Dayar, and Jean-Michel Fourneau

ABSTRACT: Stochastic automata networks (SANs) have been developed and
used in the last fifteen years as a modeling formalism for large systems
that can be decomposed into loosely connected components. In this work,
we extend the near complete decomposability concept of Markov chains
(MCs) to SANs so that the inherent difficulty associated with solving
the underlying MC can be forecasted and solution techniques based on
this concept can be investigated. A straightforward approach to finding
a nearly completely decomposable (NCD) partitioning of the MC underlying
a SAN requires the computation of the nonzero elements of its global
generator. This is not feasible for very large systems even in sparse
matrix representation due to memory and execution time constraints.
We devise an efficient solution algorithm to this problem that is based
on analyzing the NCD structure of each component of a given SAN.
Numerical results show that the given algorithm performs much better
than the straightforward approach.