Диагональное обновление симметричной положительно определенной матрицы

19

- это n × n- симметричная разреженная матрица с положительным определением (SPD). G - разреженная диагональная матрица. n большое ( n > 10000) и число ненулевых в G обычно составляет 100 ~ 1000.An×nGnnG

Были разложено в Холецкой формевиде L D L T .ALDLT

Как эффективно обновить и D, когда A становится A + G ?LDAA+G


источник
У G есть только положительные элементы? Если это так, то здесь есть тривиальная верхняя граница: рассмотрите диагональное обновление как сумму обновлений ранга один. Существуют O (n ^ 2) методов для вычисления факторизации LDL ^ t обновления первого ранга (примеры в поиске Google). Тогда ваше обновление по диагонали будет выполняться в O (rn ^ 2), где r - это число ненулевых диагональных элементов G. Учитывая специфику этих обновлений, существуют ярлыки для сохранения некоторых вычислений, но не ясно, возможно ли уменьшите порядок ниже O (rn ^ 2).
3
Я согласен - я не верю, что есть какой-либо способ сделать диагональные обновления факторизации Холецкого быстрее, чем просто повторение факторизации, но обновления первого ранга можно выполнить за , и вам нужно сделать только одно для каждого отличен от нуля на диагонали G . O(m2)G
Брайан Борчерз
10
Для и п п г ( G ) в сотни, это будет трудно превзойти рефакторинга А . Если размер A станет намного больше, а G очень разреженным, это может окупиться. В любом случае, возможные обновления и аппроксимации подробно рассматриваются в разделе Можно ли решить диагональные плюс фиксированные симметричные линейные системы за квадратичное время после предварительного вычисления? , n104nnz(G)AAG
Джед Браун
5
Джед, я думаю, ты должен рекламировать свой комментарий здесь.
Майкл Грант

Ответы:

3

Последняя версия пакета CHOLMOD SuiteSparse (бета-версия 4.4.5) поддерживает изменение симметричной строки / столбца (обновление ранга 2) для декомпозиции LDLT с использованием API-интерфейса matlab (и C). Я успешно использовал его в одном из моих проектов.

Вы можете использовать его для обновления nnz(G) факторизации. Он основан на этой статье.

Следовательно, сложность будет O(nnz(G)nnz(L)) . Где nnz(L) может быть значительно уменьшено при использовании перестановки уменьшения заполнения для разреженного A

Пакет можно скачать здесь

Ниже приведены некоторые примечания, сделанные владельцем пакета (проф. Тим Дэвис):

API:

LD = ldlrowmod (LD, k) удаляет строку / столбец k, устанавливая A (:, k) и A (k, :) в k-ую строку / столбец идентичности.

LD = ldlrowmod (LD, k, C) заменяет k-ю строку / столбец A (которая должна быть k-й строкой / столбцом идентификатора) на разреженный столбец C.

Сложность:

O(nnz(L))nnz(L)O(n)O(n)

Заполнить редукционную перестановку:

LDLTLDLTPAPTL

Юваль Ацмон
источник