LDLT-разложение: особая индийская магия!

[nabbla1]

Мы изложили "стандартный" подход к обращению симметричной положительно определённой матрицы через LDLT-разложение с последующим обращением матриц L и D, и получением итогового результата как результат умножения 3 матриц.

В итоге количество умножений получилось порядка 2/3N3, что конечно получше, чем N3 в алгоритме обращения матрицы "общего вида",

Comments

[lj_frank_bot]

Здравствуйте!
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: Работа.
Если вы считаете, что система ошиблась - напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.

[nabbla1]

Математика, линейная алгебра, вычислительная математика, статьи.

[kouzdra]

Бедный козел Френк

[rdia]

Он охуел и самозабанился, видимо.

[rdia]

Скажите пожалуйста, а в конечном виде весь алгоритм выражается через высокоуровневые функции аля BLAS level 2/3?

То есть правильно ли я понимаю, что это какие-то вложенные циклы, которые делают операции

x_n = \sum a*x_k (0 <= k < n)?

То есть, фактически оно выражается через свёртки в окнах (Slice)?

[nabbla1]

Да, вот этот метод (конкретно получить обратную матрицу A-1 из нижнетреугольной L и диагональной D, лежащих бок о бок) сводится к набору скалярных произведений.

У меня не хватило терпения в пятницу вечером изложить детали реализации, наверное сегодня напишу отдельным постом. В общем, этот метод, увы, требует вспомогательной памяти, на N-1 чисел, грубо говоря - на строку.

И удобнее всего именно по строкам идти: начать с самой нижней, на 1 элемент, затем предпоследнюю на 2 элемента, и так далее. На каждой строке начинаем с того, что запоминаем все элементы в свой временный массив. И затем для каждого элемента делаем скалярное произведение. Один набор коэффициентов - во временном массиве, а второй берётся от текущего положения сначала "вниз", пока не дойдём до диагонали, а потом "вправо" (у нас по диагонали так сказать "зеркало" стоит, которое отражает верхний треугольник вниз).