Cálculo determinante mientras se resuelve

11

Estoy resolviendo para una enorme matriz definida positiva escasa usando el método de gradiente conjugado (CG). ¿Es posible calcular el determinante de utilizando la información producida durante la resolución? $Ax=b$ $A$ $A$

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

¿Por qué desearía calcular el determinante? Tal resultado seguramente será un desbordamiento o un desbordamiento para una matriz enorme de todos modos. ¡Sería más caritativo si hubiera pedido que calcule el número de condición, pero no pierda su tiempo con el determinante!

Probablemente ya lo sepas, pero los valores de Ritz durante el proceso de gradiente conjugado convergen con los valores propios de la matriz, y de esto puedes derivar estimaciones simples para el determinante.

shuhalo

10

Calcular el determinante de una matriz dispersa suele ser tan costoso como una resolución directa, y soy escéptico de que CG sea de mucha ayuda para calcularlo. Sería posible ejecutar CG para iteraciones (donde es ) para generar información para todo el espectro de , y luego calcular el determinante como el producto de los valores propios, pero esto sería lento y numéricamente inestable $n$ $A$ $n \times n$ $A$

Sería una mejor idea calcular la factorización de Cholesky de dispersión directa de su matriz, digamos , donde es triangular inferior. Entonces donde es simplemente el producto de las entradas diagonales de la matriz triangular inferior ya que los valores propios de una matriz triangular se encuentran a lo largo de su 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$

En el caso de una matriz general no singular, se debe utilizar una descomposición LU pivotada, por ejemplo , donde es una matriz de permutación, de modo que Como es una matriz de permutación, y, por construcción, $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 tendrá una diagonal de todos, lo que implica que

. Por lo tanto, puede calcular

como

y nuevamente reconocer que el determinante de una matriz triangular es simplemente el producto de sus entradas diagonales. Por lo tanto, el costo de calcular el determinante es esencialmente el de una factorización.

det (L) = 1

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

det (A)

$\text{det}(A)$

\pm det (U)

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

Jack Poulson
fuente

A

$A$

10^{6} x 10^{6}

$10^6 x 10^6$

@ManuelSchmidt Las matrices dispersas de ese tamaño resultantes de discretizaciones de tipo de elementos finitos generalmente se pueden factorizar fácilmente con (por ejemplo) métodos multifrontales. Estoy de acuerdo en que la factorización de Cholesky debería usarse si su matriz es HPD (y la generalización de mi argumento anterior es obvia).

Jack Poulson

Gracias por su rápida respuesta y respuesta. Lamentablemente, la matriz no tiene una estructura especial (lo que permitiría una factorización fácil).

Manuel Schmidt

2

Tengo curiosidad por saber por qué necesita calcular el determinante de la matriz. ¿Los valores propios más altos y más bajos no son suficientes?

Jack Poulson

Es parte de una función de distribución de probabilidad compleja y no solo una constante de normalización. Sé que las distribuciones se pueden factorizar (y eso es lo que estamos haciendo en este momento), sin embargo, tenemos toneladas de datos para modelar y cada uno de los factores se vuelve 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
fuente

Resulta que hay algunos algoritmos realmente hermosos y prácticos que implican el cálculo de determinantes considerables. Visite www-m3.ma.tum.de/foswiki/pub/M3/Allgemeines/…

Matt Knepley

2

Sin entrar (nuevamente) en por qué y cómo los determinantes son malos, supongamos que su operador no es fácilmente factorizable o simplemente no está disponible como una matriz y que realmente necesita estimar su determinante.

$A$ $A$

Probablemente pueda realizar ingeniería inversa sobre cómo se obtiene esta estimación del determinante en la implementación estándar de CG siguiendo de cerca la Sección 6.7.3 del libro.

Dominique
fuente

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
fuente

Cálculo determinante mientras se resuelve

Respuestas: