2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 13:36 


07/10/15

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

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

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

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


23/12/05
11626

(Оффтоп)

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

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

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


07/10/15

2400
photon в сообщении #1396228 писал(а):
Если $\bold S $ разрежена, то, возможно, будет целесообразно пользоваться sparse матрицами

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

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


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

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 15:32 


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

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 15:53 


07/10/15

2400
Pavia в сообщении #1396243 писал(а):
Таки в чём проблема?
$A \cdot S \cdot A = A^2 \cdot S$

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

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


31/10/08
1244
$(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 


07/10/15

2400
Спасибо Pavia!

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:32 


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

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

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:42 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 16:55 


16/04/19
161
$$ \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 
Заслуженный участник


18/01/15
2590
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 


07/10/15

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

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


23/12/05
11626
ой :oops:

 Профиль  
                  
 
 Re: Оптимизация умножения симметричных матриц
Сообщение29.05.2019, 17:06 
Заслуженный участник


18/01/15
2590
Andrey_Kireew в сообщении #1396286 писал(а):
Вот и приехали
Никогда не садитесь в машину к незнакомцу ... :lol:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group