Scomposizione di Cholesky di matrici sparse mediante matrici di permutazione

Question

Sono interessato alla scomposizione di Cholesky di matrici sparse di grandi dimensioni. Il problema che sto avendo è che i fattori Cholesky non sono necessariamente sparsi (proprio come il prodotto di due matrici sparse non è necessariamente scarso).

Ad esempio per una matrice con zero non solo lungo la prima riga, prima colonna e diagonale, i fattori Cholesky hanno il 100% di fill-in (i triangoli inferiore e superiore sono 100% densi). Nel image sotto il grigio non è zero e il bianco è zero.

Una soluzione Sono consapevole è quello di trovare una permutazione P matrice e fare la decomposizione di Cholesky di P ^T AP. Ad esempio con la stessa matrice applicando una matrice di permutazione che sposta la prima riga all'ultima riga e la prima colonna all'ultima colonna i fattori di Cholesky sono sparsi.

La mia domanda è come determinare P in generale?

Per avere un'idea della differenza della decomposizione di Cholesky di A e P ^T AP da una matrice più realistica vedi immagine sotto. Ho preso tutte queste immagini dal http://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdf

Secondo i lecture notes

molti metodi euristici (che non riguardiamo) esistere per la selezione di buona permutazione matrici P.

Mi piacerebbe sapere quali sono alcuni di questi metodi (il codice in C, C++, o anche Java sarebbe l'ideale).

Answer 1

Il problema di trovare una permutazione ottimale di righe e colonne di una matrice per una fattorizzazione minima della matrice di riempimento non è un cestino trascurabile (come indicato nei commenti). Pertanto, gli algoritmi euristici sono utilizzati nella prassi.

Esistono alcune librerie che implementano strategie di rinumerazione/ordinamento euristico, spesso basate su algoritmi grafici per il grafico di adiacenza della matrice. Si tenta di ridurre la larghezza di banda della corrispondente matrice di adiacenza. Un algoritmo facile da implementare è l'algoritmo Cuthill-McKee Algorithm o Minimum-Degree Ordering. Maggiori informazioni su questo problema sono disponibili nel Libro Yousef Saad: Iterative Methods for Sparse Linear Systems (2003), su molti altri.

Molte librerie implementano algoritmi euristici, come

• Suitesparse Una collezione di librerie per solutori diretti per sistemi lineari sparsi largse.metodi di ordinazione implementati nelle librerie AMD, CAMD, COLAMD, e CCOLAMD
• (Par-)Metis Una biblioteca per Graph-partizionamento, ma fornisce Matrix riordino algoritmi così
• Boost.Graph Lavorando sul grafico di adiacenza direttamente e fornisce alcuni algoritmi di ordinamento, come il citato Cuthill-McKee, e minimo-Degree ordinazione
• (PT-)Scotch per Graph-partizionamento e radi-matrice riordino

Alcune di queste librerie forniscono anche metodi sparse fattorizzazione di Cholesky e può essere utilizzato direttamente.