[mlir][polynomial] remove incorrect canonicalization rule (#110318)

arith.add for tensor does not mod coefficientModulus, and it may
overflow; the result could be incorrect

It should be rewritten a

[mlir][polynomial] remove incorrect canonicalization rule (#110318)

arith.add for tensor does not mod coefficientModulus, and it may
overflow; the result could be incorrect

It should be rewritten as modular arithmetic instead of arith

Revert https://github.com/llvm/llvm-project/pull/93132
Addresses https://github.com/google/heir/issues/749

Cc @j2kun

show more ...

mlir/LogicalResult: move into llvm (#97309)

This patch is part of a project to move the Presburger library into
LLVM.

[mlir][polynomial] ensure primitive root calculation doesn't overflow (#93368)

Rebased over https://github.com/llvm/llvm-project/pull/93243

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.

[mlir][polynomial] ensure primitive root calculation doesn't overflow (#93368)

Rebased over https://github.com/llvm/llvm-project/pull/93243

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

show more ...

[mlir][polynomial] verify from_tensor coeff type (#93243)

Rebased over https://github.com/llvm/llvm-project/pull/93227

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

[polynomial] Move primitive root attribute to ntt/intt ops. (#93227)

Better design to put semantics on the ops, and in this case the ntt/intt
op can lower in multiple ways depending on the polynomi

[polynomial] Move primitive root attribute to ntt/intt ops. (#93227)

Better design to put semantics on the ops, and in this case the ntt/intt
op can lower in multiple ways depending on the polynomial ring modulus
(it can need an nth root of unity for cyclic polymul -> ntt, or a 2nth
root for negacyclic polymul -> ntt)

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

show more ...

[polynomial] distribute add/sub through ntt to reduce ntts (#93132)

Addresses
https://github.com/google/heir/issues/542#issuecomment-2126175775

Co-authored-by: Jeremy Kun <j2kun@users.noreply.gi

[polynomial] distribute add/sub through ntt to reduce ntts (#93132)

Addresses
https://github.com/google/heir/issues/542#issuecomment-2126175775

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

show more ...

[mlir][polynomial] use typed attributes for polynomial.constant op (#92818)

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

Poly canonicalization (#91410)

Adds simple canonicalization rules to the polynomial dialect. Mainly to
get the boilerplate incorporated before more substantial
canonicalization patterns are added.

Poly canonicalization (#91410)

Adds simple canonicalization rules to the polynomial dialect. Mainly to
get the boilerplate incorporated before more substantial
canonicalization patterns are added.

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

show more ...

Upstream polynomial.ntt and polynomial.intt (#90992)

These two ops represent a number-theoretic transform of a polynomial to
a tensor of evaluations of the polynomial at a list of powers of
primitiv

Upstream polynomial.ntt and polynomial.intt (#90992)

These two ops represent a number-theoretic transform of a polynomial to
a tensor of evaluations of the polynomial at a list of powers of
primitive roots of the polynomial.

To support this, a new optional attribute is added to the ring attribute
to specify the primitive root of unity used for the NTT. A verifier for
the op is added to ensure the chosen root is a primitive nth root of
unity.

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>
Co-authored-by: Oleksandr "Alex" Zinenko <ftynse@gmail.com>

show more ...

polynomial: Add basic ops (#89525)

Adds a few basic polynomial ops.

- add, sub, mul
- mul_scalar
- leading_term, monomial_mul, monomial (useful for lowering `mul` to
standard MLIR)
- from_ten

polynomial: Add basic ops (#89525)

Adds a few basic polynomial ops.

- add, sub, mul
- mul_scalar
- leading_term, monomial_mul, monomial (useful for lowering `mul` to
standard MLIR)
- from_tensor, to_tensor, constant

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>
Co-authored-by: Oleksandr "Alex" Zinenko <ftynse@gmail.com>

show more ...

Add a polynomial dialect shell, attributes, and types (#72081)

RFC:
https://discourse.llvm.org/t/rfc-a-poly-dialect-for-polynomial-arithmetic/73891

This PR implements the minimal work needed to

Add a polynomial dialect shell, attributes, and types (#72081)

RFC:
https://discourse.llvm.org/t/rfc-a-poly-dialect-for-polynomial-arithmetic/73891

This PR implements the minimal work needed to represent the polynomial
type such that it can be tested with `lit`.

In this PR:

- Dialect shell
- `Polynomial` data structure needed for folding
- Polynomial attributes (`PolynomialAttr` and `RingAttr` which store a polynomial)
- `polynomial.polynomial` type
- Basic lit tests

---------

Co-authored-by: Jeremy Kun <j2kun@users.noreply.github.com>

show more ...