 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
RECAL (REcursive CALculation) for the exact normalizing constant of a closed product-form network (Conway and Georganas 1986). More...
#include <cmath>#include <cstddef>#include <limits>#include <type_traits>#include <vector>#include "line/api/pfqn/pfqn_ca.h"#include "line/num/number.h"#include "line/util/error.h"#include "line/util/matrix.h"#include "line/util/population.h"Go to the source code of this file.
Namespaces | |
| namespace | line |
| namespace | line::pfqn |
Functions | |
| template<class T> | |
| NcResult< T > | line::pfqn::pfqn_recal (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const std::vector< int > &m0) |
| RECAL (REcursive CALculation) for the exact normalizing constant of a closed product-form network (Conway and Georganas 1986). | |
| template<class T> | |
| NcResult< T > | line::pfqn::pfqn_recal (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z) |
| Overload with unit station multiplicities. | |
| template<class T> | |
| NcResult< T > | line::pfqn::pfqn_recal (const Matrix< T > &L, const std::vector< int > &N) |
| Overload without think times. | |
RECAL (REcursive CALculation) for the exact normalizing constant of a closed product-form network (Conway and Georganas 1986).
Templated port of matlab/src/api/pfqn/pfqn_recal.m, cross-checked against mp_pfqn's recal/recal-multi-exact.c for the exact path.
Where convolution recurses on stations over the population lattice, RECAL recurses on jobs over the space of station multiplicity vectors. Jobs are added one at a time, class 0 first, and the state carried between steps is a function g_n indexed by a multiplicity vector m with sum(m) = Ntot - n:
g_0(m) = 1 for all sum(m) = Ntot g_n(m) = ( Z_r g_{n-1}(m + e_delay)
where r is the class of the n-th job, n_r its index within that class, and m0(j) the multiplicity of station j. The answer is g_Ntot(0), the single state with an empty multiplicity vector. Every operation is a field operation (the only division is by the small integer n_r), so the recursion is exact in rational arithmetic with no reformulation, which is what makes RECAL usable as an exactness oracle for the rest of the pfqn family.
Delay column: think time enters as one extra column of m, appended after the M queueing stations. It is allocated only when some class has a non-zero think time, following mp_pfqn. MATLAB always carries the column; with Z = 0 the column is a spectator (g never reads across it and the level-0 value is 1 everywhere), so the returned constant is identical and only the size of the intermediate arrays differs.
Station consolidation: stations with identical demand rows are merged and their multiplicities added, which is exactly what the (m_j + m0_j - 1) coefficient is for. This mirrors pfqn_unique in the MATLAB reference and shrinks the state space from multichoose(M+1, Ntot) to multichoose(M'+1, Ntot). Rows are compared for exact equality rather than with the MATLAB 1e-14 tolerance: merging rows that only nearly agree would perturb the constant, which an exact-capable algorithm must not do.
Scaling: as for convolution, in IEEE double the recursion can leave the exponent range, so the same power-of-two rescaling of pfqn_ca is applied there and nowhere else. G is homogeneous of degree Ntot in (L, Z), so dividing every demand and think time by 2^k divides G by exactly 2^(k*Ntot), and the recovery is an exponent adjustment rather than an exp().
Definition in file pfqn_recal.h.
1.18.0