Быстрое умножение циклической матрицы на вектор

[showme777]

svv в сообщении #1391386 писал(а):

Н
Всё, что я говорил об этом, вытекает из общих соображений.

Можете ещё уточнить из каких элементов состоит матрица $A$ Из предыдущего ответа . Просто другого комментатора не очень понял.

[svv]

Матрица $A$ — это Ваша циклическая матрица $C$. Я её обозначил $A$, чтобы подчеркнуть, что то, что о ней говорится, справедливо в общем случае диагонализируемой матрицы.
Матрица $S$, приводящая её к диагональному виду, в общем случае состоит из записанных в столбцы собственных векторов $A$ (каждый столбец — собственный вектор).
Если $A$ циклическая, то эти собственные векторы хорошо известны, зависят только от размера $A$, и составляют матрицу (оператора) ДПФ:
$S_{k\ell}=\exp(\pm i\frac{2\pi}n k\ell)$
Точнее, собственные векторы определены с точностью до множителя и порядка следования, но можно выбрать такую нормировку и порядок, что формула будет вот такой.