Package jline.api.pfqn.nc

Class Pfqn_gerasimov

java.lang.Object
jline.api.pfqn.nc.Pfqn_gerasimov
public final class Pfqn_gerasimov extends Object

  • Method Details

    • pfqn_gerasimov

      public static Ret.pfqnNc pfqn_gerasimov(Matrix L, Matrix N, Matrix Z, double tol, int maxterms)
      Exact normalizing constant of a closed multiclass product-form network by ITERATED RESIDUES of its rational generating function, one class at a time.

      Gerasimov (1995) evaluates 

         G(N_1,...,N_R) = (2 pi i)^-R int_G1 ... int_GR
                      prod_s z_s^(N_s-1) prod_i (1 - sum_s x_is/z_s)^-1
      by residues, and gives the resulting CLOSED FORM only for R = 1 (Thm 1-2) and R = 2 (Thm 3 for simple poles, Thm 4 for multiple ones), stating that "for three or more classes of customers, the normalizing constants can be found by numerical methods". This routine implements the residue elimination itself, so the closed form is produced for ANY R; at R = 2 it reproduces Thm 3/4 term by term.

      Written as a coefficient of the u_s = 1/z_s series, 

         G(N) = [prod_s u_s^(N_s)] exp(sum_s Z_s u_s) prod_i (1 - sum_s x_is u_s)^-1,
      every factor is AFFINE in u, so singling out u_r gives f = A - B u_r with A affine in the surviving variables. Partial fractions in u_r, 
         [u_r^n] prod_j (A_j - B_j u_r)^-m_j
     = sum_j sum_{k=0}^{m_j-1} (-B_j)^-k C(n+m_j-k-1,n) B_j^n A_j^-(n+m_j-k)
       [t^k] prod_{l!=j} (C_jl - B_l t)^-m_l,   C_jl = (A_l B_j - B_l A_j)/B_j,
      map a sum of products of affine powers into another one with one variable fewer, and R-1 such steps leave a univariate coefficient extraction. At R = 2 the single step returns one term per station i, with outer factor x_i2^(N_2+M-1)/prod_(k!=i)(x_i2-x_k2), a pole of order N_2+1 at x_i1 and simple poles at the paper's z_1ik = (x_k1 x_i2 - x_i1 x_k2)/(x_i2 - x_k2): exactly Thm 3, with the multiple poles of Thm 4 (his xi_i < M) handled by the same step. Tied x_i2, vanishing x_i2 and identical station rows, all outside the paper's hypotheses, are ordinary cases here.

      Cost. Let M be the number of stations and order the populations N_(1) <= ... <= N_(R). The first elimination turns the single input term into M, and every later one multiplies the count by C(S+M-1,M-1) + M-1, where S is the total population already eliminated: a pole of order S+1 has to be differentiated against the M-1 remaining ones. The innermost extraction then convolves M series of length N_(1). Hence R = 1 costs O(M N), Buzen's own cost; R = 2 costs O(M^2 N_(1)^2), INDEPENDENT OF N_(2); and R >= 3 costs the same times prod_(r=3..R) C(N_(r)+M-1,M-1). The R = 2 line is the reason to reach for this method: a population removed by residues enters only as a pole ORDER, i.e. through binomial coefficients, so it costs nothing at all. On a 4-station two-class model at N = [6, 20000] this returns lG in 0.1 ms where pfqn_ca needs 79 s, to the same 1.3e-16. For R >= 3 the term count is polynomial in the populations of degree (M-1)(R-2) and exponential in R, which is why the paper stops at two classes and why maxterms exists.

      Conditioning. The sum is alternating, exactly as the paper writes it, and two decisions keep it usable: near-coincident poles are merged under a RELATIVE tolerance, so they are one multiple pole rather than two nearly cancelling simple ones, and the class left for the innermost extraction is the one with the SMALLEST population, because that population is the degree the final, sign-indefinite series is carried to. Measured on 372 random models against pfqn_ca: median 2.0e-16, p90 4.6e-15, p99 1.1e-11, worst 1.5e-09. On an ill-conditioned demand matrix pfqn_ca or pfqn_nc are still the safer routes to the same number.

      Parameters:
      L - service demand matrix (M x R), L(i,r) = demand of class r at station i
      N - population vector (1 x R), nonnegative integers
      Z - think time vector (1 x R), may be null. A delay contributes the entire factor exp(sum_s Z_s u_s), handled exactly by convolving its Poisson coefficients into each elimination.
      tol - relative tolerance for declaring two affine forms proportional, hence one pole rather than two
      maxterms - cap on the number of residue terms carried between eliminations. Exceeding it is an error, not a truncation: a truncated residue sum is not a bound or an approximation of G, it is a wrong number.
      Returns:
      the normalizing constant and its logarithm

    • pfqn_gerasimov

      public static Ret.pfqnNc pfqn_gerasimov(Matrix L, Matrix N, Matrix Z)
      Defaults: tol = 1e-12, maxterms = 200000.

    • pfqn_gerasimov

      public static Ret.pfqnNc pfqn_gerasimov(Matrix L, Matrix N)
      Delay-free case.