mdd_mcd.h File Reference

Miner-Ciardo-Donatelli approximate stationary analysis. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <string>
#include <utility>
#include <vector>
#include "line/api/mdd/mdd.h"
#include "line/api/mdd/mdd_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lstsq.h"
#include "line/util/matrix.h"

Include dependency graph for mdd_mcd.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mdd

Functions
template<class T>
MddMcdResult< T >	line::mdd::mdd_mcd (const MddStruct &mdds, const MddDescriptor< T > &desc, const MddMcdOptions &options=MddMcdOptions())
	Approximate stationary measures by decision-diagram-guided aggregation.

Detailed Description

Miner-Ciardo-Donatelli approximate stationary analysis.

Port of matlab/src/api/mdd/mdd_mcd.m, jline.api.mdd.Mdd_mcd and python/line_solver/api/mdd/mcd.py, after A.S. Miner, G. Ciardo, S. Donatelli, "Using the exact state space of a Markov model to compute approximate stationary measures", ACM SIGMETRICS 2000, pp.207-216.

Solve a structured CTMC whose EXACT reachable state space is stored in a decision diagram, by building and iterating K level-CTMCs. The method never forms the |S|-state generator or probability vector. It keeps one CTMC per level k, over states M_k = {(p,i_k)} with p a level-k node and i_k a local state on a non-null arc, and iterates the coupled system to a fixed point. The single approximation (Eq. 5) is Pr{i_k | alpha} = Pr{i_k | p}: the local-state law at level k depends only on the node p, not the full path above it, which the exact reachability the diagram encodes justifies. For product-form models the method is EXACT (paper Sec. 5), so on a single-class closed QN it reproduces SolverCTMC.

ORIENTATION. The paper indexes levels K (top/root) down to 1 (bottom/terminal); MDD uses level 0 as the root. This function works in the paper's orientation with 0-based indices, so paper level k (0 = bottom) maps to MDD level K-1-k and to station K-1-k. Getting this backwards silently mislabels every per-station metric.

Definition in file mdd_mcd.h.