В прошлой части мы рассмотрели общий подход к расчету эффективности алгоритмов с принципом "разделяй и властвуй", а также применение принципа к различным базовым алгоритмам.

Сегодня поговорим о следующем приеме. Как известно, составная часть принципа, это поделить задачу на подзадачи. Мы ни разу не касались, как именно делить. Просто делили на равные части. Но тут вот и есть нюанс, если поделить не абы как, а используя какую-то стратегию, то можно добиться применения принципа там, где это даже не очевидно. И именно эта тема станет предметом данной статьи на примере задачи умножения полиномов. Как и в предыдущих частях, я упрощаю математическую часть, опуская различные нюансы и частные случаи, с целью сохранить научно-популярный характер публикации. При этом я пытаюсь сохранить основные элементы алгоритмов и математических основ. Я хочу подать информацию в кратком доступном виде, в виде математического пересказа, и если у кого-либо возникнет интерес, тот может легко найти полные и строгие математические выкладки по данной теме.

Сигналы

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

Сигнал в общем случае, это некоторый показатель изменяющийся во времени. Это может быть огибающая звука, диаграмма распределения, статистические данные, яркость видеосигнала и др. Для того чтобы обрабатывать сигнал компьютерными алгоритмами сигнал "оцифровывают", т.е. заменяют непрерывный сигнал дискретной величиной, в разные моменты времени.

Также принято следующее компактное представление оцифрованного сигнала, облегчающего математику с сигналом

Данный сигнал оцифрован в набор из дискретных значений. Функция это, так называемая дельта-функция, функция, которая везде равна 0, кроме точки 0, где она равна 1.
Далее компьютерная программа занимается преобразованием данного входного сигнала. И получает в результате некоторый выходной сигнал

Большой интерес в работе с сигналами представляют, так называемые, линейные преобразования. Это такие преобразования исходного сигнала , что обладают следующими свойствами

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

• сохраняют линейное преобразование сигнала. То есть если сигнал , то результат его преобразования будет

Используя второе свойство линейности, можем записать преобразование используя представление сигнала из формулы (1)

Далее используя первое свойство независимости линейного преобразования от сдвига по времени

И получается, чтобы выполнить линейное преобразование любого сигнала,нам нужно лишь посчитать одно преобразование от "дельта-сигнала" , а преобразования любых других сигналов рассчитываются операциями сумм и произведения. Допустим, мы посчитали это одно преобразование и получили в результате сигнал . Давайте этот полученный сигнал, также разложим по формуле (1)

Тогда, продолжим преобразование в формуле (2)

Наивное вычисление по этой формуле всех составляющих сигнала имеет сложность , но метод "Разделяй и властвуй" позволил получить сложность и это было очень существенное изменение. Это было революционное усовершенствование эффективности обработки сигналов. Благодаря этому изменению у нас работает цифровое видео, сотовая связь и другие вещи, без которых не представить жизнь в современности.
Резюме:

1. Любой сигнал для обработки оцифровывается и представляется в виде некоторого набора дискретных значений

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

3. Формула (3) позволяет вычислить результат линейного преобразования сигнала

Модель полиномов

Итак выше мы получили задачу, которую нам надо оптимально вычислять, чтобы обрабатывать сигналы. Сформулируем ее еще раз:
Даны значения , , где . Расширим эти наборы значений до размера , считая , если . Требуется вычислить значений

Эффективное решение данной задачи позволит нам эффективно обрабатывать оцифрованные сигналы, как мы видели в разделе выше.
Как будем решать такую задачу? Более того, как свести эту задачу к методу "Разделяй и властвуй"? Если подойти к решению наивным методом, то мы для каждого будем выполнять операций умножения. И всего у нас штук таких , каждый из которых требует вычисления по формуле (4). В итоге, наивное вычисление дает эффективность вида и надо что-то улучшить, и где то надо "разделить и властвовать", чтобы улучшить эту эффективность.
Формула (4) выглядит довольно простой. Применима она не только для линейного преобразования сигналов. Можно легко вспомнить еще одну простую математическую задачу, для решения которой потребуется выполнить вычисления по формуле (4)
Пусть у нас есть два полинома:

И нам нужно вычислить новый полином, который является произведением этих двух данных полиномов

Легко проверяется, что в общем случае, чтобы вычислить придется воспользоваться формулой

Что в точности соответствует нашей исходной задаче (4)
Таким образом мы свели исходную задачу к задаче нахождения произведения двух полиномов за оптимальное время, и теперь мы будем решать эту задачу.

Альтернативное представление полинома

Любой полином степени однозначно задается его коэффициентами при степени , где . Но есть еще один способ однозначно задать полином. Любой полином степени однозначно задается его значениями в любых различных точках Мы знаем, что прямая линия однозначно задается двумя различными точками, константа задается одной точкой. И это также верно для других степеней полиномов. Но что очень удобно, в применении к нашей задаче, если два перемножаемых полинома будут заданы не коэффициентами, а заданы в этой альтернативной "системе счисления" точками и значениями в одинаковых точках

, то в этой интерпретации легко вычислить результирующий полином. Ведь если мы хотим в той же "системе счисления" получить произведение двух полиномов, то есть найти новый полином со значения в этих точках, то очевидно, что нам достаточно просто перемножить значение одного полинома на значение другого полинома:

Что потребует всего операций умножения
Если мы найдем алгоритм, которым сможем эффективно переводить полиномы, задаваемые коэффициентами ; при степенях в полиномы задаваемыми значениями в точках

, то далее у нас будет задача линейной сложности по вычислению Под конец у нас останется еще одна задача, перевести полином, заданный значениями в точках : обратно в форму коэффициентов при степени , где . Тогда исходная задача (4) будет решена.
Как эффективно вычислить полином

в точках? Допустим, мы за линейное время выберем случайные различные точек и будем наивно вычислять значения полинома в этих точках. Во первых, нам нужно вычислить все степени , от 1 до , что потребует операций умножения. Потом нам еще потребуется операций умножения каждой степени на свой коэффициент и, наконец, сложить слагаемых. Везде только линейные операции, но мы вычислим за линейное время только одну точку. А у нас таких точек и мы опять выходим на сложность , что перечеркивает все наши усилия.
Но, что если точки, в количестве , будут заданы не совсем произвольно? Например, это будет положительно-отрицательных пар

Полином из (5) можно разрезать на две части, с четными степенями и с нечетными степенями .

В этом случае данный полином можно записать как

Где два полинома и имеют степени, как минимум в два раза меньше, чем в нашем исходном полиноме (5)
Но самое главное, что для четно-нечетных пар нам потребуется вычислить значения этих полиномов уже не в точках, а в точках, так как исходные точки - это четно-нечетные пары, а нам нужны лишь их квадраты, которые одинаковы для каждой четно-нечетной пары. После чего за линейное время мы сделаем вычисления значений по формуле (6) для нашего исходного полинома.
Ничего не напоминает? Мы начали вычислять значения полинома степени в точках, но свели эту задачу к вычислению двух полиномов степени , каждого в точках. Это же наш "разделяй и властвуй". Если мы рекурсивно продолжим и дальше делить степени полиномов, то на следующем уровне рекурсии у нас будет четыре полинома степени , которые нам надо будет посчитать в точках.
Рекурсивное соотношение

Согласно мастер-теореме дает результат . Ровно то, что доктор прописал. Гораздо эффективнее исходных , что давал исходный наивный алгоритм.
Но, позвольте, ведь, когда мы спускались на нижний уровень рекурсии, мы возвели в квадрат наши положительно-отрицательные пары и получили вместо положительно-отрицательных пар положительные числа, с которыми уже так просто не спустишься на следующий уровень рекурсии.
Казалось бы да, но на помощь приходят комплексные числа. Допустим у нас есть набор из 4-ёх положительно-отрицательных пар:

После того как мы каждую из этих пар возведем в квадрат, исчезнет плюс/минус, и получится 4 числа.

Заметьте, у нас опять вышли две положительно отрицательные пары:

Если мы возведем их в квадрат, то опять исчезнет плюс/минус, первое число даст +1, второе даст -1 и у нас опять будет одна положительно отрицательная пара.
То есть, для вычисления значения полинома можно выбрать такие точки, которые будут положительно отрицательными парами, и при возведении в квадрат останутся также набором положительно-отрицательных пар, что позволит совершать рекурсии. Тогда значения полинома можно вычислить по формуле (6) для квадратов этих положительно отрицательных пар. Затем, так как эти квадраты все еще остались положительно-отрицательными парами, мы можем повторить рекурсивно разбиение по формуле (6) и выйти на полиномы еще меньшей степени.
В общем случае, чтобы выбрать нужные точки, в которых провести вычисления, в количестве штук нам нужно найти все решения уравнения:

Тогда в качестве точек, образующих положительно-отрицательные пары будет для , пара , Для пара и так далее.
Уравнение в комплексных числах решается довольно просто и имеет следующие корни

Для чётного у нас в этом множестве образуются необходимые положительно-отрицательные пары:

• для 1 это

• для это и т.д.

При возведении этих чисел в квадрат, каждая положительно-отрицательная пара дает число, которое также является одним из корней, то есть также находится в множестве . Количество чисел при возведении в квадрат сокращается в два раза. На предпоследней итерации алгоритма останутся два числа +1 и -1, и наконец одно число 1.
Подведем промежуточный итог:

1. Мы получили алгоритм, который позволяет вычислить значения полиномов степени в точке за время и, используя этот алгоритм, перевели перемножаемые полиномы, задаваемые коэффициентами ; при степенях в полиномы задаваемыми значениями в точках

2. Далее мы за линейное время вычислили произведения этих полиномов

3. Осталась одна задача. Перевести полином, заданный значениями в точке в привычный вид

Интерполяция

Это известная задача - интерполяция полинома степени по точкам.

В точках известны значение полинома

По этим значениям надо вычислить коэффициенты

В общем случае (8) это линейная система уравнений, которую надо решить относительно неизвестных Чтобы увидеть решение этой задачи в общем случае, запишем систему (8) в привычном матричном виде

Надо просто найти матрицу, обратную к квадратной матрице , и в этом случае получим интерполяцию, которая и будет решением нашей задачи

Проблема в том, что в общем случае нахождение обратной матрицы имеет сложность , что нас не устраивает и нам необходимо как-то решить эту задачу более эффективным способом.

На помощь приходит то, что множество точек для интерполяции у нас не произвольное, а жестко задано в (7).

Тогда, с учетом (7) матрица M выглядит следующим образом

Если задать формулу для элемента этой матрицы (нумеруя индексы для упрощения формулы с 0 до ), то это будет

Данная матрица называется оператором дискретного преобразования Фурье и обладает рядом замечательных свойств, применяемые в различных областях. Заметим, что эта матрица является постоянной, совершенно не зависящей от того, какие полиномы мы перемножаем и зависящей только от размерности . Чтобы получить эту матрицу для заданной размерности надо вычислить , после чего заполнить матрицу по схеме выше, где . Вычислительная система может вычислить заранее эту матрицу и держать ее в памяти, чтобы дальше заниматься только умножением полиномов степени и не тратить время на вычисление элементов матрицы. Обозначим матрицу дискретного преобразования Фурье размерности n, как

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

По известной формуле умножения двух матриц

Заметим, что для сопряженного значения справедливо следующее:

Тогда

Действительно, если то под суммой будут единицы. Если , то под сумой будет набор комплексных чисел, которые в своем множестве на комплексной плоскости похожи на спицы колеса, эти комплексные вектора смотрят в разные стороны и "гасят" друг друга.

Интуитивно понятно, но если хотите более математического обоснования, то оно следующее:
Пусть для некоторого ,
Умножим эту сумму на , тогда

Так как , значит такое равенство возможно только, если

Следовательно, матрица которую мы вычислили, это просто единичная матрица умноженная на . Получается, что . А значит, матрица это и будет та самая обратная матрица, которую нам надо найти. Используя (10) мы легко можем выписать, как выглядит эта матрица

То есть (10)
Заметим, что имея вычисленную матрицу нет необходимости вычислять элементы обратной матрицы, достаточно отразить матрицу по вертикали. Действительно, учитывая, что :

Аналогично, можно отразить элементы и по горизонтали. Обозначим эту матрицу как , то есть по смысле это обратная матрица к , или просто отраженная по вертикали, как мы видели выше, что я отразил, переставив буквы DFT в TFD.
Чтобы наивно провести вычисления по формуле (9) потребуется вычисления сложности , коэффициентов , по каждому надо провести операций умножения и сложения. Но не волнуйтесь, немного терпения, мы почти на финише. Осталось еще раз "разделить и повластвовать", чтобы эффективно провести вычисления по формуле (9)
Прием следующий. Давайте в матрице (10) переставим колонки. Сначала будут идти все четные колонки (0,2,4...), потом все нечетные (1,3,5...)
Чтобы результат вычислений по формуле (9) после такой перестановки не изменился, то мы одновременно переставим коэффициенты , сверху будут все те, что были с четными индексами (C(x_0), C(x_2), C(x_4), ...), потом те, что с нечетными индексами (C(x_1), C(x_3), C(x_4), ...). В итоге формула (9) после раскрытия станет выглядеть так:

Разобьем эту матрицу на 4 равных матричных блока , размером каждый

Элементы матрицы
Элементы матрицы
Элементы матрицы
Элементы матрицы

Получается, что вместо наивного вычисления по формуле (9), мы можем провести следующие рекурсивные вычисления:
Для

Для

И мы опять свели задачу вычисления формулы (9) размера к двум подзадачам размерности . Таким образом, мы опять приходим к рекурсивному соотношению:

что по мастер-теореме дает нам результат

Данный алгоритм, который мы рассматривали в этой публикации называется алгоритмом быстрого преобразования Фурье

Заключение

Мы рассмотрели решение вычислительной задачи

Мы разделили ее на следующие этапы, где почти на каждом этапе применяли метод "Разделяй и властвуй"

1. Свели задачу к умножению двух полиномов

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

3. За линейное время нашли произведение полиномов этом альтернативном представлении

4. Привели результирующий полином из альтернативного к традиционному представлению за время