Свертка

Дискретной сверткой функций f(t) и g(t), определенных на множестве целых чисел Z, называется следующая операция:

Круговой дискретной сверткой не-периодической функции f с периодической функцией g называется следующая операция:

Дискретная свертка имеет много различных применений – умножение полиномов, арифметика произвольной точности, обработка сигналов. Круговая свертка не коммутативна – одна из функций является периодическим сигналом, а другая – не-периодическим ответом на сигнал. Операнды обычной свертки тоже часто имеют различный смысл, но сама операция коммутативна – результат свертки не меняется от перестановки функций f и g.

Представление данных

Областью определения функций f и g является всё множество целых чисел, но на практике мы имеем дело с данными ограниченной длины. Удобнее всего, когда функции f и g отличны от ноля только для неотрицательных t. Вычислительные подпрограммы пакета ALGLIB решают именно эту задачу – свертку двух функций, отличных от ноля только при неотрицательных значениях аргумента. Это позволяет воспользоваться простым соответствием между аргументом функции и индексом массива, в котором хранятся её значения: f(t=i) = f_array[i], 0 ≤ i < M и g(t=i) = g_array[i], 0 ≤ i < N (аналогичное соглашение применяется к результату работы подпрограммы).

В случае, если функции f и g отличны от ноля и при положительных, и при отрицательных значениях аргумента, можно воспользоваться тем, что при сдвиге одного из аргументов свертки результат также подвергается сдвигу в том же направлении на ту же величину (при сдвиге двух аргументов – на сумму отдельных смещений). Просто сдвиньте f и g вправо, пока все ненулевые значения не окажутся по одну сторону от ноля, вызовите подпрограмму для свертки, после чего сдвиньте обратно результат.

Реализация свертки в ALGLIB

Здесь мы для простоты будет считать, что N ≥ M, т.е. второй операнд длиннее первого, хотя быстродействие алгоритма не зависит от порядка, в котором передаются операнды. Широко известно, что свертка может быть вычислена с использованием быстрого преобразования Фурье за время O(N·log(N)). Вместе с тем, прямолинейное использование преобразования Фурье не всегда является оптимальным решением – в случае, если один из операндов короче другого, можно значительно ускорить вычисления, использовав другие алгоритмы. В зависимости от длин операндов, пакет ALGLIB может использовать следующие алгоритмы:

Если M невелико – используется алгоритм с трудоемкостью O(M·N)
Если M существенно меньше N, но слишком велико для использования первого алгоритма – используется overlap-add алгоритм, имеющий трудоемкость O(N·log(M)).
Если два предыдущих алгоритма не дают выигрыша в скорости – используется основанный на БПФ алгоритм с трудоемкостью O(N·log(N)) (осуществляется БПФ операндов, покомпонентное произведение частот, обратное БПФ).

Для вычисления свертки используется входящий в состав ALGLIB алгоритм БПФ. Подпрограмма свертки автоматически подбирает длину операндов, по необходимости дополняя их нолями, чтобы достичь оптимального быстродействия (быстродействие БПФ сильно зависит от разложения длины операнда на простые множители). Таким образом, пользователям ALGLIB не надо беспокоиться об оптимальной длине операндов.