2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Сложность обращения матриц
Сообщение10.05.2014, 13:19 
Заслуженный участник


14/03/10
867
 i  Тема отделена от «Матрица оператора»

Munin в сообщении #861268 писал(а):
операция произведения матриц - сравнительно "лёгкая", а операция взятия обратной матрицы - более "тяжёлая"
на практике - возможно, но в теории это не совсем так - эти задачи имеют одинаковую сложность :-)

 Профиль  
                  
 
 Re: Матрица оператора
Сообщение10.05.2014, 13:53 
Заслуженный участник
Аватара пользователя


06/10/08
6422
patzer2097 в сообщении #861286 писал(а):
на практике - возможно, но в теории это не совсем так - эти задачи имеют одинаковую сложность
:-)
$O(n^{\gamma})$ и $O(n^{\gamma})$ - это не одинаковая сложность :)

 Профиль  
                  
 
 Re: Матрица оператора
Сообщение10.05.2014, 20:45 
Заслуженный участник
Аватара пользователя


30/01/06
72407
К тому же, обычно сначала обратную матрицу считают через определители, и только набравшись мудрости - начинают через Гаусса.

 Профиль  
                  
 
 Re: Матрица оператора
Сообщение11.05.2014, 11:35 
Заслуженный участник


14/03/10
867
Munin в сообщении #861439 писал(а):
К тому же, обычно сначала обратную матрицу считают через определители, и только набравшись мудрости - начинают через Гаусса.
а у нас $3\times3$ матрицы, их еще и проще через определители: 9 сложений и 18 умножений на алгебраические дополнения, и потом еще 3 сложения и 3 умножения на определитель; в то время как стандартное умножение матриц требует 27 умножений и 18 сложений :P

Xaositect в сообщении #861299 писал(а):
$O(n^{\gamma})$ и $O(n^{\gamma})$ - это не одинаковая сложность :)
Не знаю, что такое $\gamma$, и вообще не понял, зачем Вы это написали. Вы считаете, что с этим абзацем что-то не так?

 Профиль  
                  
 
 Re: Матрица оператора
Сообщение11.05.2014, 11:56 
Заслуженный участник


11/05/08
32166
patzer2097 в сообщении #861647 писал(а):
не знаю, что такое $\gamma$ и вообще Вас не понял.

Видимо, имелось в виду, что трудоёмкость -- это не сложность.

patzer2097 в сообщении #861647 писал(а):
проще через определители: 18 сложений и 9 умножений на алгебраические дополнения, и потом еще 3 сложения и 3 умножения на определитель;

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

 Профиль  
                  
 
 Re: Матрица оператора
Сообщение11.05.2014, 12:13 
Заслуженный участник
Аватара пользователя


06/10/08
6422
patzer2097 в сообщении #861647 писал(а):
Не знаю, что такое $\gamma$, и вообще не понял, зачем Вы это написали. Вы считаете, что с этим абзацем что-то не так?
$\gamma$ - это 2.373 из тех таблиц. Текущий рекорд экспоненты матричного умножения.
А насчет примечания - если аккуратно посчитать все константы в Кормене, то получится, что сложность обращения по приведенному алгоритму может быть от 2 до 4 раз больше, чем сложность умножения, в зависимости от экспоненты матричного умножения. Так что формулировка "runs with the same time complexity" неверная, да. В Кормене, естественно, формулировка более аккуратная.
Возможно, конечно, что сложности действительно одинаковые. Но пока мы знаем только то, что они одного порядка, и с небольшой константой.

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 13:11 
Заслуженный участник


14/03/10
867
Xaositect в сообщении #861655 писал(а):
А насчет примечания - если аккуратно посчитать все константы в Кормене, то получится, что сложность обращения по приведенному алгоритму может быть от 2 до 4 раз больше, чем сложность умножения, в зависимости от экспоненты матричного умножения.
Посмотрел книгу :twisted: Для симметрических положительно определенных матриц они дают оценку $$I(n)\leqslant 2 I(n/2)+4 M(n/2)+O(n^2),$$ где $I(n)$ и $M(n)$ --- сложности (соответственно) обращения и произведения $n\times n$ матриц. В частности, если мы умножаем матрицы по алгоритму Штрассена, то обращение будет работать быстрее умножения. Такой же метод работает и для произвольных матриц, смотрите также этот комментарий c формулировкой, которая Вам не понравилась :-)

Xaositect в сообщении #861655 писал(а):
Так что формулировка "runs with the same time complexity" неверная, да. В Кормене, естественно, формулировка более аккуратная.

да, конечно :twisted: :twisted:
Cormen и др., глава 7, введение писал(а):
Chapter 28 studies efficient algorithms for operating on matrices. <...> It also shows that matrix inversion and matrix multiplication can be performed equally fast.




(ewert)

ewert в сообщении #861652 писал(а):
Кроме того, если всё это дело зациклить, то понадобятся ещё и операции на смену знаков, так что получится даже больше.
этого совсем не понял 8-)
ewert в сообщении #861652 писал(а):
А вот четыре на четыре -- уже гораздо хуже.
А я в случае 4x4 и не предлагал считать определители :evil: Для больших матриц все делается иначе, можете посмотреть детали тут

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 14:41 
Заслуженный участник
Аватара пользователя


30/01/06
72407
patzer2097 в сообщении #861647 писал(а):
Вы считаете, что с этим абзацем что-то не так?

С вашим чтением этого абзаца "что-то не так". Почитайте, что такое http://en.wikipedia.org/wiki/Big_O_notation . Например, две функции $x$ и $100500x$ будут иметь одинаковое поведение $\mathcal{O}(x).$

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 15:05 
Заслуженный участник


14/03/10
867
Munin в сообщении #861711 писал(а):
С вашим чтением этого абзаца "что-то не так". Почитайте, что такое http://en.wikipedia.org/wiki/Big_O_notation .
спасибо за ссылку, но я понимаю, что такое О-большое :evil: Вероятно, Вы поняли меня неправильно - я про этот абзац писал

(Оффтоп)

Munin в сообщении #861711 писал(а):
Например, две функции $x$ и $100500x$ будут иметь одинаковое поведение $\mathcal{O}(x).$
видимо, Вы имели в виду $O(x)$, а то Вы что-то непонятное написали

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 17:04 
Заслуженный участник
Аватара пользователя


06/10/08
6422
patzer2097 в сообщении #861670 писал(а):
Посмотрел книгу :twisted: Для симметрических положительно определенных матриц они дают оценку $$I(n)\leqslant 2 I(n/2)+4 M(n/2)+O(n^2),$$ где $I(n)$ и $M(n)$ --- сложности (соответственно) обращения и произведения $n\times n$ матриц. В частности, если мы умножаем матрицы по алгоритму Штрассена, то обращение будет работать быстрее умножения
Да, но и умножать симметричные матрицы можно быстрее. С использованием алгоритма де Гроота для одновременного вычисления $XY$ и $YX$ получается $M_{symm}(n) \leqslant 2M_{symm}(n/2) + 2M(n/2) + 9M(n/4) + O(n^2)$.

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 18:03 
Заслуженный участник


14/03/10
867
Xaositect в сообщении #861801 писал(а):
С использованием алгоритма де Гроота для одновременного вычисления $XY$ и $YX$
пока не видел этого результата, но я, конечно, согласен с Вами и не утверждаю ни что $I(n)<M(n)$, ни чего-либо другого в этом роде :-)
В целом, я в своем первом посте хотел просто отметить, что утвеждение "операция произведения матриц - сравнительно "лёгкая", а операция взятия обратной матрицы - более "тяжёлая", с которого началась эта тема, может не быть верным хотя бы в каком-нибудь разумном смысле

 Профиль  
                  
 
 Re: Сложность обращения матриц
Сообщение11.05.2014, 21:37 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А, ну это, конечно, верно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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