Cálculo do determinante ao resolver

11

Estou resolvendo para uma enorme matriz definida positiva esparsa usando o método do gradiente conjugado (CG). É possível calcular o determinante de usando as informações produzidas durante a resolução? $Ax=b$ $A$ $A$

linear-algebra optimization krylov-method conjugate-gradient Manuel Schmidt
fonte

Por que você deseja calcular o determinante? Esse resultado certamente será um underflow ou um estouro para uma matriz enorme de qualquer maneira. Seria mais caridoso se você pedisse para calcular o número da condição, mas não perca seu tempo com o determinante!

Você provavelmente já sabe disso, mas os valores de Ritz durante o processo de gradiente conjugado convergem para os valores próprios da matriz e é possível derivar estimativas simples para o determinante.

shuhalo

10

Computar o determinante de uma matriz esparsa é tipicamente tão caro quanto uma solução direta, e sou cético quanto ao fato de que o CG seria de grande ajuda para computá-lo. Seria possível executar o CG para iterações (onde é ) para gerar informações para todo o espectro de e depois calcular o determinante como o produto dos autovalores, mas isso seria lento e numericamente instável. $n$ $A$ $n \times n$ $A$

Seria uma idéia melhor calcular a fatoração de Cholesky esparsa direta de sua matriz, digamos , onde é triangular inferior. Então que é simplesmente o produto das entradas diagonais da matriz triangular inferior uma vez que os valores próprios de uma matriz triangular estão ao longo de sua diagonal. $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$

No caso de uma matriz geral não singular, uma decomposição LU pivotada deve ser usada, digamos, , onde é uma matriz de permutação, de modo que Como é uma matriz de permutação, e, por construção, $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$ normalmente terá uma diagonal de todos, o que implica que

. Assim, você pode calcular

como

e novamente reconhecer que o determinante de uma matriz triangular é simplesmente o produto de suas entradas diagonais. Assim, o custo da computação do determinante é essencialmente apenas o de uma fatoração.

det (L) = 1

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

det (A)

$\text{det}(A)$

\pm det (U)

$\pm \text{det}(U)$

Jack Poulson
fonte

A

$A$

10^{6} x 10^{6}

$10^6 x 10^6$

@ManuelSchmidt Matrizes esparsas desse tamanho, resultantes de discretizações do tipo de elementos finitos, geralmente podem ser facilmente fatoradas com (por exemplo) métodos multifrontais. Concordo que a fatoração de Cholesky deve ser usada se sua matriz for HPD (e a generalização do meu argumento acima é óbvia).

Jack Poulson

Obrigado pela sua resposta e resposta rápidas. Infelizmente, a matriz não possui estrutura espezial (o que permitiria uma fatoração fácil).

Manuel Schmidt

2

Estou curioso para saber por que você precisa calcular o determinante da matriz. Os valores próprios mais altos e mais baixos não são suficientes?

precisa

Faz parte de uma função complexa de distribuição de probabilidade e não apenas uma constante de normalização. Eu sei que as distribuições podem ser fatoradas (e é isso que estamos fazendo no momento), no entanto, temos toneladas de dados para modelar e cada um dos fatores se torna enorme.

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
fonte

Acontece que existem alguns algoritmos verdadeiramente bonitos e práticos que envolvem o cálculo de determinantes consideráveis. Verifique www-m3.ma.tum.de/foswiki/pub/M3/Allgemeines/…

Matt Knepley 15/14

2

Sem entrar (novamente) no porquê e como os determinantes são maus, vamos supor que seu operador não seja facilmente fatorável ou simplesmente não esteja disponível como uma matriz e que você realmente precise estimar seu determinante.

$A$ $A$

Provavelmente, você pode fazer engenharia reversa de como essa estimativa do determinante ocorre na implementação padrão do CG, seguindo atentamente a Seção 6.7.3 do livro.

Dominique
fonte

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
fonte

Cálculo do determinante ao resolver

Respostas: