Почти Фурье на неравномерной сетке

[ilghiz]

Добрый день.

Пусть у меня есть несколько $W_n, n=1,\dots,N, ~ N \simeq 128, ~ W_n \in [1,50]$. Сами значения $W_n$ распределены хаотично по этому интервалу, и это данность ни от чего не зависит и ни от чего не меняется.

У меня имеется последовательность $f_{mk}, ~ m=1,\dots,M, ~ k=0,\dots,K-1, ~ M=2/4/8, ~ K \simeq 200-1000$,

мне надо быстро считать

$\displaystyle s_{nm} = \sum_{k=0}^{K-1} e^{2 \pi \alpha W_n k} f_{nk}$, вернее $r_{nm} = |s_{nm}|$ и $g_{nm} = \arctg(Re(s_{nm}),Im(s_{nm}))$,

так, что $\alpha \simeq 1$, но может слегка отличаться от единицы примерно на доли процента.


То есть я вылизываю по точности и скорости модуль, в который попадает последовательность $f_{mk}$ и задана 16-ти битными целыми, $\alpha$ бывает, что не меняется с предыдущего вызова, (скажем так, примерно каждый второй раз меняется), а на выходе этого модуля мне надо получать $r_{nm}$ и $g_{nm}$.


Хочется решать эту задачу с минимальным числом арифметических операций.


Пока реализовал так, считаю синусы и косинусы кордиком с точностью 18 бит по двум таблицам на 512 значений каждая, так, что на вычисление каждой пары синусов тратится 4 умножения (то есть всего надо примерно $8NK$ операций), но далее, результаты все равно приходится умножать матрично, что требует еще $2MNK$ операций, то есть суммарно, $2NK(4+M)$, это я еще перевод комплексного в тригонометрическую форму не учел.

У меня банально флопов не хватает, при $N=128, K=1000, M=4,$ мне надобно $2 \times 10^6$ арифметических операций, а у меня есть в наличии только примерно $10^5$.

Скажите, пожалуйста, есть ли какой-то способ использовать тот факт, что $W_n$ заданы и не меняются, чтоб как-то уменьшить вычислительную сложность этой задачи?

Или хотя бы для случая, когда $\alpha$ не меняется?

PS: Ранг матрицы такого неравномерного Фурье полный, то есть малоранговость не попользуешь.


Спасибо!

[ilghiz]

OFF: скажите, пожалуйста, а на каком форуме какого ресурса разумнее обсуждать похожие как я изложил вопросы, как я понимаю, здесь вычислительная математика за рамками обычного университетского курса как-то не сильно обсуждается? Спасибо!

[Pphantom]

Да нет, просто задача нетривиальна, и шансы на то, что кто-то другой случайно знает готовый ответ или может его быстро придумать, невелики.

[Munin]

Можно попытать счастья на StackExchange сообществах.

[ilghiz]

Pphantom в сообщении #1394734 писал(а):

Да нет, просто задача нетривиальна, и шансы на то, что кто-то другой случайно знает готовый ответ или может его быстро придумать, невелики.

Спасибо большое за ответ!

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

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

Про stackexchange - не знал, посмотрю. Честно говоря, форум возможно быстрее позволяет обмениваться мнениями, чем единичные топики.

[Pphantom]

(Оффтоп)

ilghiz в сообщении #1394787 писал(а):

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

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