Algorithms

where each x_i is repeated m_i times.

1. Incremental calcula­tion of h_k(x₁, x₂, …, x_n), for increas­ing k, with O(n) increment step

2. Incremental calcula­tion of h_k(m₁ • x₁, m₂ • x₂, …, m_n • x_n) — which may be useful when ∑ m_i ≫ n

The same algo­rithm may be useful when the m_i are not integers (e.g., when calcu­lating a con­volu­tion of gamma dis­tribu­tions with vary­ing scale parameters). In this case the algo­rithm out­puts for each k the value

3. Incremental calcula­tion of φ_k(t; x₁, x₂, …, x_n)

4. If G(s) is the rational function

then the inverse Laplace trans­form of G(s) is the function

where A_i, k is given by:

If one modifies G(s) by incre­ment­ing m_j for some 1 ≤ j ≤ n, then g(t) is replaced by (g ∗ D_μj)(t), and the coeffi­cients A_i, k change as shown below:

If  j = n + 1 so that we are including a new fac­tor (s + μ_n + 1) in the denominator of G(s), in­sert the line m_j ← 0 before line 1 and append the line n ← n + 1 after line 12.

If the value of g(t) is needed only for a specific value of t, and if it is known that one m_j will be incre­mented repeatedly and no other m_i will in­crease, then a dif­fer­ent ver­sion of the algo­rithm can be used to recal­culate A_i, k only for i ≠ j, with­out accumulating the sum s. The sum of all the A_j, k terms can be recal­cu­lated at each itera­tion using the φ function above with­out cal­cu­lating the individual co­effi­cients A_j, k.

Note: Given any function g(t) of the form

with arbitrary coeffi­cients A_i, k, if we wish to cal­cu­late (g ∗ D_μj)(t), the same algo­rithm for up­dating the co­effi­cients works. However, the short­cut method of evalu­ating g(t) using the φ func­tion is not guaran­teed to work for arbi­trary A_i, k.