package orgeat

  1. Overview
  2. Docs

Parameters

module K : Scalar.S

Signature

type species_system = K.t Smol.Polynomial.Make(Literal.Variable).p Species.s Stdlib.Map.Make(Orgeat.Literal.Class).t
type solution_kind =
  1. | Poly of species_system
  2. | Seq of K.t
  3. | Tree of K.t * K.t Stdlib.Map.Make(Orgeat.Literal.Class).t

Translate a class_tree into a system of equations

val translate_class : 'a Combi.Make(K).combi_class -> species_system

Note for both translations: variables in h are prefixed with "T_", while in sampler_mapping they are prefixed with "s_"

Algorithm isWellFounded Characterization of well-founded systems See Definition 5.3 and Theorem 5.5. This condition is sufficient to use Newton's iteration to evaluate the generating function of the combinatorial system.

  • parameter s

    the mapping of known samplers appearing in the system

  • parameter h

    a vector of species

  • parameter j

    the Jacobian of h. Note that it is also the Jacobian of the companion system k, so it does not need to be computed multiple times.

  • returns

    true iff the system Y = H(Z,Y) is well founded

val newton_iteration : species_system -> K.t Smol.Polynomial.Make(Literal.Variable).p Species.s Smol.Matrix.Make(Literal.Class).m -> K.t -> K.t -> K.t Stdlib.Map.Make(Orgeat.Literal.Class).t option

Newton iteration

  • parameter s

    the mapping of known samplers appearing in the system

  • parameter h

    a vector of species such that Y = h(Z,Y) is well founded

  • parameter j

    the Jacobian of h

  • parameter epsilon

    the precision of the evaluation

  • parameter z

    the point of evaluation

  • returns

    some value approximating the solution at z with precision (at least) epsilon, or None if the iteration does not converges with the given parameters.

val eval_convergence_radius : species_system -> K.t Smol.Polynomial.Make(Literal.Variable).p Species.s Smol.Matrix.Make(Literal.Class).m -> K.t -> K.t * K.t Stdlib.Map.Make(Orgeat.Literal.Class).t option

Estimation of the convergence radius. Since the system is well founded, it exists and is between 0 and 1. Uses a bisection method: the newtown iteration method converges for a certain value iff it is inside the convergence disk (TODO: citation needed).

  • parameter s

    the mapping of known samplers appearing in the system

  • parameter h

    a vector of species such that Y = h(Z,Y) is well founded

  • parameter j

    the Jacobian of h

  • parameter epsilon

    the precision of the bisection method

  • returns

    approximation of the convergence radius of the system with precision epsilon.

val solve : species_system -> Literal.Class.t -> K.t -> int -> K.t * K.t Stdlib.Map.Make(Orgeat.Literal.Class).t option
val solve_class : 'a Combi.Make(K).combi_class -> K.t -> int -> K.t * K.t Stdlib.Map.Make(Orgeat.Literal.Class).t option