Polynomial

The Polynomial dialect defines single-variable polynomial types and operations.

The simplest use of this dialect is to do math in a polynomial ring R[x], where R is another MLIR integer type like u32, and lower to arith.

More generally, this dialect represent polynomial operations in a quotient polynomial ring Z/qZ[X]/(f(x)) for some integer q and polynomial f(x). Polyomials p(x), q(x) are equal in this ring if they have the same remainder when dividing by f(x). The canonical representative for a polynomial p(x) is has degree less than deg(f(x)). When a modulus is given, ring operations are polynomial addition and multiplication performed with reductions modulo f(x) and q.

Polynomial attributes

PolynomialAttr

An attribute containing a single-variable polynomial.

#poly = #_polynomial.polynomial<x**1024 + 1>

Parameters:

RingAttr

An attribute specifying a ring.

An attribute specifying a polynomial quotient ring with integer coefficients, $\mathbb{Z}/n\mathbb{Z}[x] / (p(x))$.

cmod is the coefficient modulus $n$, ideal is the ring ideal $(p(x))$, and root is a primitive 2d-th root of unity of cmod where d is the degree of p(x). Because all ideals in a single-variable polynomial ring are principal, the ideal is defined by a single polynomial. root is optionally specified to a desired 2n-th primitive root of unity for the coefficient ring of the polynomial ring. If it is not provided then a pre-computed value is used instead for ops that need it. The semantics of this root (e.g., its degree) are determined by the lowerings.

#ring = #_polynomial.ring<cmod=1234, ideal=#_polynomial.polynomial<x1024 + 1» #ring = #_polynomial.ring<cmod=256, ideal=#_polynomial.polynomial<x4 + 1>, root=31>

Parameters:

Polynomial types

PolynomialType

An element of a polynomial quotient ring

Syntax:

!_polynomial.polynomial<
  ::mlir::heir::polynomial::RingAttr,   # ring
  Attribute   # encoding
>

A type for polynomials in a polynomial quotient ring.

Parameters:

Polynomial ops

_polynomial.add (heir::polynomial::AddOp)

Addition operation between polynomials.

Syntax:

operation ::= `_polynomial.add` `(` operands `)` attr-dict `:` qualified(type($output))

Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.constant (heir::polynomial::ConstantOp)

Define a constant polynomial via an attribute.

Syntax:

operation ::= `_polynomial.constant` $input attr-dict `:` qualified(type($output))

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Results:

_polynomial.from_tensor (heir::polynomial::FromTensorOp)

Creates a polynomial from integer coefficients stored in a tensor.

Syntax:

operation ::= `_polynomial.from_tensor` $input attr-dict `:` type($input) `->` qualified(type($output))

polynomial.from_tensor creates a polynomial value from a tensor of coefficients. The input tensor must list the coefficients in degree-increasing order.

The input one-dimensional tensor may have size at most the degree of the ring’s ideal generator polynomial, with smaller dimension implying that all higher-degree terms have coefficient zero.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.intt (heir::polynomial::INTTOp)

Computes the reverse integer Number Theoretic Transform (NTT).

Syntax:

operation ::= `_polynomial.intt` $input attr-dict `:` qualified(type($input)) `->` type($output)

polynomial.intt computes the reverse integer Number Theoretic Transform (INTT) on the input tensor. This is the inverse operation of the polynomial.ntt operation.

The input tensor is interpreted as a point-value representation of the output polynomial at powers of a primitive $n$-th root of unity (see polynomial.ntt). The ring of the polynomial is taken from the required encoding attribute of the tensor.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.leading_term (heir::polynomial::LeadingTermOp)

Compute the leading term of the polynomial.

Syntax:

operation ::= `_polynomial.leading_term` operands attr-dict `:` qualified(type($input)) `->` `(` type($degree) `,` type($coefficient) `)`

The degree of a polynomial is the largest $k$ for which the coefficient $a_k$ of $x^k$ is nonzero. The leading term is the term $a_k x^k$, which this op represents as a pair of results.

Operands:

Results:

_polynomial.monomial_mul (heir::polynomial::MonomialMulOp)

Multiply a polynomial by a monic monomial.

Syntax:

operation ::= `_polynomial.monomial_mul` operands attr-dict `:`  `(` type(operands) `)` `->` type(results)

In the ring of polynomials mod $x^n - 1$, monomial_mul can be interpreted as a cyclic shift of the coefficients of the polynomial. For some rings, this results in optimized lowerings that involve rotations and rescaling of the coefficients of the input.

Interfaces: InferTypeOpInterface

Operands:

Results:

_polynomial.monomial (heir::polynomial::MonomialOp)

Create a polynomial that consists of a single monomial.

Syntax:

operation ::= `_polynomial.monomial` operands attr-dict `:`  `(` type(operands) `)` `->` type(results)

Operands:

Results:

_polynomial.mul (heir::polynomial::MulOp)

Multiplication operation between polynomials.

Syntax:

operation ::= `_polynomial.mul` `(` operands `)` attr-dict `:` qualified(type($output))

Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.mul_scalar (heir::polynomial::MulScalarOp)

Multiplication by a scalar of the field.

Syntax:

operation ::= `_polynomial.mul_scalar` operands attr-dict `:` qualified(type($polynomial)) `,` type($scalar)

Traits: Elementwise, Scalarizable, Tensorizable, Vectorizable

Interfaces: InferTypeOpInterface

Operands:

Results:

_polynomial.ntt (heir::polynomial::NTTOp)

Computes point-value tensor representation of a polynomial.

Syntax:

operation ::= `_polynomial.ntt` $input attr-dict `:` qualified(type($input)) `->` type($output)

polynomial.ntt computes the forward integer Number Theoretic Transform (NTT) on the input polynomial. It returns a tensor containing a point-value representation of the input polynomial. The output tensor has shape equal to the degree of the ring’s ideal generation polynomial. The polynomial’s RingAttr is embedded as the encoding attribute of the output tensor.

Given an input polynomial $F(x)$ (over a ring with degree $n$) and a primitive $n$-th root of unity $\omega_n$, the output is the list of $n$ evaluations

$f_k = F(\omega_n^k) ; k \in [0, n)$ The choice of primitive root is determined by subsequent lowerings.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.sub (heir::polynomial::SubOp)

Subtraction operation between polynomials.

Syntax:

operation ::= `_polynomial.sub` `(` operands `)` attr-dict `:` qualified(type($output))

Traits: AlwaysSpeculatableImplTrait, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results:

_polynomial.to_tensor (heir::polynomial::ToTensorOp)

Creates a tensor containing the coefficients of a polynomial.

Syntax:

operation ::= `_polynomial.to_tensor` $input attr-dict `:` qualified(type($input)) `->` type($output)

polynomial.to_tensor creates a tensor value containing the coefficients of the input polynomial. The output tensor contains the coefficients in degree-increasing order.

Operations that act on the coefficients of a polynomial, such as extracting a specific coefficient or extracting a range of coefficients, should be implemented by composing to_tensor with the relevant tensor dialect ops.

The output tensor has shape equal to the degree of the ring’s ideal generator polynomial, including zeroes.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands:

Results: