Семинар 6. Быстрое преобразование Фурье (Алгоритмы и структуры данных, часть 1)

• Обучение перемножению многочленов.  

• Рассматриваются два многочлена.  

• Произведение многочленов как сумма произведений коэффициентов.  

• Порядок многочлена n и его связь со степенью.  

• Порядок удобен для программистов, так как определяет длину массива коэффициентов.  

• Коэффициенты многочлена ответа.  

• Абстрагирование от многочленов и рассмотрение векторов коэффициентов.  

• Операция свертки векторов.  

• Цель: выполнить свертку быстрее, чем за n^2.  

• Пример использования свертки: вычисление скалярного произведения векторов.  

• Скалярное произведение как сумма произведений координат.  

• Использование свертки для ускорения вычисления скалярного произведения.  

• Простой алгоритм для перемножения многочленов.  

• Разделение коэффициентов многочленов пополам.  

• Рекурсивное перемножение пар многочленов.  

• Время работы алгоритма: n^2 + линейная добавка.  

• Линейная добавка пренебрежимо мала по сравнению с квадратичной частью.  

• Проблема квадратичного времени остается актуальной.  

• Карацуба предложил способ избежать одного умножения, считая три произведения.  

• Это позволяет вычислить произведение за линейное время.  

• Общее время работы алгоритма зависит от двоичного логарифма степени многочлена.  

• Алгоритм Карацубы является попыткой улучшить квадратичное время.  

• Ранее считалось, что умножение матриц за кубическое время оптимально.  

• Алгоритм Карацубы показывает, что можно перемножать многочлены быстрее, чем за квадратичное время.  

• Можно представить многочлены как набор значений в фиксированных точках.  

• Перемножение значений многочленов работает за линейное время.  

• Для этого нужно научиться переводить многочлены из одного представления в другое.  

• Преобразование многочленов из коэффициентов в значения и обратно линейно и взаимно однозначно.  

• Это преобразование можно рассматривать как преобразование базиса в линейном пространстве.  

• Однако, для практического применения нужен быстрый алгоритм преобразования.  

• Схема Горнера позволяет вычислить значение многочлена за линейное время в одной точке.  

• Однако, для вычисления всех значений многочлена требуется квадратичное время.  

• Это ограничивает возможность использования схемы Горнера для перемножения многочленов.  

• Задача интерполяции заключается в получении коэффициентов многочлена по его значениям в различных точках.  

• Можно использовать интерполяционные полиномы Лагранжа для решения этой задачи.  

• Это позволяет перевести значения многочлена в коэффициенты за линейное время.  

• По значениям многочлена в точках можно восстановить все его коэффициенты.  

• Для каждого многочлена коэффициенты можно вычислить за линейное время.  

• Однако, для многочлена порядка n это требует n^2 операций, что приводит к времени работы n^3.  

• Можно улучшить ситуацию до квадратичного времени.  

• Для этого нужно заранее вычислить многочлен, перемножив все x^i - x^j.  

• Затем делить этот многочлен на x^i - x^j, что занимает линейное время.  

• Интерполяция Ньютона строит серию многочленов, каждый раз увеличивая степень.  

• Процесс включает индукцию и добавление правильных значений.  

• Каждый раз добавляется один правильный многочлен, и степень увеличивается на один.  

• Для улучшения времени работы нужно выбрать специальные точки.  

• Эти точки должны быть комплексными корнями из единицы.  

• Комплексные корни из единицы обозначаются как w^k_n, где k - целое число.  

• Комплексные корни образуют группу относительно операции умножения.  

• Группа абелева и коммутативна, с единицей и обратным корнем.  

• Эти корни образуют группу вычетов по модулю n относительно сложения.  

• Комплексные корни используются как точки для вычисления значений многочлена.  

• Значение многочлена в точке w^k_n вычисляется как сумма коэффициентов, умноженных на w^k_n.  

• Преобразование вектора коэффициентов в вектор значений называется дискретным преобразованием Фурье.  

• Порядок преобразования влияет на корни и результаты.  

• Преобразование линейно и объективно, что делает его подходящим для интерполяции.  

• Обратное преобразование из значений в коэффициенты называется интерполяцией.  

• Обратное преобразование Фурье должно быть обратным к линейному преобразованию.  

• Автор пишет формулу обратного преобразования и проверяет её правильность.  

• Обратное преобразование должно возвращать исходные коэффициенты.  

• Проверка включает подстановку значений из прямого преобразования в обратное.  

• Автор объясняет, что порядок индексов не важен, но влияет на понимание вычислений.  

• Автор меняет порядок сумм и произведений в формуле.  

• Объясняет, что сумма в скобках равна нулю, кроме случая, когда и равно т.  

• Доказывает, что обратное преобразование действительно работает.  

• Прямое и обратное преобразования Фурье имеют одинаковые формулы, но с разными индексами.  

• Единственное отличие — использование сопряженных корней и масштабирующего коэффициента.  

• Автор объясняет, как совместить формулы для прямого и обратного преобразований.  

• Быстрое преобразование Фурье — это алгоритм для дискретного преобразования Фурье.  

• Алгоритм работает за O(n log n) для векторов длины, являющейся степенью двойки.  

• Для векторов другой длины можно использовать более сложные алгоритмы, но это менее эффективно.  

• Рассматриваются коэффициенты полинома.  

• Деление коэффициентов на четные и нечетные.  

• Сравнение с алгоритмом Карацубы.  

• Четные коэффициенты объединяются в многочлен А.  

• Нечетные коэффициенты домножаются на X.  

• Многочлены А и Б имеют порядок в два раза меньше.  

• Запуск быстрого преобразования Фурье для многочленов А и Б.  

• Получение значений для каждого многочлена.  

• Обучение вычислению значений многочлена в комплексных корнях из единицы.  

• Рассмотрение двух случаев: когда n меньше n/2 и когда n больше n/2.  

• Применение формулы для деления коэффициентов.  

• Упрощение выражений и сокращение показателей.  

• Значения для всех k вычисляются из рекурсии.  

• Линейное время для вычисления корней.  

• Рекурсивный алгоритм с временем работы O(n log n).  

• Первый вызов рекурсии для всего многочлена.  

• Рекурсивные вызовы для многочленов размера n/2.  

• Время работы на каждом уровне вложенности линейно от n.  

• Общее время работы O(n log n), где n - длина многочлена.  

• Коэффициенты разбиваются на четные и нечетные.  

• Используется формула через квадрат для решения задачи.  

• Подставляются комплексные корни из единицы.  

• Корни из единицы можно найти в комплексных числах или в полях вычетов.  

• В библиотеке GNU MP используется быстрое преобразование Фурье для длинных произведений.  

• В полях вычетов погрешности отсутствуют, что обеспечивает точность.  

• Рекурсивный вариант преобразования Фурье медленный.  

• Итеративный вариант строится путем выполнения рекурсивного алгоритма.  

• В рекурсии есть спуск вниз и подъем наверх.  

• Преобразование бабочки используется для пересчета значений.  

• Входные значения альфа и бета преобразуются с коэффициентом омега.  

• Преобразование бабочки выполняется на подъеме наверх.  

• Перестановка коэффициентов выполняется путем разворота битов.  

• Четность и нечетность коэффициентов определяют направление перестановки.  

• Перестановка может быть выполнена за линейное время.  

• Перестановка вектора и подъем наверх.  

• Преобразование бабочки используется для получения результатов.  

• Входы и выходы преобразования бабочки находятся в одних и тех же позициях.  

• Массив делится на блоки, и результаты сливаются.  

• Перебираются степени двойки для определения длины блоков.  

• Преобразования бабочки выполняются для каждого блока.  

• Рассматриваются четыре элемента: два в левой половине и два в правой.  

• Перебираются значения от 0 до размера блока минус один.  

• Элементы берутся из массивов и преобразуются с использованием коэффициента.  

• Коэффициент вычисляется с использованием корня комплексной степени.  

• Преобразование бабочки записывает два ответа в те же позиции.  

• Вычисление коэффициента может быть медленным, поэтому его можно предварительно вычислить.  

• Вычисление коэффициента можно ускорить, умножая на заранее вычисленное значение.  

• Это может привести к потере точности, но ускоряет процесс.  

• Альтернативный подход: вычисление коэффициента один раз и использование его для всех блоков.  

• Быстрое преобразование Фурье для векторов a и b.  

• Поэлементное умножение и нахождение комплексных корней.  

• Обратное быстрое преобразование Фурье и деление на степень двойки.  

• Важно выбрать степень двойки, чтобы получить точный многочлен.