pfqn_dmlin.h File Reference

de Souza e Silva-Muntz Improved Linearizer (IL). More...

#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_amva_common.h"
#include "line/api/pfqn/pfqn_bs.h"
#include "line/api/pfqn/pfqn_egflinearizer.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_dmlin.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_dmlin (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const std::vector< SchedStrategy > &type, double tol, int maxiter, const Matrix< T > &QN0, int npasses=3)
	de Souza e Silva-Muntz Improved Linearizer (IL).
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_dmlin (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z)
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_dmlin (const Matrix< T > &L, const std::vector< int > &N)

Detailed Description

de Souza e Silva-Muntz Improved Linearizer (IL).

Templated port of matlab/src/api/pfqn/pfqn_dmlin.m, cross-checked against jar/src/main/java/jline/api/pfqn/mva/Pfqn_dmlin.java. E. de Souza e Silva, R. R. Muntz, "A note on the computational cost of the Linearizer algorithm for queueing networks", IEEE Trans. Computers 39(6), 1990. Linearizer evaluates the arrival-instant queue length as

A_k^(c)(n) = sum_i (n_i - delta_c^(i)) [Q_ik(n)/n_i + Delta^(i)_ck],

re-summing the C Delta-terms at every Core iteration, at every one of the C+1 populations: O(K C^3) per refresh pass. IL splits that sum into the part that moves with the Core iterate and the part that does not,

A_k^(c)(n) = sum_i (n_i - delta_c^(i)) Q_ik(n)/n_i + xi_ck(n), xi_ck(N) = sum_i (N_i - delta_c^(i)) Delta^(i)_ck, xi_ck(N - 1_j) = xi_ck(N) - Delta^(j)_ck,

so the C K aggregates xi are computed ONCE per refresh pass and each Core iteration then costs O(K C) instead of O(K C^2). Time drops to O(K C^2) with the space unchanged at O(K C^2), and, because the split is an IDENTITY and not an approximation, the fixed point is the one Linearizer reaches: pfqn_dmlin and pfqn_linearizer agree to round-off. Transcribing (2.50) of the Wang (1997) survey literally – xi_ck(N - 1_j) ~= xi_ck(N), dropping the Delta^(j)_ck correction – breaks that agreement and costs about an order of magnitude of accuracy, so the correction is not optional.

Arithmetic: field operations only, so each iterate is EXACT in rational arithmetic; the Core stops on enorm(Q_{k+1} - Q_k) < tol, so the returned value still depends on the stopping rule.

Definition in file pfqn_dmlin.h.