Pembaruan diagonal dari matriks pasti positif simetris

adalahmatriks jarang simetris positif pasti (SPD). adalah matriks diagonal yang jarang. besar (> 10.000) dan jumlah nonzeros dibiasanya 100 ~ 1000. $A$ $n \times n$ $G$ $n$ $n$ $G$

$A$ telah difaktorkan dalam bentuk Cholesky sebagai . $LDL^T$

Bagaimana cara memperbarui dan efisien ketika menjadi ? $L$ $D$ $A$ $A+G$

linear-algebra
sumber

Apakah G hanya memiliki elemen positif? Jika demikian, berikut ini adalah batas atas sepele: lihat pembaruan diagonal sebagai jumlah pembaruan peringkat satu. Ada metode O (n ^ 2) untuk menghitung faktorisasi LDL dari pembaruan peringkat satu (pencarian google memberikan contoh). Maka pembaruan diagonal Anda akan berjalan di O (rn ^ 2) di mana r adalah jumlah elemen diagonal non-nol dari G. Mengingat sifat spesifik dari pembaruan ini ada cara pintas untuk menyimpan beberapa perhitungan, tetapi tidak jelas apakah mungkin untuk kurangi urutan di bawah O (rn ^ 2).

Saya setuju - saya tidak percaya ada cara untuk melakukan pembaruan diagonal ke faktorisasi Cholesky lebih cepat daripada hanya mengulang faktorisasi, tetapi pembaruan peringkat satu dapat dilakukan dalam waktu , dan Anda hanya perlu melakukan satu untuk masing-masing nol pada diagonal dari .

O (m^{2})

$O(m^2)$

G

$G$

Brian Borchers

Untuk dan dalam ratusan, itu akan sulit untuk mengalahkan refactoring . Jika ukuran menjadi jauh lebih besar dan sangat jarang, itu bisa membuahkan hasil. Dalam setiap kasus, pembaruan dan perkiraan yang mungkin dicakup secara mendalam oleh Dapatkah sistem linier simetris diagonal plus tetap diselesaikan dalam waktu kuadrat setelah perhitungan? .

n \sim 10^{4}

$n \sim 10^4$

n n z (G)

$\mathrm{nnz}(G)$

A

$A$

A

$A$

G

$G$

Jed Brown

Jed, saya pikir Anda harus mempromosikan komentar Anda untuk jawaban di sini.

Michael Grant

Jawaban:

Versi terbaru dari paket CHOLMOD SuiteSparse (beta 4.4.5) mendukung pengubahan baris / kolom simetris (pembaruan peringkat2) untuk dekomposisi , menggunakan matlab (dan C) API. Saya menggunakannya dengan sukses di salah satu proyek saya. $LDL^T$

Anda dapat menggunakannya untuk membuat pada faktorisasi. Ini didasarkan pada makalah ini . $nnz(G)$

Oleh karena itu, kompleksitasnya adalah . Di mana dapat dikurangi secara signifikan saat menggunakan permutasi reduksi fill untuk jarang $O(nnz(G)*nnz(L))$ $nnz(L)$ $A$

Paket dapat diunduh dari sini

Berikut adalah beberapa catatan yang diberikan pemilik paket (Prof. Tim Davis):

API:

LD = ldlrowmod (LD, k) menghapus baris / kolom k, dengan menetapkan A (:, k) dan A (k, :) ke baris ke-k / kolom identitas.

LD = ldlrowmod (LD, k, C) menggantikan baris k / k dari A (yang harus merupakan baris k / k dari identitas) dengan kolom C.

Kompleksitas:

Baris tambah / hapus paling banyak memakan waktu $O(nnz(L))$ , jadi jika $nnz(L)$ adalah $O(n)$ , maka waktu paling banyak $O(n)$ .

Isi permutasi yang dikurangi:

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

Yuval Atzmon
sumber