Сложность обращения матриц

[patzer2097]

Тема отделена от «Матрица оператора»

Munin в сообщении #861268 писал(а):

операция произведения матриц - сравнительно "лёгкая", а операция взятия обратной матрицы - более "тяжёлая"

на практике - возможно, но в теории это не совсем так - эти задачи имеют одинаковую сложность

[Xaositect]

patzer2097 в сообщении #861286 писал(а):

на практике - возможно, но в теории это не совсем так - эти задачи имеют одинаковую сложность

$O(n^{\gamma})$ и $O(n^{\gamma})$ - это не одинаковая сложность :)

[Munin]

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

[patzer2097]

Munin в сообщении #861439 писал(а):

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

а у нас $3\times3$ матрицы, их еще и проще через определители: 9 сложений и 18 умножений на алгебраические дополнения, и потом еще 3 сложения и 3 умножения на определитель; в то время как стандартное умножение матриц требует 27 умножений и 18 сложений

Xaositect в сообщении #861299 писал(а):

$O(n^{\gamma})$ и $O(n^{\gamma})$ - это не одинаковая сложность :)

Не знаю, что такое $\gamma$, и вообще не понял, зачем Вы это написали. Вы считаете, что с этим абзацем что-то не так?

[ewert]

patzer2097 в сообщении #861647 писал(а):

не знаю, что такое $\gamma$ и вообще Вас не понял.

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

patzer2097 в сообщении #861647 писал(а):

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

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

[Xaositect]

patzer2097 в сообщении #861647 писал(а):

Не знаю, что такое $\gamma$, и вообще не понял, зачем Вы это написали. Вы считаете, что с этим абзацем что-то не так?

$\gamma$ - это 2.373 из тех таблиц. Текущий рекорд экспоненты матричного умножения.
А насчет примечания - если аккуратно посчитать все константы в Кормене, то получится, что сложность обращения по приведенному алгоритму может быть от 2 до 4 раз больше, чем сложность умножения, в зависимости от экспоненты матричного умножения. Так что формулировка "runs with the same time complexity" неверная, да. В Кормене, естественно, формулировка более аккуратная.
Возможно, конечно, что сложности действительно одинаковые. Но пока мы знаем только то, что они одного порядка, и с небольшой константой.

[patzer2097]

Xaositect в сообщении #861655 писал(а):

А насчет примечания - если аккуратно посчитать все константы в Кормене, то получится, что сложность обращения по приведенному алгоритму может быть от 2 до 4 раз больше, чем сложность умножения, в зависимости от экспоненты матричного умножения.

Посмотрел книгу Для симметрических положительно определенных матриц они дают оценку

$$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" неверная, да. В Кормене, естественно, формулировка более аккуратная.

да, конечно

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 писал(а):

Кроме того, если всё это дело зациклить, то понадобятся ещё и операции на смену знаков, так что получится даже больше.

этого совсем не понял

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

А вот четыре на четыре -- уже гораздо хуже.

А я в случае 4x4 и не предлагал считать определители Для больших матриц все делается иначе, можете посмотреть детали тут

[Munin]

patzer2097 в сообщении #861647 писал(а):

Вы считаете, что с этим абзацем что-то не так?

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

[patzer2097]

Munin в сообщении #861711 писал(а):

С вашим чтением этого абзаца "что-то не так". Почитайте, что такое http://en.wikipedia.org/wiki/Big_O_notation .

спасибо за ссылку, но я понимаю, что такое О-большое Вероятно, Вы поняли меня неправильно - я про этот абзац писал

(Оффтоп)

Munin в сообщении #861711 писал(а):

Например, две функции $x$ и $100500x$ будут иметь одинаковое поведение $\mathcal{O}(x).$

видимо, Вы имели в виду $O(x)$, а то Вы что-то непонятное написали

[Xaositect]

patzer2097 в сообщении #861670 писал(а):

Посмотрел книгу Для симметрических положительно определенных матриц они дают оценку

$$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)$.

[patzer2097]

Xaositect в сообщении #861801 писал(а):

С использованием алгоритма де Гроота для одновременного вычисления $XY$ и $YX$

пока не видел этого результата, но я, конечно, согласен с Вами и не утверждаю ни что $I(n)<M(n)$, ни чего-либо другого в этом роде
В целом, я в своем первом посте хотел просто отметить, что утвеждение "операция произведения матриц - сравнительно "лёгкая", а операция взятия обратной матрицы - более "тяжёлая", с которого началась эта тема, может не быть верным хотя бы в каком-нибудь разумном смысле

[Xaositect]

А, ну это, конечно, верно.