Exact normalizing constant of a SINGLE-CLASS closed network whose stations are LIMITED load dependent, i.e. More...

#include <algorithm>
#include <cstddef>
#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 dependency graph for pfqn_lldsingle.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
NcResult< T >	line::pfqn::pfqn_lldsingle (const Matrix< T > &L, int N, const Matrix< T > &mu)
	Exact normalizing constant of a SINGLE-CLASS closed network whose stations are LIMITED load dependent, i.e.

Detailed Description

Exact normalizing constant of a SINGLE-CLASS closed network whose stations are LIMITED load dependent, i.e.

whose rate functions stay constant past a per-station threshold.

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

Same recursion, same arithmetic and bit-identical results to pfqn_gldsingle, but with the rate-offset axis truncated at that threshold instead of at the population. Unrolling the recursion of pfqn_gldsingle,

g(m, n, t) = g(m-1, n, 1) + L(m) g(m, n-1, t+1) / mu(m, t)

shows that its third index is an offset into station m's rate function,

g(m,n,t) = sum_{j=0..n} prod_{i=0..j-1} L(m)/mu(m,t+i) * g(m-1,n-j,1)

so once t >= s_m, where s_m is the population past which mu(m, .) stays constant, every factor is mu(m, s_m), the product collapses to (L(m)/mu(m,s_m))^j and

g(m, n, t) = g(m, n, s_m) for all t >= s_m

The N - s_m upper slices that pfqn_gldsingle materializes are duplicates of one another. Capping the offset at s_m and reading g(m, n-1, min(t+1, s_m)) keeps every value the answer reads.

COST. O(N sum_k s_k) time against O(M N^2) for pfqn_gldsingle, and O(N max_k s_k) space against O(M N^2), the station levels being rolled. On a multiserver model, where s_k is the server count, this is LINEAR in the population rather than quadratic. Unlike pfqn_explicit_ld, which reaches the same asymptotics through Gordon's alternating partial fraction, this loses no digits to cancellation at T = double: the arithmetic performed is a SUBSET of pfqn_gldsingle's, so the two agree to the last bit in every field.

There is no gain on a station whose rates never settle, an infinite server mu(m,n) = n being the usual case: it gets s_m = N and costs what it costs in pfqn_gldsingle. The saving is over the OTHER stations, so a model carrying one delay among M queues drops from O(M N^2) to O(N^2 + N sum_k s_k).

Arithmetic: EXACT-CAPABLE, and the threshold scan is what keeps it so. It compares rates with the field's own operator==, never a tolerance: at T = Rational or T = Real<D> a tolerance has no meaning, and at T = double a multiserver row repeats its tail exactly. A MISSED tie only costs time, since the routine then behaves as pfqn_gldsingle; a FALSE tie would be a wrong answer, which exact comparison cannot produce. The reference carries an eps-relative tolerance instead, being confined to IEEE double.

As in pfqn_gldsingle this port keeps only the linear recursion, the reference's log-space branch being a range-management device for IEEE double, and an infinite rate is accepted the same way: the term L/mu vanishes.

Definition in file pfqn_lldsingle.h.

Namespaces

Functions

Detailed Description