pfqn_pas_nc.h File Reference

Normalizing constant G_C of one communicating class of a closed PASS-AND-SWAP (P&S) network, plus one aggregated delay. More...

#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_ca.h"
#include "line/api/pfqn/pfqn_ncoi.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for pfqn_pas_nc.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Typedefs
using	line::pfqn::PlacementOrder = std::vector<std::vector<int>>
	Placement order of one station: prec[i][j] != 0 iff class i must be placed before class j.

Functions
template<class T>
NcResult< T >	line::pfqn::pfqn_pas_nc (const std::vector< T > &Z, const std::vector< int > &N, const std::vector< OiRate< T > > &mu, const std::vector< PlacementOrder > &prec)
	Normalizing constant G_C of one communicating class of a closed PASS-AND-SWAP (P&S) network, plus one aggregated delay.
template<class T>
NcResult< T >	line::pfqn::pfqn_pas_nc (const std::vector< T > &Z, const std::vector< int > &N, const std::vector< OiRate< T > > &mu)
	Plain OI case (no placement order); prefer pfqn_ncoi, which is cheaper.

Detailed Description

Normalizing constant G_C of one communicating class of a closed PASS-AND-SWAP (P&S) network, plus one aggregated delay.

Templated port of matlab/src/api/pfqn/pfqn_pas_nc.m.

With a non-empty swap graph the ordered-state chain is reducible (Comte and Dorsman, 2021, arXiv:2009.12299): the recurrent communicating classes are the placement-order-adhering sets and the product form pi(c) = prod_m Phi_m(c_m)/G_C holds per class. This routine returns that per-class constant.

Method. Build station M's chain head-first: appending class r at chain position k = |occ|+1 is admissible iff no class already placed at that station must come after r, and contributes the reciprocal OI prefix rate 1/mu_M(occ+e_r); the chain may be finalized (recursing to station M-1) only when occ is a placement-order ideal at full multiplicity. Once every P&S station is peeled the residual population sits at the delay node with the multinomial weight prod_r Z_r^{N_r}/N_r!.

This is a MICROSTATE routine: it walks the ordered chains position by position, because with a placement order the reachable set is a set of ORDERINGS that does not collapse onto the count lattice. With an empty order the node count is sum_{b<=N} C(|b|+M-1,M-1) |b|!/prod_r b_r!, factorial in the total population – use pfqn_ncoi for the plain OI case, which returns the same constant on the count lattice.

The occupancy shift is carried as an explicit vector per station rather than by wrapping the callable in a new closure at every level as MATLAB does (shifted = @(state) active(state + e_r)). The two are the same function; the vector form avoids a closure chain whose depth is the total population.

Arithmetic: EXACT-CAPABLE, on the same terms as pfqn_ncoi.

Definition in file pfqn_pas_nc.h.