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.poly<x**1024 + 1>

Parameters:

ParameterC++ typeDescription
valuePolynomial

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$, and ideal is the ring ideal $(p(x))$. Because all ideals in a single-variable polynomial ring are principal, the ideal is defined by a single polynomial.

#ring = #polynomial.ring<cmod=1234, ideal=#polynomial.polynomial<x**1024 + 1»

Parameters:

ParameterC++ typeDescription
cmodIntegerAttr
idealPolynomial

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:

ParameterC++ typeDescription
ring::mlir::heir::polynomial::RingAttrAn attribute specifying a ring.
encodingAttribute

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:

OperandDescription
lhspolynomial-like
rhspolynomial-like

Results:

ResultDescription
outputpolynomial-like

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:

AttributeMLIR TypeDescription
input::mlir::heir::polynomial::PolynomialAttrAn attribute containing a single-variable polynomial.

Results:

ResultDescription
outputAn element of a polynomial quotient ring

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:

OperandDescription
inputranked tensor of integer values

Results:

ResultDescription
outputAn element of a polynomial quotient ring

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:

OperandDescription
inputAn element of a polynomial quotient ring

Results:

ResultDescription
degreeindex
coefficientinteger

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:

OperandDescription
inputAn element of a polynomial quotient ring
monomialDegreeindex

Results:

ResultDescription
outputAn element of a polynomial quotient ring

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:

OperandDescription
coefficientinteger
degreeindex

Results:

ResultDescription
outputAn element of a polynomial quotient ring

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:

OperandDescription
lhspolynomial-like
rhspolynomial-like

Results:

ResultDescription
outputpolynomial-like

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:

OperandDescription
polynomialpolynomial-like
scalarinteger

Results:

ResultDescription
outputpolynomial-like

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:

OperandDescription
lhspolynomial-like
rhspolynomial-like

Results:

ResultDescription
outputpolynomial-like

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:

OperandDescription
inputAn element of a polynomial quotient ring

Results:

ResultDescription
outputranked tensor of integer values