Re: sparse polynomial arithmetic

On Apr 4, 3:36 am, rjf <fate...@xxxxxxxxx> wrote:

FLINT doesn't use either of the strategies you have in mind, for small
polynomials.

If FLINT neither uses machine integer/float arithmetic, nor calls to
libraries, what does it do?

It doesn't multiply individual coefficients at all for polynomials
that small. It currently uses Kronecker segmentation. The "large"
integers that result are multiplied by GMP since that is faster than
implementing the multiplication in C. I call directly to GMP's
routines which are basically implemented in assembly for this. In the
range we are talking about, it uses the classical algorithm to
multiply the "large" integers at the cost of about 4.67 cycles per
limb x limb. There is something like 32 cycles of overhead for the
large integer multiplication.

But of course the polynomials in FLINT are stored in a format which
supports multiprecision coefficients, so any comparison with a format
which only supports up to 64 bit signed coefficients is meaningless.

Nonetheless, the raw time FLINT currently uses is 3 microseconds to
multiply two length ( = degree + 1) 16 polynomials with 29 bit signed
coefficients on a 1.8GHz Opteron machine. That is around 20 cycles per
coefficient by coefficient multiplication on this machine.

I'd actually be surprised if you could do that much more efficiently
in a relatively portable way using machine integer/floating point
arithmetic. You've got memory accesses, loop overhead, coefficient
multiplications, term additions.

If your algorithm is going to be fairly general, it will need to then
multiply polynomials of different lengths and bitsizes, ensure
overflows are not going to occur, in which case it will have to either
implement logic to detect these as it goes and reallocate the output
accordingly or it will have to check the bit size of the coefficients
before starting the computation to ensure that they are not going to
overflow.

The completely general algorithm in FLINT for polynomials with
multiple precision coefficients, which does memory allocation, selects
the correct algorithm to use, etc, takes 5 microseconds for the
problem mentioned above.

On top of this, in a computer algebra system, you are going to have an
enormous amount of logic to convert from whatever the general format
is for storing polynomials, to this format. You will also have
interpreter overhead etc.

I really doubt the optimisation you are talking about makes all that
much difference for general polynomial multiplications in a CAS. It
might make a few percent difference, in which case, go and buy a
faster processor for your machine.

How fast can you do the above computation in LISP, or any of the
packages you mention, assuming uniformly distributed random signed
coefficients, and an algorithm general enough to handle overflows,
should they occur, or select the correct algorithm after computing
that overflows won't occur?

Bill.
.

Relevant Pages

  • Integrating Rational Functions
    ... as a linear combination of a rational function, ... tangents of polynomials of degree 1, ... of which will have real number coefficients. ... has complex roots that show up in complex conjugate ...
    (sci.math)
  • Re: An observation of Weils
    ... Do you know how to use the Euclidean algorithm to compute the ... polynomials in one variable, because we have a division algorithm ... there and keep all the equations and coefficients integral. ... Of course if pand qhave no common factors in the first ...
    (sci.math)
  • Re: Finding the Formula...
    ... algorithm for generating the coefficients. ... how you said it took many many iterations with huge matrices to ... If my "hunch" is right and the polynomials are of degree n, ...
    (sci.math)
  • Re: An observation of Weils
    ... homogeneous polynomials with integer coefficients, ... You need the division algorithm, that is, you need to know ... But any common divisor will, ...
    (sci.math)
  • Re: An observation of Weils
    ... homogeneous polynomials with integer coefficients, ... the greatest common divisor d of two integers p,q ... You need the division algorithm, that is, you need to ...
    (sci.math)