Полиномы имеют множество операций, проводимых над ними. Например, чтобы их сложить, необходимо время 0(п). А для умножения - 0(п2'). Преимущество быстрого преобразования Фурье в том, что с последней операцией он может справиться за время 0(п logn), позволяя упростить задачи, содержащие действия над многочленами.
Наиболее часто преобразование Фурье применяется в процедуре обработки сигнала. Сам сигнал задается во временной области как функция, отображающая время в амплитуду. «Анализ Фурье позволяет выразить его как взвешенную сумму сдвинутых по фазе синусоид различных частот.» [1, 926-953 c.]. Веса и фазы связаны с частотными характеристиками сигнала в частотной области.
Далее рассмотрим быстрое преобразование Фурье и его применение для умножения многочленов.
Таким образом, написаны программы быстрого преобразования Фурье и обратного БПФ над полем комлексных чисел и кольцом вычетов по модулю, а так же программы для быстрого умножения многочленов над указанными полем и кольцом со сложностью 0(п log и).
Следовательно, данный факт дает толчок развитию в технических приложениях.
