3

I am new to FFTs so I am slightly confused on some concepts. So far the FFT examples I've seen for equation multiplication involve equations with consecutive exponents (i.e. A(x) = 1 + 3x + 5x^2 +... and B(x) = 4 + 6x + 9x^2 + ... and C(x) = A(x)*B(x)). However, it is possible to use FFT on two equations that do not have equal exponents? For example, is it possible to use FFT to multiply:

A(x) = 1 + 3x^2 + 9x^8

and 

B(x) = 5x + 6 x^3 + 10x^8

in O(nlogn) time?

If not, are there any cases where the runtime will be O(nlogn)? For example, if the number of terms in the product is O(n) instead of O(n^2)?

Even if the runtime is more than O(nlogn), how can we use FFT to minimize the runtime?

Quanquan Liu
  • 1,427
  • 3
  • 16
  • 30

1 Answers1

1

yes it is possible to use DFFT on non equal exponent polynomials...

the missing exponents are just multiplied by 0 which is also a number... just rewrite your polynomials:

A(x) = 1 + 3x^2 + 9x^8
B(x) = 5x + 6x^3 + 10x^8

to something like this:

A(x) = 1x^0 + 0x^1 + 3x^2 + 0x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 +  9x^8
B(x) = 0x^0 + 5x^1 + 0x^2 + 6x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 + 10x^8

so your vectors for DFFT are:

A = (1,0,3,0,0,0,0,0, 9)
B = (0,5,0,6,0,0,0,0,10)

add zero's so the vector is the correct result size (max A exponent +1 + max B exponent +1) and also round up to closest power of 2 for DFFT usage so original sizes are 9,9 -> 9+9 -> 18 -> round up -> 32

A = (1,0,3,0,0,0,0,0, 9,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
B = (0,5,0,6,0,0,0,0,10,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
//  |    original      | correct result  |    nearest power of 2      |

and do the DFFT stuff you want ... I assume you want to do something like this:

A' = DFFT(A)
B' = DFFT(B)
C(i)' = A'(i) * B'(i)   // i=0..n-1
C= IDFFT(C')

which is O(n*log(n)). Do not forget that if you use DFFT (not DFT) n = 32 and not 18 !!! because n must be power of 2 for fast algorithm of DFT also if you want performance improvements than look at the DFFT weight matrices for DFFT(A),DFFT(B) they are the same so no need to compute them twice ...

Spektre
  • 49,595
  • 11
  • 110
  • 380