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

[showme777]

Хочу проверить правильно ли я разобрался в алгоритме
Ниже представлена формула умножения циклической матрицы на вектор за $O(n\log n)$ с помощью диагонализации циклической матрицы преобразованием фурье
$Cb=F^{-1} \operatorname{diag}(Fc)Fb$,где $C,F,\operatorname{diag}(Fc),b$ обозначают циклическую матрицу,быстрое преобразование фурье ,диагональную матрицу ,где на главных диагоналях стоят элементы первой строки матрицы $C$ и вектор на который умножается матрица $C$ соответственно.
1)Находим БПФ от $b$.
2)Находим БПФ от $c$.
3)Умножаем матрицы из предыдущих шагов поэлементно между собой.
4) Берем обратное БПФ от вектора из шага 3

Lia: следите за читабельностью оформления, пожалуйста. Исправила, корректность не проверяла.

[arseniiv]

Как я понял, вы спрашиваете, как сделать циклическую свёртку двух кортежей одинаковой длины с помощью ДПФ (а вот классическое быстрое оно или другой алгоритм — совершенно не важно; есть и используются где-то там на практике вполне не медленные алгоритмы, применимые для длин, не являющихся степенями двойки, без дополнения нулями). Тогда да, свёртка $b * c = \mathcal F^{-1}(\mathcal Fb\;\mathcal Fc)$ (хотя в формуле у вас там пропущены важные скобки, но в описании всё как надо). Ну, с точностью до скалярного множителя, зависящего от нормировки в определении $\mathcal F$; в любом случае стоит смотреть, что пишут про них в справке по используемой функции.

[showme777]

arseniiv в сообщении #1391261 писал(а):

Как я понял, вы спрашиваете, как сделать циклическую свёртку двух кортежей одинаковой длины с помощью ДПФ (а вот классическое быстрое оно или другой алгоритм — совершенно не важно; есть и используются где-то там на практике вполне не медленные алгоритмы, применимые для длин, не являющихся степенями двойки, без дополнения нулями). Тогда да, свёртка $b * c = \mathcal F^{-1}(\mathcal Fb\;\mathcal Fc)$ (хотя в формуле у вас там пропущены важные скобки, но в описании всё как надо). Ну, с точностью до скалярного множителя, зависящего от нормировки в определении $\mathcal F$; в любом случае стоит смотреть, что пишут про них в справке по используемой функции.

когда берем ДПФ от $c$ ,нужно взять ДПФ от матрицы получается? я просто до этого только ДПФ от вектора встречал. Не могли бы вы подсказать книгу или методичку какую нибудь где на примере конкретном эта свертка показывается?

[Munin]

У вас же циклическая матрица. Она полностью задаётся своей первой строкой или первым столбцом.

[arseniiv]

showme777
Как раз тут хорошо, что не надо брать от матрицы и даже чтобы она вообще где-то появлялась: в сущности у вас есть два кортежа и всё, а матрица не очень понятно откуда взялась. Через неё можно выразить циклическую свёртку, но можно и без неё.

[showme777]

arseniiv в сообщении #1391322 писал(а):

showme777
Как раз тут хорошо, что не надо брать от матрицы и даже чтобы она вообще где-то появлялась: в сущности у вас есть два кортежа и всё, а матрица не очень понятно откуда взялась. Через неё можно выразить циклическую свёртку, но можно и без неё.

Матрица взялась так как на 2 шаге (первый пост) мы берем бпф от матрицы где на диагоналях стоят элементы из первой строки ,а на остальных местах в этой матрице стоят нули . Разве нет? Это не правильно ?

[svv]

Неправильно. Нет никакого смысла располагать элементы вектора (первой строки либо столбца данной циклической матрицы — зависит от определения преобразования Фурье) на диагонали диагональной матрицы, прежде чем применить к нему преобразование Фурье.

Дискретному преобразованию Фурье нужен вектор, и Вам надо указать, какой именно. Матрица, даже диагональная — не вектор.

В формуле $Cb=F^{-1} \operatorname{diag}(Fc)Fb$ символ $F$ обозначает матрицу, соответствующую ДПФ. Её элементы — экспоненты с мнимым показателем. Эта формула является обоснованием алгоритма быстрого умножения, но она не является его «расчётной формулой» (сравните с формулой arseniiv, где нет никаких $\operatorname{diag}$, а $\mathcal F$ — линейный оператор).

[showme777]

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

Неправильно. Нет никакого смысла располагать элементы вектора (первой строки либо столбца данной циклической матрицы — зависит от определения преобразования Фурье) на диагонали диагональной матрицы, прежде чем применить к нему преобразование Фурье.

Дискретному преобразованию Фурье нужен вектор, и Вам надо указать, какой именно. Матрица, даже диагональная — не вектор.

В формуле $Cb=F^{-1} \operatorname{diag}(Fc)Fb$ символ $F$ обозначает матрицу, соответствующую ДПФ. Её элементы — экспоненты с мнимым показателем. Эта формула является обоснованием алгоритма быстрого умножения, но она не является «расчётной формулой» (см. формулу arseniiv, где нет никаких $\operatorname{diag}$).

Получается мы берём БПФ не от диагональной матрицы ,а просто от вектора где элементы - первая строка циклической матрицы ?

И второй вопрос, я читал,правда на английском ,что где то тут ещё замешаны собственные вектора/значения . Не знаете где ?

[arseniiv]

showme777 в сообщении #1391352 писал(а):

Получается мы берём БПФ не от диагональной матрицы ,а просто от вектора где элементы - первая строка циклической матрицы ?

Ага.

Вообще если вводить в рассмотрение циклические матрицы, то может и можно примешать и их собственные значения и векторы, но вообще то, что преобразование Фурье меняет свёртку и умножение, доказывается и для непрерывного случая, когда привлекать матрицы будет совсем странно, потому что матрица получится с континуумом строк и столбцов. (И для «бесконечного дискретного», когда сворачиваются последовательности, пронумерованные целыми числами.) Потому мне немного странно, что эти матрицы возникли даже здесь.

[svv]

Собственные векторы замешаны вот где. Известно, что если матрицу $A$ можно привести к диагональному виду преобразованием $S^{-1}AS$, то преобразующая матрица $S$ состоит из собственных векторов $A$, записанных в столбик. Матрица $S$, составленная из собственных векторов циклической матрицы $A$ (в правильном порядке и с нужными коэффициентами) — это ровно матрица линейного оператора «дискретное преобразование Фурье».

[showme777]

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

Собственные векторы замешаны вот где. Известно, что если матрицу $A$ можно привести к диагональному виду преобразованием $S^{-1}AS$, то преобразующая матрица $S$ состоит из собственных векторов $A$, записанных в столбик. Матрица $S$, составленная из собственных векторов циклической матрицы $A$ (в правильном порядке и с нужными коэффициентами) — это ровно матрица линейного оператора «дискретное преобразование Фурье».

Что вы имеете в виду под "...состоит из собственных векторов, записанных в столбик". В столбик - то есть на диагоналях, а что тогда стоит на других местах?

[svv]

Пусть матрица $A$ может быть приведена к диагональному виду преобразованием $S^{-1}AS$.
И пусть собственные векторы $A$ известны.
Тогда матрицу $S$ можно получить так.
Берём первый собственный вектор матрицы $A$, записываем его элементы в столбец сверху вниз, это будет первый столбец матрицы $S$.
Берём второй собственный вектор матрицы $A$, записываем его элементы в столбец сверху вниз, это будет второй столбец матрицы $S$.
И так далее.
На всякий случай: матрица $S$, преобразующая к диагональному виду матрицу $A$, сама по себе диагональной не является!

У меня к Вам тоже вопрос. Вы уже дважды говорите о диагоналях (именно во множественном числе), один раз даже о главных диагоналях. Но главная диагональ в матрице одна. Что Вы имеете в виду? Элементы, стоящие на главной диагонали?

[showme777]

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

У меня к Вам тоже вопрос. Вы уже дважды говорите о диагоналях (именно во множественном числе), один раз даже о главных диагоналях. Но главная диагональ в матрице одна. Что Вы имеете в виду? Элементы, стоящие на главной диагонали?

Да,элементы стоящие на главной диагонале.
Выше писал,продублирую.
Не могли бы вы подсказать книгу или методичку какую нибудь где на примере конкретном эта свертка показывается?

[Lia]

showme777
Избегайте избыточного цитирования.
Есть кнопка "Вставка" для цитирования выделенного фрагмента, есть кнопка "Цитата" и del для лишнего.

[svv]

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