Re: multiplication ofpolynomials using FFT


Jeremy Watts wrote:
"Chip Eastham" <hardmath@xxxxxxxxx> wrote in message
news:1164082034.143089.238410@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Jeremy Watts wrote:
at what sort of degree of polynomials is it worthwhile using the FFT
method
to multiply them over the 'classical' method?

A rough answer can be given in terms of the comparative
count of operations.

The coefficients in the product of two polynomials are a
convolution of the two (finite) sequences of coefficients
in the multiplicands.

The 'classical' method forms this convolution by doing
all the pairwise products and summing according to
the like degrees. The operation count is therefore a
close reflection (for large degrees anyway) of the product
of the two degrees.

At its heart the FFT method replaces the convolution
calculation by evaluations of the two polynomials at
some common set of nodes, multiplication of these
evaluations at those nodes, and interpolation of the
resulting products to obtain the polynomial that is
the desired product of input polynomials.

What makes an FFT method "fast" is that at some
special choice of nodes, the evaluations and the
interpolation can be done with astonishing economy.
While Horner's method for evaluation at a single
point requires multiplication count equal to the
degree, and a number of nodes for interpolation
equal to the number of coefficients in the product
polynomial, an FFT method relies on sharing some
common intermediate results to the effect that the
number of multiplications behaves like O(N log N)
rather than O(N^2), which would be a reasonable
basis for comparison if the input polynomials have
roughly the same (large) degrees.

There is another "penalty" to the usual FFT
method, and that is the arithmetic is being done
over the complex numbers even if the coefficients
of the input polynomials are all real.

So let's assume a factor of two for the real vs.
complex issue, and a factor of three for doing
both evaluations and the one interpolation, ie.
two FFT's and one inverse FFT, which are at
most slight variations on the same method,
and throw in another factor of two because
roughly 2N nodes are needed to determine
the coefficients of the product of two degree
N polynomials.

Then we ask, when does 12 N log N become
comparable to N^2 ? It's not an exact basis
for comparison, but a reasonable exercise
to get a feel for things. The log here, in the
usual "powers of two" FFT is a log base 2.
So it amounts to asking when is:

N/(log_2 N) = 12

And the answer is: someplace between
N = 2^6 = 64 and N = 2^7 = 128, if we are
sticking to the powers of 2. Okay, the
number of coefficients is one more than
the degree, so I'm being a little sloppy,
but you get a rough idea. There aren't a
lot of natural applications for polynomials
of degree this high, but more often an
interest in extended precision arithmetic
involving this many digits. If you treat
the extended precision integer as a
high degree polynomial being evaluated
at the arithmetic base/radix, then you
see why after a certain point FFT gets
to be an attractive option for multiplying
big numbers.

regards, chip

thank you for that astonishingly detailed answer... :)


You're quite welcome, but take it with a grain
of salt! We can be sure FFT is not beneficial
for multiplying two polynomials of degree 10,
and we should be motivated to consider FFT if
we had routinely occasion to multiply pairs of
polynomials of degree 1000 or more. Some
in-between case, degree ~100 (give or take),
approaches a break even point, but details of
the problem (what kind of coefficients) and
the implementation (hardware & software) will
have an effect on locating that point.

--c

.

Relevant Pages

  • Re: multiplication ofpolynomials using FFT
    ... convolution of the two sequences of coefficients ... At its heart the FFT method replaces the convolution ... calculation by evaluations of the two polynomials at ...
    (sci.math.symbolic)
  • Re: multiplication ofpolynomials using FFT
    ... convolution of the two sequences of coefficients ... At its heart the FFT method replaces the convolution ... calculation by evaluations of the two polynomials at ...
    (sci.math.symbolic)
  • 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: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)