Быстрая свертка дискретных сигналов, как? Опции

[phantom]

Надо написать алгоритм КИХ фильтрации. Особенность процесса такова, что сигнал выдается фрагментами (начиная от 64 отсчетов).Светрку реализовили через БПФ в нескольких вариантах (overlap&save, overlap&add), но необходимой производительности достичь не удалось (получается в 2-8раз медленнее чем у существующих программ). Причем у программ-аналогов загрузка процессора практически не зависит от длины импульсной характеристики, а у нас - чем больше длина ИХ, тем больше времени требуется на обработку. Думали может БПФ медленное, заменили на Intel FFT которое в 10 раз быстрее общепринятых алгоритмов, но это существенно не помогло. Осталось попаробовать метод блоков переменной длины, но не совсем понятно как это работает. Что можно было бы сделать?

[phantom]

Ой, какие все пафосные, аж страшно...

Ну а вы оптимизацией подобных вычислительных алгоритмов раньше занимались? Опыт имеется?

Странный подход. Если раньше не занимались - то что, и пробовать нельзя?

За вас в конференции никто это не сделает.

Никто и не просил ДЕЛАТЬ что-либо за меня. Хотелось просто услышать мнения по поводу быстрых алгоритмов свертки и особенностей их применения для данной конкретной задачи, особенности которой в следующем:
а) входной сигнал поступает короткими блоками (64...2048)
б) импульсная характеристика имеет очень большую длину по сравнению с длиной блока (100000...500000)
в) обработка идет в реальном времени, т.е. на выход сигнал нужно выдавать блоками такой же длины, что и входные блоки, причем в ответ на каждый входной блок нужно выдать один выходной до того, как придет следующий входной блок (собственно, этот существенный момент не был упомянут ранее, что возможно и вызвало столь странную реакцию отвечающих). И еще один момент: чем короче блоки, тем чаще они поступают на вход и тем меньше времени на обработку.

Хотите теории - Блейхут, "Быстрый алгоритмы цифровой обрабогтки ".

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

Понятно что алгоритмы коротких сверток Винограда им скорее всего не потребуются.

Это вы к чему? Алгоритмы Винограда, как я понимаю, эффективнее для ОЧЕНЬ коротких сверток (пример со сверткой векторов длиной 2 и 3 действительно поучителен), и то еще вопрос, нужно ли стремиться уменьшать количество именно умножений за счет сложений, в то время как бОльшую часть времени занимают операции чтения-записи

есть подозрение, что ребята сами не понимают что делают

прочитав Блейхута они поймут, как использовать FFT для их фильтрации наиболее успешно

...ну и что? Вы что, после каждого приращения буфера на 64 сэмпла делаете новое FFT на 4096(допустим) отсчета?

Нет, делаю одно FFT на 64 отсчета. Алгоритм overlap-discard (то, которое "перекрытие с накоплением" у Блейхута) со сложением в частотной области и обратное FFT на те же 64 отсчета. Поэтому то, что

На 130 000 выигрыш FFT очень ощутим.

меня не сильно волнует.

Вот получили свои 130 000 и сделали один раз FFT...

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