Calcul du déterminant tout en résolvant aide de CG

11

Je résout pour une énorme matrice définie positive clairsemée utilisant la méthode du gradient conjugué (CG). Est-il possible de calculer le déterminant de utilisant les informations produites lors de la résolution? $Ax=b$ $A$ $A$

linear-algebra optimization krylov-method conjugate-gradient Manuel Schmidt
la source

Pourquoi souhaiteriez-vous calculer le déterminant? Un tel résultat sera sûrement un débordement ou un débordement pour une énorme matrice de toute façon. Je serais plus charitable si vous aviez demandé de calculer le nombre de conditions, mais ne perdez pas votre temps sur le déterminant!

Vous le savez probablement déjà, mais les valeurs de Ritz pendant le processus de gradient conjugué convergent vers les valeurs propres de la matrice, et vous pouvez en déduire des estimations simples pour le déterminant.

shuhalo

10

Le calcul du déterminant d'une matrice clairsemée est généralement aussi coûteux qu'une résolution directe, et je suis sceptique que CG serait d'une grande aide pour le calculer. Il serait possible d'exécuter CG pour itérations (où est ) afin de générer des informations pour l'ensemble du spectre de , puis de calculer le déterminant comme le produit des valeurs propres, mais ce serait à la fois lent et numériquement instable. $n$ $A$ $n \times n$ $A$

Ce serait une meilleure idée de calculer la factorisation de Cholesky directe clairsemée de votre matrice, disons , où est triangulaire inférieur. Alors où est simplement le produit des entrées diagonales de la matrice triangulaire inférieure puisque les valeurs propres d'une matrice triangulaire se trouvent le long de sa diagonale. $A = L L^H$ $L$

det (A) = det (L) det (L^{H}) = | det (L) |^{2},

$\text{det}(A) = \text{det}(L) \text{det}(L^H) = |\text{det}(L)|^2,$

det (L)

$\text{det}(L)$

L

$L$

Dans le cas d'une matrice générale non singulière, une décomposition LU pivotante doit être utilisée, disons , où est une matrice de permutation, de sorte que Puisque est une matrice de permutation, , et, par construction, aura généralement une diagonale de tous ceux, ce qui implique que . Vous pouvez donc calculer comme $PA=LU$ $P$

det (A) = det (P^{- 1}) \cdot det (L) \cdot det (U) .

$\text{det}(A) = \text{det}(P^{-1}) \cdot \text{det}(L) \cdot \text{det}(U).$

P

$P$

det (P) = \pm 1

$\text{det}(P)=\pm 1$

L

$L$

det (L) = 1

$\text{det}(L)=1$

det (A)

$\text{det}(A)$

\pm det (U)

$\pm \text{det}(U)$ et reconnaissent à nouveau que le déterminant d'une matrice triangulaire est simplement le produit de ses entrées diagonales. Ainsi, le coût de calcul du déterminant est essentiellement juste celui d'une factorisation.

Jack Poulson
la source

Ce serait l'une des possibilités (bien que j'utiliserais une factorisation cholesky) si la matrice est petite, mais a une taille ~ et donc il n'est pas possible de faire une décomposition

A

$A$

10^{6} x 10^{6}

$10^6 x 10^6$

Manuel Schmidt

@ManuelSchmidt Des matrices éparses de cette taille résultant de discrétisations de type éléments finis peuvent généralement être facilement factorisées avec (par exemple) des méthodes multifrontales. Je suis d'accord que la factorisation de Cholesky devrait être utilisée si votre matrice est HPD (et la généralisation de mon argument ci-dessus est évidente).

Jack Poulson

Merci pour votre réponse rapide. Malheureusement, la matrice n'a pas de structure speziale (ce qui permettrait une factorisation facile).

Manuel Schmidt

2

Je suis curieux de savoir pourquoi vous devez calculer le déterminant de la matrice. Les valeurs propres les plus élevées et les plus basses ne sont-elles pas suffisantes?

Jack Poulson

Elle fait partie d'une fonction de distribution de probabilité complexe et pas seulement une constante de normalisation. Je sais que les distributions peuvent être prises en compte (et c'est ce que nous faisons en ce moment) mais nous avons des tonnes de données à modéliser et chacun des facteurs devient énorme.

Manuel Schmidt

6

$A$ $B$ $\textrm{dim}A \ll \textrm{dim} B$ $\textrm{dim}B=\infty$

$B$ $A$ $B$ $A$ $B$ $\textrm{det}A$ $\textrm{det}B$ $A$ $B$

det A = \prod_{j = 1 \dots dim A} λ_{i} (A) \approx \prod_{j = 1 \dots dim A} λ_{i} (B) \prod_{j = dim A + 1 \dots dim B} λ_{i} (B)

$\textrm{det}A = \prod_{j=1\ldots \textrm{dim}A} \lambda_i(A) \approx \prod_{j=1\ldots \textrm{dim}A} \lambda_i(B) \prod_{j=\textrm{dim}A+1\ldots \textrm{dim}B} \lambda_i(B)$

B

$B$

A

$A$

dim B = \infty

$\textrm{dim}B=\infty$

det A

$\textrm{det}A$

det B

$\textrm{det}B$

Wolfgang Bangerth
la source

Il s'avère qu'il existe des algorithmes vraiment beaux et pratiques qui impliquent le calcul de déterminants de taille. Consultez www-m3.ma.tum.de/foswiki/pub/M3/Allgemeines/…

Matt Knepley

2

Sans (encore) expliquer pourquoi et comment les déterminants sont mauvais, supposons que votre opérateur n'est pas facilement factorisable ou simplement indisponible sous forme de matrice et que vous avez vraiment besoin d'estimer son déterminant.

$A$ $A$

Vous pouvez probablement inverser la façon dont cette estimation du déterminant se produit dans l'implémentation standard de CG en suivant attentivement la section 6.7.3 du livre.

Dominique
la source

2

d e t (A) = \prod_{i = 1}^{n} α_{k}^{- 1},

$det(A) = \prod_{i = 1}^n \alpha_k^{-1},$

α_{k} = \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}}

$\alpha_k = \cfrac{r_k^Tr_k}{p_k^TAp_k}$

r_{k} \neq 0 \forall k = 1, \dots, n

$r_k \ne 0 \;\,\forall k=1, \ldots, n$

R

$R$

r_{k}

$r_k$

P

$P$

p_{k}

$p_k$

p_{k} = - r_{k} + \sum_{i = 1}^{k - 1} γ_{i} r_{i} .

$p_k = -r_k + \sum_{i=1}^{k-1}\gamma_i r_i.$

d e t (P) = (- 1)^{n} d e t (R)

$det(P) = (-1)^n det(R)$

r_{k}

$r_k$

p_{k}

$p_k$

A

$A$

\prod_{k = 1}^{n} α_{k} = \prod_{k = 1}^{n} \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}} = \frac{d e t (R^{T} R)}{d e t (P^{T} A P)} = \frac{d e t (R^{T} R)}{d e t (A) d e t (P^{T} P)} = (d e t (A))^{- 1} .

$\prod_{k = 1}^n \alpha_k = \prod_{k = 1}^n \frac{r_k^T r_k}{p_k^TAp_k} = \frac{det(R^TR)}{det(P^TAP)} = \frac{det(R^TR)}{det(A)det(P^TP)}= (det(A))^{-1}.$

Yermek
la source

Calcul du déterminant tout en résolvant aide de CG

Réponses: