Factor Join Trees in Systems Exploration
Baras, John S.
Date: November 29 - December 01, 2011
The interaction of connected components creates complexity impeding the analysis of large systems. Thorough exploration, appearing as formal verification, optimization or constraint satisfaction typically has a complexity that is either a high order polynomial or an exponential function of system size. However, for a large class of systems the essential complexity is linear in system size and exponential in treewidth which makes the previous notion of exponential complexity in system size an accidental overestimate.
In this paper, we demonstrate how this reduced complexity can be achieved using summary propagation on factor graphs. We describe summary propagation in terms of operations belonging to a commutative semiring-weighted relational algebra. We show how by appropriate selection of the commutative semiring, the same solution applies to propositional satisfiability, inference on Bayesian networks and a mixed integer linear optimization problem motivated by the power restoration problem for distributed, autonomous networks. This solution leads to a non-iterative distributed algorithm that operates on local data.
While weighted relational algebraic operators are used as the basic means of calculation, the algorithm presented works only on factor graphs that are trees. This requires the calculation of a non-unique structure called a join tree, which can be trivially generated from a unique structure called a cliqueseparator graph, which can be computed in linear time from a SysML Parametric Diagram description of the system for chordal systems1 . Interesting artifacts arise from this structural analysis which may be interpreted as interfaces and components. The framework also contains mathematical artifacts that may be interpreted as hierarchy and abstraction. We develop a tool to assist in the structural analysis described and implementations of the described algorithms.Download Full Paper