О временной сложности параллельной реализации численного преобразования Фурье

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