pfqn_perm.h File Reference

Permanent of a matrix with repeated columns, by Ryser's formula. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/util/population.h"

Include dependency graph for pfqn_perm.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
T	line::pfqn::pfqn_perm (const Matrix< T > &A, const std::vector< int > &m)
	Permanent of a matrix with repeated columns, by Ryser's formula.

Detailed Description

Permanent of a matrix with repeated columns, by Ryser's formula.

Templated port of matlab/src/util/perm.m, which the pfqn family uses in two places: the joint queue-length probability pfqn_joint (through its local Fper) and the LCFS normalizing constant pfqn_lcfsqn_nc.

For an (n x R) matrix A whose column k is repeated m_k times, n = sum_k m_k, the permanent of the expanded (n x n) matrix is

perm = (-1)^n sum_{0 <= f <= m} (-1)^{|f|} prod_k C(m_k, f_k) prod_{i=1}^{n} sum_k f_k A(i,k),

which costs prod_k (m_k + 1) evaluations rather than the n! of the definition. Collapsing the repeated columns is what makes the formula usable here at all: the queueing applications have n jobs but only R distinct classes, and R is small.

Arithmetic: EXACT-CAPABLE. Additions, multiplications and integer binomials only; the binomials are formed by the exact Pascal recurrence of num_nck, not by the floating-point nck, so a large multiplicity does not lose integrality.

Definition in file pfqn_perm.h.