How to multiply polynomials in Θ(n log n) time
1–10 of 30 posts
Re: How to multiply polynomials in Θ(n log n) time
#2This isn't limited to polynomials. As far as I know, most big integer libraries (like GMP) use FFT multiplication when the integers are big enough.
Re: How to multiply polynomials in Θ(n log n) time
#3This blog post is doing precise integer arithmetic without rounding, and dealing with polynomials of tiny degree. But for more general uses...
Anyone trying to work with polynomials as continuous functions using floating point arithmetic (or trying to work efficiently with piecewise continuous functions in general) should check out Chebfun, http://www.chebfun.org
People should avoid working with polynomials expressed in the monomial basis if possible, unless dealing with a function defined on the complex unit circle. The Chebyshev basis is generally faster and more accurate for polynomials defined on some real interval, and makes it practical to compute with polynomials of very high degree. http://www.chebfun.org/examples/linalg/CondNos.html http://www.chebfun.org/examples/roots/RandomPolynomials.html
For a lot more see: http://www.chebfun.org/ATAP/atap-first6chapters.pdf http://www.chebfun.org/docs/guide/chebfun_guide.pdf
Here’s the guts of their multiplication routine, which multiplies two polynomials and returns a new polynomial which approximates the product to near machine precision: https://github.com/chebfun/chebfun/blob/development/%40chebt... (For the mathematical details see the (paywalled) paper http://epubs.siam.org/doi/abs/10.1137/120865458?journalCode=...). Multiplying values at Chebyshev points (similar to the blog post under discussion) would work too, but Chebfun natively stores an array of coefficients. In fact, they did multiply at values before April of last year, https://github.com/chebfun/chebfun/blob/05611dec557718b5b026...
Re: How to multiply polynomials in Θ(n log n) time
#4This isn't limited to polynomials. As far as I know, most big integer libraries (like GMP) use FFT multiplication when the integers are big enough.
Yes, but integers are a specialization of polynomials. For example, the number 263 can be written as 2x^2 + 6x + 3, where x=10.
(Note that for integers, a post-processing step is necessary to account for coefficients that are larger than the number base, but I guess this is relatively inexpensive).
Re: How to multiply polynomials in Θ(n log n) time
#5This isn't limited to polynomials. As far as I know, most big integer libraries (like GMP) use FFT multiplication when the integers are big enough.
Yes, but integers are a specialization of polynomials. For example, the number 263 can be written as 2x^2 + 6x + 3, where x=10. (Note that for integers, a post-processing step is necessary to account for coefficients that are larger than the number base, but I guess this is relatively inexpensive).
Indeed, having a fast way to multiply in Z[x] gives you a fast way to multiply in Z and vice versa. In the reverse direction, you can encode the polynomial f = 2x^2 + 6x + 3 as 30602, and 30602^2 = 936482404 tells you that f^2 = 4x^4 + 24x^3 + 48x^2 + 36x + 9 (of course, on a computer you do this in binary as opposed to decimal).
This correspondence is often exploited in both directions. If you ask a sufficiently sophisticated computer algebra system (SageMath, for example) to multiply two large polynomials with integer or rational coefficients, chances are that it will reduce the problem to multiplying two large integers, then reduce that problem to multiplying two large polynomials (but different from the ones you started with), and then proceed using recursive polynomial and integer multiplications to compute that product... (i.e. going through a sequence of transformations Z[x] -> Z -> Z[x] -> ...)
Re: How to multiply polynomials in Θ(n log n) time
#6This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem.
In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being an O(n log^2 n) algorithm. Still pretty good; worth knowing about for sure. The constant factor on the precision might be bad enough that you can trigger the problem for reasonable inputs if you're using floats (e.g. a million coefficients, instead of an octillion coefficients).
On the other hand, many algorithms and data structures have hidden logarithmic factors (e.g. hash tables, sorting) that we ignore [1]. YMMV.
1: http://blog.computationalcomplexity.org/2009/05/shaving-logs...
Re: How to multiply polynomials in Θ(n log n) time
#7[deleted]
Re: How to multiply polynomials in Θ(n log n) time
#8[deleted]
This is completely wrong. Big-theta does mean it's an upper bound, and also a lower bound. It certainly does not mean it's the exact number of steps; for example, 5x = Θ(3x), but 5x is more than 3x for all positive x.
Re: How to multiply polynomials in Θ(n log n) time
#9This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being a…
The best complexity these days [1] is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n).
Re: How to multiply polynomials in Θ(n log n) time
#10Fun article, but it was missing a little bit that took me a minute to get. So if you're already familiar with fourier transforms, this might be the missing piece to this article:
Multiplication of polynomials when expressed in the domain of "array of coefficients" is a convolution operation: really you're summing (AB)_k = sum_{i=0}^k A_i B_{k-i} to find the kth coefficient of the result. The indices for B go backwards to those of A and they add up to the fixed quantity k, so we're just looking at a discrete convolution of these two arrays.
And what does Fourier Transform do? It turns convolutions into point-wise multiplication in the 'time' domain. The convolution started as an n^2 operation but the point-wise multiplication is n, so we're left with the FFT time of n log n. So this is another instance of the "formulate problem as a convolution, FFT, perform point-wise multiplication in the time domain, inverse FFT, done" class of algorithms.
(I got stuck a while trying to figure out how polynomial multiplication is convolution. Literally it's point-wise multiplication of two functions, not a convolution, so everything seemed backwards.)