Можно ли упростить матрицу?

[MGM]

Дана матрица:
${a_{ij}} = \prod\limits_{k \in \left| {i - j} \right|} {{\delta _k}} ,{\delta _0} = 1,i = j;$
Можно её упростить, то есть чтобы произведение на вектор было бы операцией не квадратичной сложности. Линейная - в идеале, ну или с логорифмическим множителем.

-- Чт апр 07, 2011 14:17:26 --

То есть понятно, что алгоритм для
${\delta _k} = const,$
Существует, но вот даже не знаю как этот частный случай формализовать

[mihailm]

MGM в сообщении #432078 писал(а):

Дана матрица:
${a_{ij}} = \prod\limits_{k \in \left| {i - j} \right|} {{\delta _k}} ,{\delta _0} = 1,i = j;$
Можно её упростить, то есть чтобы произведение на вектор было бы операцией не квадратичной сложности. Линейная - в идеале, ну или с логорифмическим множителем.
...

(Оффтоп)

Старался, но эту абракадабру расшифровать не смог

[Sasha Rybak]

Как я понял, имеется в виду матрица $||a_{ij}||_{i,j=1}^n$, в которой $a_{ij}=\prod\limits_{k=1}^{|i-j|}\delta_k$ при $i \ne j$ и $a_{ij}=1$ при $i=j$, где $\delta_1,\ ...,\ \delta_{n-1}$ - некоторые числа.
В этом случае (как и в случае любой другой матрицы, в которой $a_{ij}$ зависит только от $i-j$) её произведение на вектор можно вычислить за O(n*log(n)) арифметических операций с помощью быстрого преобразования Фурье. Описывать быстрое преобразование Фурье здесь не буду, так как оно описано на многих других сайтах.

[ewert]

MGM в сообщении #432078 писал(а):

То есть понятно, что алгоритм для
${\delta _k} = const,$
Существует, но вот даже не знаю как этот частный случай формализовать

Это для $a_{ij}=q^{|i-j|}$, что ли? Тогда всё очевидно: для верхней треугольной части $y_n=x_n$, $y_{k-1}=x_{k-1}+qy_k$, и для нижней треугольной аналогично, только в обратную сторону.

Sasha Rybak в сообщении #432099 писал(а):

можно вычислить за O(n*log(n)) арифметических операций с помощью быстрого преобразования Фурье.

Это только для $n=2^m$, а так очень сильно от $n$ зависит, и для простых $n$ БПФ вообще никакого выигрыша не даёт, кроме проигрыша.

[MGM]

ewert в сообщении #432109 писал(а):

Это для $a_{ij}=q^{|i-j|}$, что ли? Тогда всё очевидно: для верхней треугольной части $y_n=x_n$, $y_{k-1}=x_{k-1}+qy_k$, и для нижней треугольной аналогично, только в обратную сторону.

Не понял.:(
В принципе, алгоритм вычисления вектора я знаю, но вот чтобы получить сильно разряженную матрицу...
Как для БПФ, например.
Хотя, возможно это и есть...

ewert в сообщении #432109 писал(а):

Это только для $n=2^m$, а так очень сильно от $n$ зависит, и для простых $n$ БПФ вообще никакого выигрыша не даёт, кроме проигрыша.

Это да. Вякое дополнение матрицы до степени двойки искажает задачу.
За редкими исключениями.

[ewert]

Да что значит искажает: там (в БПФ) объём вычислений порядка $n\cdot(n_1+n_2+\ldots)$, где в скобках складываются те простые сомножители, на которые раскладываеся $n$.

[MGM]

ewert в сообщении #432159 писал(а):

Да что значит искажает: там (в БПФ) объём вычислений порядка $n\cdot(n_1+n_2+\ldots)$, где в скобках складываются те простые сомножители, на которые раскладываеся $n$.

Я имел в виду, что и матрицу и вектор можно в некоторых случаях дополнить элементами до размерности степени двойки. А ответ урезать до первоначальной размерности.
Если при этом результат будет эквивалентным - то игра стоит свеч.
368Х368 всяко меньше, чем 512Х9Х4.

-- Чт апр 07, 2011 19:24:28 --

Sasha Rybak в сообщении #432099 писал(а):

Как я понял, имеется в виду матрица $||a_{ij}||_{i,j=1}^n$, в которой $a_{ij}=\prod\limits_{k=1}^{|i-j|}\delta_k$ при $i \ne j$ и $a_{ij}=1$ при $i=j$, где $\delta_1,\ ...,\ \delta_{n-1}$ - некоторые числа.
В этом случае (как и в случае любой другой матрицы, в которой $a_{ij}$ зависит только от $i-j$) её произведение на вектор можно вычислить за O(n*log(n)) арифметических операций с помощью быстрого преобразования Фурье. Описывать быстрое преобразование Фурье здесь не буду, так как оно описано на многих других сайтах.

А не кинете ссылку на наиболее простое обяснение преобразования таких матриц к псевдодиагональному виду.
Я когда-то БПФ даже программировал, но мне бы теорию - и чтобы попроще.

[MGM]

удалил