Optimizing for large num of vars with small exponents

[Brent W. Baccala]

Hi -

Just a quick FYI.

I've started work on optimizing FLINT for polynomials with a large number of variables and small exponents, mostly because I've got a problem where it's running out of memory on my computer.

So, when I say "optimize", I'm really interested in its memory footprint.

My first step is to introduce what I call "prime ordering" (is there a better name?) which is the monomial ordering generated by evaluating the monomial at a different small prime for each variable.  So x^2*y^3*z -> 2^2*3^3*5 = 540.  So multiplication is fast; no need to unpack the encoding.

For a polynomial with 100 variables and single digit exponents (say one that requires 3 bits and only a few others that are even non-zero) this means 2 64-bit words for each term (a coefficient and an exponent) instead of 6 under FLINT's current scheme.

So far, I've gotten the four basic operations (+ - * /) working in fmpz_mpoly.  Now I'm on to GCD calculations, and am realizing that FLINT's GCD algorithms recurse on the number of variables in the ring and re-write the polynomials each time, so a 100 variable ring will trigger an extra 100 copies of the polynomials.

Obviously, there's plenty of work to be done...

Just giving the list a heads up about what I'm working on.  I've been active on Sage for a number of years, but this is my first time posting on flint-devel, or working on the internals of FLINT at all, for the matter.

    agape

    brent

[da sh]

So, I am assuming that for this prime ordering each exponent vector is encoded as a integer: fmpz or ulong? It is supposed to be general purpose? or only work in a few cases? The current scheme evaluates x,y,z at powers of two in order to support the common orderings of lex, deglex, and degrevlex.

[Brent W. Baccala]

On Thu, Apr 29, 2021 at 7:41 AM da sh <tths...@gmail.com> wrote:

So, I am assuming that for this prime ordering each exponent vector is encoded as a integer: fmpz or ulong? It is supposed to be general purpose? or only work in a few cases? The current scheme evaluates x,y,z at powers of two in order to support the common orderings of lex, deglex, and degrevlex.

The exponents are encoded as fmpz's, and it's supposed to be general purpose, but of course it can't handle very large exponents.

I've also considered encoding deglex and degrevlex using a combinatorial scheme, like 0 for constants, 1 2 3 for x y z, 4 5 6 7 8 9 for x^2 xy xz y^2 yz z^2, etc, but I decided to try this prime ordering first because it doesn't require unpacking the encoding to do multiplication.

 

    agape

    brent