GitHub

Rankings

Let $A$ be an action polynomial ring with $m$ elementary symbols and $n$ commuting action maps. Define $\underline{m} := \{1, \ldots, m\}$, with $m \in \mathbb{N}$.

Many algorithms require the jet variables of $A$ to be totally ordered. This is achieved using rankings. Analogous to how monomial orderings in a multivariate polynomial ring in $n$ variables correspond to total orderings of $\mathbb{N}_0^n$, rankings of jet variables correspond to total orderings of $X := \underline{m} \times \mathbb{N}_0^n$.

Specifically, we identify a jet variable $(u_i)_J \in A$ with the pair $(i, J) \in X$.

Riquier rankings

The rankings we use are called Riquier rankings. By definition, these are rankings of $X$ that extend to a ranking of $\{1\} \times \mathbb{N}^{m+n}$.

Equivalently, there exists a positive integer $s$ and an $s \times (m+n)$ real matrix $M$ such that the total ordering of the jet variables defined by $X$ coincides with the ordering obtained from the matrix ordering on $\mathbb{N}_0^{m+n}$ defined by $M$.

For this construction, we identify a jet variable $(u_i)_J \in A$ with $(e_i, J) \in \mathbb{N}_0^{m+n}$, where $e_i$ is the $i$-th unit row and restrict ourselves to integer matrices $M$. In this context, we call $M$ a Riquier matrix.

Note

Not all Riquier rankings are obtained from integral Riquier matrices. However, this is the case if we only require a total ordering of a finite subset of $X$. Thus, only considering integer matrices is sufficient for practical use.

Constructing Riquier rankings

In OSCAR, we define rankings, i.e., total orderings of $X$, by combining the natural less-than relation on $\underline{m}$ with a customizable total ordering on $\mathbb{N}_0^n$. The latter is constructed as a matrix ordering; see index_ordering_matrix.

The way of combining of these two total orderings to obtain a total ordering of $X$ is specified by an ordered partition of $\underline{m}$, i.e. by grouping the elements of $\underline{m}$ into blocks. The first block is considered largest and so on. See partition.

Consider two elements $x_1 = (i_1, J_1), x_2 = (i_2, J_2)$ \in $X$. Then $x_1 < x_2$ if and only if:

  1. The block of $i_1$ is smaller than the one of $i_2$.
  2. $i_1$ and $i_2$ are in the same block and $J_1 < J_2$ with respect to the total ordering on $\mathbb{N}_0^n$.
  3. $i_1$ and $i_2$ are in the same block, $J_1 = J_2$ and $i_1 < i_2$.

Each action polynomial ring has an internal field ranking, which can be modified using the set_ranking!-method.

set_ranking! — Function
set_ranking!(A::ActionPolyRing;
             partition_name::Symbol = :default,
             index_ordering_name::Symbol = :default,
             partition::Vector{Vector{Int}} = Vector{Int}[],
             index_ordering_matrix::ZZMatrix = zero_matrix(ZZ, 0, 0))

This method configures the ranking of the action polynomial ring A, using an ordered partition of the elementary symbols and a monomial ordering on the indices. The ranking can be specified either by choosing predefined naming options or by explicitly providing a custom configuration.

Keyword Arguments

  • partition_name: Determines the partition of the elementary symbols of dpr. Supported values are:

    • :top: groups all elementary symbols into a single block,
    • :pot: separates each elementary symbol into its own block,
    • :default: uses :top unless a custom partition is specified.

  • index_ordering_name: Specifies the ordering on the multiindices. Supported values are:

    • :lex: lexicographic ordering,
    • :deglex: degree lexicographic ordering,
    • :invlex: inverse lexicographic ordering,
    • :deginvlex: degree inverse lexicographic ordering,
    • :degrevlex: degree reverse lexicographic ordering,
    • :default: uses :lex unless a custom matrix is specified.

  • partition: A custom partition of the elementary symbols, represented as a vector of characteristic vectors. The elementary symbols corresponding to the first characteristic vectors are considered largest and so on.

  • index_ordering_matrix: A custom matrix representing a monomial ordering on the indices. Its number of columns must equal n_action_maps(A).

Examples

julia> dpr = differential_polynomial_ring(ZZ, [:a, :b, :c], 4; partition_name=:pot, index_ordering_name = :degrevlex)[1]; ranking(dpr)
Ranking of differential polynomial ring in 3 elementary symbols over ZZ
with elementary symbols partitioned by
  [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
and ordering of the indices defined by
  [1    1    1    1]
  [0    0    0   -1]
  [0    0   -1    0]
  [0   -1    0    0]

julia> set_ranking!(dpr; partition = [[0,1,1],[1,0,0]], index_ordering_matrix = identity_matrix(ZZ, 4))
Ranking of differential polynomial ring in 3 elementary symbols over ZZ
with elementary symbols partitioned by
  [[0, 1, 1], [1, 0, 0]]
and ordering of the indices defined by
  [1   0   0   0]
  [0   1   0   0]
  [0   0   1   0]
  [0   0   0   1]

julia> set_ranking!(dpr)
Ranking of differential polynomial ring in 3 elementary symbols over ZZ
with elementary symbols partitioned by
  [[1, 1, 1]]
and ordering of the indices defined by
  [1   0   0   0]
  [0   1   0   0]
  [0   0   1   0]
  [0   0   0   1]
Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
Note

set_ranking! is also called upon construction with difference_polynomial_ring or differential_polynomial_ring. These constructors allow for the same keywords.

parent — Method
parent(r::ActionPolyRingRanking)

Return the action polynomial ring A with r = ranking(A).

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
ranking — Method
ranking(dpr::Union{DifferencePolyRing, DifferentialPolyRing}) -> ActionPolyRingRanking

Return the ranking of the jet variables of the difference or differential polynomial ring dpr.

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
riquier_matrix — Method
riquier_matrix(r::ActionPolyRingRanking) -> ZZMatrix

Return a Riquier matrix that induces the ranking r of the action polynomial ring A, where r = ranking(A).

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
index_ordering_matrix — Method
index_ordering_matrix(r::ActionPolyRingRanking) -> ZZMatrix

Return the matrix inducing the monomial ordering of the multiindices defined by the ranking r of the action polynomial ring A, where r = ranking(A).

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
partition — Method
partition(r::ActionPolyRingRanking) -> Vector{Vector{Int}}

Return the partition of the elementary symbols defined by the ranking r of the action polynomial ring A, where r = ranking(A).

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source