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

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

Были разложено в Холецкой формевиде . $A$ $LDL^T$

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

linear-algebra
источник

У G есть только положительные элементы? Если это так, то здесь есть тривиальная верхняя граница: рассмотрите диагональное обновление как сумму обновлений ранга один. Существуют O (n ^ 2) методов для вычисления факторизации LDL ^ t обновления первого ранга (примеры в поиске Google). Тогда ваше обновление по диагонали будет выполняться в O (rn ^ 2), где r - это число ненулевых диагональных элементов G. Учитывая специфику этих обновлений, существуют ярлыки для сохранения некоторых вычислений, но не ясно, возможно ли уменьшите порядок ниже O (rn ^ 2).

Я согласен - я не верю, что есть какой-либо способ сделать диагональные обновления факторизации Холецкого быстрее, чем просто повторение факторизации, но обновления первого ранга можно выполнить за

, и вам нужно сделать только одно для каждого отличен от нуля на диагонали

O (m^{2})

$O(m^2)$

G

$G$

Брайан Борчерз

Для

в сотни, это будет трудно превзойти рефакторинга

. Если размер

станет намного больше, а

очень разреженным, это может окупиться. В любом случае, возможные обновления и аппроксимации подробно рассматриваются в разделе Можно ли решить диагональные плюс фиксированные симметричные линейные системы за квадратичное время после предварительного вычисления? ,

n \sim 10^{4}

$n \sim 10^4$

n n z (G)

$\mathrm{nnz}(G)$

A

$A$

A

$A$

G

$G$

Джед Браун

Джед, я думаю, ты должен рекламировать свой комментарий здесь.

Майкл Грант

Ответы:

Последняя версия пакета CHOLMOD SuiteSparse (бета-версия 4.4.5) поддерживает изменение симметричной строки / столбца (обновление ранга 2) для декомпозиции $LDL^T$ с использованием 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)$

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

$LDL^T$ $LDL^T$ $PAP^T$ $L$

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