Обращение матрицы через LDLT-разложение: итоги

[nabbla1]

Мы описали, как это делается:
раз
два
три.

Теперь подведём итоги по количеству необходимых операций. Поначалу кажется, что это удаление гланд армейским способом - мы выполняем операцию ну очень окольными путями. Что ж, сейчас сравним.

Comments

[iv_an_ru]

> Почему-то человеку кажется, что нахождение обратной матрицы - операция СУЩЕСТВЕННО более сложная [чем перемножение матриц]

При вычислении обратной уж очень делить лень. И если в мозгу застряли воспоминания об институтской алгебре, в которой складывать маленькие целые было намного-намного приятнее, чем делить, то при подсчёте сложности в миллисекундах, а не в попугаях, воображение рисует что-то вроде деления математической библиотекой вместо деления сопроцессором.

[kouzdra]

Большие матрицы кстати умножаются не за N3, а за N2.81 (см. алгоритм Штрассена) - тоже несколько через ж, но быстрее.

[nabbla1]

Честно говоря, не знаю, бывают ли на практике действительно большие "плотные" матрицы. Во всяких анализах цепей, FEM и пр. выползают разреженные матрицы, и под них алгоритмы совсем другие.

Окромя Штрассена, вроде бы и Виноград чего-то придумал, как всегда асимптотически очень круто, но вряд ли применимо на практике.

[kouzdra]

Как я понимаю очень даже бывают - у всяких метеорологов и прочих атомщиков, которым надо системы с туевой хучей переменных считать

[permea_kra]

У метеорологов и атомщиков все эти системы строятся на пространственной сетке, и взаимодействие идет, условно, через границы ячеек. Т.е. это не про этих конкретных.