Оптимизация умножения симметричных матриц

[Andrey_Kireew]

Требуется вычислить матричное произведение:

$$\bold A \cdot \bold S \cdot \bold A,$$

где все матрицы симметричные, а $\bold S$, к тому же, сильно разряженная.

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

Есть ли для этого средства в matlab?

[photon]

(Оффтоп)

Если есть разряженные, то должны быть и заряженные, а может быть даже наряженные матрицы.

Если $\bold S $ разрежена, то, возможно, будет целесообразно пользоваться sparse матрицами. Вот пример - как минимум, на одном умножении вы время сэкономите. Но, боюсь, если вы каким-то образом хотите учесть симметрию, то придется делать это самостоятельно, а не какими-то встроенными средствами.

[Andrey_Kireew]

photon в сообщении #1396228 писал(а):

Если $\bold S $ разрежена, то, возможно, будет целесообразно пользоваться sparse матрицами

спасибо, но это уже сделано

[Pavia]

Таки в чём проблема?
$A \cdot S \cdot A = A^2 \cdot S$

[feedinglight]

Pavia
Разьве любые симметричные матрицы являются коммутирующими?

[Andrey_Kireew]

Pavia в сообщении #1396243 писал(а):

Таки в чём проблема?
$A \cdot S \cdot A = A^2 \cdot S$

присоединяюсь к вопросу feedinglight, так было бы слишком просто

[Pavia]

$(A \cdot S)=M$
$(S \cdot A)=P $

$m_{ij}=\sum\limits_{k=1}^n a_{ik} \cdot s_{kj}$
$p_{ij}=\sum\limits_{k=1}^n s_{ik} \cdot a_{kj}$

Воспользуемся коммутативностью умножения чисел*. (Для действительных и комплексных чисел это выполняется)
$p_{ij}=\sum\limits_{k=1}^n s_{ik} \cdot a_{kj}$
$p_{ij}=\sum\limits_{k=1}^n a_{kj} \cdot s_{ik}$

Определение симметричных матриц $a_{ij}=a_{ji}$, $s_{ij}=s_{ji}$
$p_{ij}=\sum\limits_{k=1}^n a_{ki} \cdot s_{jk}$
$p_{ij}=\sum\limits_{k=1}^n a_{ik} \cdot s_{kj}$

Тут очевидно что $p_{ij}=m_{ij}$
$m_{ij}=\sum\limits_{k=1}^n a_{ik} \cdot s_{kj}$
$p_{ij}=\sum\limits_{k=1}^n a_{ik} \cdot s_{kj}$

Что и требовалось показать.
$(A \cdot S)=(S \cdot A)$

*Для каких не выполняется? К примеру когда у нас матрица сама состоит из матриц (тензер). Тогда умножение элементов матриц будет не коммутативно.

[Andrey_Kireew]

Спасибо Pavia!

[feedinglight]

При умножении матриц $A \cdot B$ первую хранить в строчном формате, вторую в столбцовом, и хранить в блочном виде. Можно получить ускорение в несколько раз за счёт улучшения локальности. Но на матлабе наверно быстро никогда не будет.
Можно записать в более удобном для реализации виде: $A \cdot S \cdot A = (S \cdot A)^T \cdot A$

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

[photon]

Да нет, вроде бы все правильно. В общем случае перемножение матриц не коммутативно, но для симметричных матриц - все ОК. И, наверное, $\bold A^2$ можно сделать как-то быстрее, но надо думать. Скорее всего, если в Matlab начать ручками крутить индексы и пытаться что-то выгадать, то будет только хуже, но если переписать на C специально под возведение в квадрат симметричной матрицы, то, может быть, получится какой-то прирост производительности .

[feedinglight]

$$ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}= \begin{pmatrix} 0 & 2 \\ 1 & 0 \end{pmatrix} $$

$$ \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix} $$

Если матрица $S$ не меняется, то можно разложить:
$S = LL^T$
$A \cdot S \cdot A = A \cdot L \cdot L^T \cdot A = (A \cdot L) \cdot (A \cdot L)^T$
но это такое себе

[vpb]

Pavia в сообщении #1396267 писал(а):

Что и требовалось показать

Andrey_Kireew в сообщении #1396269 писал(а):

Спасибо Pavia!

photon в сообщении #1396277 писал(а):

В общем случае перемножение матриц не коммутативно, но для симметричных матриц - все ОК

Ужас-ужас-ужас ... Возьмите две случайные (пусть с целочисленными элементами, чтоб считать легче) симметричные матрицы размера 2, и перемножьте руками.

ЗЫ. Пример уже успели привести...

-- 29.05.2019, 16:01 --

Andrey_Kireew в сообщении #1396214 писал(а):

а $\bold S$, к тому же, сильно разряженная.

Это барышня бывает вся из себя разрЯженная да расфуфыренная ... А матрица разрЕженная.

[Andrey_Kireew]

Вот и приехали. А я уже код поменять успел ...

[photon]

ой

[vpb]

Andrey_Kireew в сообщении #1396286 писал(а):

Вот и приехали

Никогда не садитесь в машину к незнакомцу ...