Add multivariate polynomial support

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations

https://www.arkworks.rs

Apache License 2.0

776 stars 209 forks source link

Add multivariate polynomial support #261

Closed ryanleh closed 3 years ago

ryanleh commented 4 years ago

Renamed all univariate structs to differentiate
Added dense + sparse multivariate coefficient representations which support basic addition/subtraction and evaluation

Plan to add some further functionality and evaluation representation in the near future

weikengchen commented 4 years ago

ah, cargo fmt --all may help. Some IDE support automatic rustfmt when saving (such as Clion).

weikengchen commented 4 years ago

as for no_std, I have a hard feeling: https://github.com/rust-ndarray/ndarray/issues/708

Ndarray does not support no_std at this moment. Maybe we need a word of wisdom from Pratyush. @Pratyush Should we try to see if there are any similar libraries with no_std? How serious is no_std?

ryanleh commented 4 years ago

Hmm not sure what's happening, running rustfmt on the exact files it's complaining about locally doesn't do anything (cargo fmt --all also doesn't change anything).

And ya, didn't think about the issue with ndarray. Honestly, the dense representation probably isn't going to be used that much, so if it is an issue removing it is probably fine.

weikengchen commented 4 years ago

Let us ~wall~ wait for the stable/nightly CI to finish. I can have a try of rustfmt after.

weikengchen commented 4 years ago

Ah, my local rustfmt did not complain about anything. Maybe let us ignore that for a while...

Pratyush commented 4 years ago

Re Rustfmt, you might be using nightly, so it’s using the nightly rustfmt

ryanleh commented 3 years ago

These recent commits move the univariate and multivariate implementations into separate modules and defines a few new interfaces which will be useful for poly-commit and a few other crates.

Polynomial: An interface for all types of polynomials. The domain of the implementing polynomial is an associated type. UVPolynomial: An interface for univariate polynomials. Currently only DensePolynomial implements this. MVPolynomial: An interface for multivariate polynomials. There is an additional interface defined for describing terms in the multivariate polynomial which will allow easily integrating specialized multivariate schemes (e.g. multilinear)

Pratyush commented 3 years ago

This is superseded by PRs on arkworks-rs/algebra