2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 13:36 
Требуется вычислить матричное произведение:
$$\bold A \cdot \bold S \cdot \bold A,$$
где все матрицы симметричные, а $\bold S$, к тому же, сильно разряженная.

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

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 14:30 
Аватара пользователя

(Оффтоп)

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

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 14:43 
photon в сообщении #1396228 писал(а):
Если $\bold S $ разрежена, то, возможно, будет целесообразно пользоваться sparse матрицами

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 15:20 
Аватара пользователя
Таки в чём проблема?
$A \cdot S \cdot A = A^2 \cdot S$

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 15:32 
Pavia
Разьве любые симметричные матрицы являются коммутирующими?

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 15:53 
Pavia в сообщении #1396243 писал(а):
Таки в чём проблема?
$A \cdot S \cdot A = A^2 \cdot S$

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:17 
Аватара пользователя
$(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)$

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:21 
Спасибо Pavia!

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

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

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

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:55 
$$ \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$
но это такое себе

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:56 
Pavia в сообщении #1396267 писал(а):
Что и требовалось показать

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

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

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

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

-- 29.05.2019, 16:01 --

Andrey_Kireew в сообщении #1396214 писал(а):
а $\bold S$, к тому же, сильно разряженная.
:mrgreen: Это барышня бывает вся из себя разрЯженная да расфуфыренная ... А матрица разрЕженная.

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 17:04 
Вот и приехали. А я уже код поменять успел ...

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 17:05 
Аватара пользователя
ой :oops:

 
 
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 17:06 
Andrey_Kireew в сообщении #1396286 писал(а):
Вот и приехали
Никогда не садитесь в машину к незнакомцу ... :lol:

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group