Быстрое преобразование Фурье

[user_msk]

Не понял вот что:

$C_n$ - циркулянтная матрица, известно что $C_n = F_n^{*} * L * F_n$
$L$ - диагональная матрица с с.з. матрицы $C_n$, $F_n$ - матрица Фурье.

Получить L можно с помощью быстрого преобразования Ф. первого столбца матрицы $C_n$ за $O(n \log n)$. Это понятно.

А как получить с помощью БПФ за $O(n \log n)$ матрицу $C_{n}^{-1}$ (обратную к $C_n$)?

[DMVN]

А нам не поможет то, что мы можем мгновенно обратить матрицу L, найдя её за $O(n \log n)$ операций ? Может быть, зная $L^{-1}$, уже можно будет и $C_n^{-1}$ изыскать?

[user_msk]

DMVN писал(а):

А нам не поможет то, что мы можем мгновенно обратить матрицу L, найдя её за $O(n \log n)$ операций ? Может быть, зная $L^{-1}$, уже можно будет и $C_n^{-1}$ изыскать?

Да, но как?

Ясно, что $C_n^{-1} = F_n * L^{-1} * F_n^{*}$. Но разве тут $O(n \log n)$ действий?