Скажем, у вас есть два полинома: и .
Я пытаюсь понять, как БПФ помогает нам умножить эти два полинома. Однако я не могу найти какие-либо разработанные примеры. Может кто-нибудь показать мне, как алгоритм FFT умножит эти два полинома. (Примечание: в этих многочленах нет ничего особенного, но я хотел, чтобы это было просто, чтобы было легче следовать.)
Я посмотрел на алгоритмы в псевдокоде, но все они, похоже, имеют проблемы (не указывайте, какой должен быть ввод, неопределенные переменные). И, что удивительно, я не могу найти, где кто-нибудь на самом деле прошел (вручную) пример умножения многочленов с использованием БПФ.
Ответы:
Предположим, что мы используем четвертые корни единицы, что соответствует замене1,i,−1,−i на x . Мы также используем прореживание по времени, а не прореживание по частоте в алгоритме FFT. (Мы также без проблем применяем операцию обращения битов.)
Чтобы вычислить преобразование первого полинома, мы начнем с записи коэффициентов:3,1,0,0.
Преобразование Фурье четных коэффициентов 3,0 равно 3,3 , а нечетных коэффициентов 1,0 равно 1,1 . (Это преобразование просто a,b↦a+b,a−b .) Следовательно, преобразование первого полинома равно
4,3+i,2,3−i.
Это получается с использованиемX0,2=E0±O0 ,X1,3=E1∓iO1 . (Из расчета тиддл-фактора).
Давайте сделаем то же самое для второго полинома. Коэффициенты равны2,0,2,0.
Четные коэффициенты 2,2 преобразуются в 4,0 , а нечетные коэффициенты 0,0 преобразуются в 0,0 . Следовательно, преобразование второго полинома равно
4,0,4,0.
Мы получаем преобразование Фурье полинома произведений, умножая два преобразования Фурье поточечно:16,0,8,0.
Осталось вычислить обратное преобразование Фурье. Четные коэффициенты 16,8 обратного преобразования в 12,4 и нечетные коэффициенты 0,0 обратного преобразования в 0,0 . (Обратное преобразование: x,y↦(x+y)/2,(x−y)/2 ) Следовательно, преобразование полинома произведений равно
6,2,6,2.
Это получается с помощьюX0,2=(E0±O0)/2 ,X1,3=(E1∓iO1)/2 . Мы получили желаемый ответ
(3+x)(2+2x2)=6+2x+6x2+2x3.
источник
Определите полиномы, где
deg(A) = q
иdeg(B) = p
.deg(C) = q + p
.В этом случае
deg(C) = 1 + 2 = 3
.Мы легко можем найти C за времяO(n2) путем умножения коэффициентов методом грубой силы. Применяя БПФ (и обратное БПФ), мы могли бы достичь этого за O(nlog(n)) времени. Явное:
Continuing along, we represent each polynomial as a vector whose value are its coefficients. We pad the vector with 0's up to the smallest power of two,n=2k,n≥deg(C) . Thus n=4 . Choosing a power of two provides us a way to recursively apply our divide-and-conquer algorithm.
LetA′,B′ be the value representation of A and B, respectively. Notice that FFT (Fast Fourier Transform) is a linear transformation (linear map) and can be represented as a matrix, M . Thus
We defineM=Mn(ω) where ω is complex roots nth complex roots of unity. Notice jth row and kth column is ωjkn . See more about the DFT matrix here
n = 4
, in this example. Also notice that the entry in theGiven theω4=4th roots of unity, we have the ordered set equality:
This can be visualized as iterating thru roots of the unit circle in the counter-clockwise direction.
Also, notice theω6=ω6modn=ω2=−1 and −i=ω3=ω3+n
mod n
nature, i.e.To complete step 1 (evaluation) we findA′,B′ by performing
This step can be achieved using D&C algorithms (beyond the scope of this answer).
MultiplyA′∗B′ component-wise (step 2)
Finally, the last step is to represent C' into coefficients. Notice
NoticeM−1n=1nMn(ω−1) 1 and ωj=−ωn/2+j .
Also, it is true that, given thenth root of unity, the equality ω−j=ωn−j holds. (Do you see why?)
Then,c⃗ =M−1C′=1nMn(w−1)=14⎡⎣⎢⎢⎢11111−i−1i1−11−11i−1−i⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢16080⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎢(16+8)/4(16−8)/4(16+8)/4(16−8)/4⎤⎦⎥⎥⎥⎥=⎡⎣⎢⎢⎢6262⎤⎦⎥⎥⎥
Thus, we get the polynomialC=A∗B=6+2x+6x2+2x3
1: Inversion Formula pg 73, Algorithms by Dasgupta et. al. (C) 2006
источник