Згортка - бібліотека алгоритмів

Дискретної сверткой функцій f (t) і g (t). визначених на множині цілих чисел Z. називається наступна операція:

Круговий дискретної сверткой НЕ-періодичної функції f з періодичною функцією g називається наступна операція:

Дискретна згортка має багато різних застосувань - множення поліномів, арифметика довільної точності, обробка сигналів. Кругова згортка НЕ ​​коммутативна - одна з функцій є періодичним сигналом, а інші - не-періодичним відповіддю на сигнал. Операнди звичайної згортки теж часто мають різний зміст, але сама операція коммутативна - результат згортки не змінюється від перестановки функцій f і g.

подання даних

Областю визначення функцій f і g є все безліч цілих чисел, але на практиці ми маємо справу з даними обмеженої довжини. Найзручніше, коли функції f і g відмінні від нуля тільки для невід'ємних t. Обчислювальні підпрограми пакета ALGLIB вирішують саме це завдання - згортку двох функцій, відмінних від нуля тільки при невід'ємних значеннях аргументу. Це дозволяє скористатися простим відповідністю між аргументом функції і індексом масиву, в якому зберігаються її значення: f (t = i) = f_array [i], 0 ≤ i

У разі, якщо функції 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 не треба турбуватися про оптимальну довжину операндів.

Manual entries