¿Cuál es la forma más eficiente de calcular la traza del producto del inverso de una matriz definida positiva simétrica escasa y una matriz simétrica muy escasa?

Answer 1

Voy a suponer que las únicas dos entradas distintas de cero de [math] B [/ math] están fuera de su diagonal. Como [math] B [/ math] es simétrico, estas dos entradas distintas de cero deben ser iguales a [math] \ alpha [/ math], digamos. Supongamos que [math] B [/ math] es una matriz cero, excepto que tiene dos entradas iguales a [math] \ alpha [/ math] en [math] {ij} ^ {th} [/ math] y [math] { ji} ^ {th} [/ math] posiciones. Esto se puede escribir como

[matemáticas] B = \ alpha (e_ie_j ^ T + e_je_i ^ T) [/ matemáticas]

donde [math] e_i [/ ​​math] es la columna [math] i ^ {th} [/ math] de la matriz de identidad del mismo tamaño que [math] B [/ math].

Deje [math] A ^ {- 1} = \ begin {pmatrix} c_1 & c_2 & \ ldots & c_n \ end {pmatrix} [/ math]. Como [math] A [/ math] es simétrico, también lo es [math] A ^ {- 1} [/ math]. Por lo tanto

[matemáticas] A ^ {- 1} B = \ begin {pmatrix} c_1 ^ T \\ c_2 ^ T \\ \ vdots \\ c_n ^ T \ end {pmatrix} (\ alpha (e_ie_j ^ T + e_je_i ^ T) )[/matemáticas]
[matemáticas] = \ alpha (c_ie_j ^ T + c_je_i ^ T) [/ matemáticas]

Ahora

[matemáticas] c_ie_j ^ T = \ begin {pmatrix} 0 & \ cdots & 0 & c_i & 0 & \ cdots & 0 \ end {pmatrix} [/ math]

donde el vector [math] c_i [/ ​​math] está en la columna [math] j ^ {th} [/ math]. De manera similar, [math] c_je_i ^ T [/ math] es la matriz cero con su columna [math] i ^ {th} [/ math] reemplazada por [math] c_j [/ math]. Por lo tanto, [math] A ^ {- 1} B [/ math] es la matriz cero con su columna i ^ {th} reemplazada por [math] \ alpha c_j [/ math] y su [math] j ^ {th} [ / math] columna reemplazada por [math] \ alpha c_i [/ ​​math].

Esto significa que la traza de [math] A ^ {- 1} B [/ math] es [math] \ alpha [/ math] multiplicada por la suma de la entrada [math] i ^ {th} [/ math] de [ math] c_j [/ math] y la entrada [math] j ^ {th} [/ math] de [math] c_i [/ ​​math]. Pero [math] A ^ {- 1} [/ math] es simétrico, por lo que estas dos entradas son iguales. Por lo tanto

[matemáticas] tr (A ^ {- 1} B) = 2 \ alpha c_ {ij} [/ matemáticas]

donde [math] c_ {ij} [/ math] es la entrada [math] {ij} ^ {th} [/ math] de [math] A ^ {- 1} [/ math]. Esto se puede encontrar por la regla de cofactor habitual

[matemáticas] c_ {ij} = (- 1) ^ {i + j) \ frac {\ det A_ {ij}} {\ det A} [/ matemáticas]

donde [math] A_ {ij} [/ math] es una matriz [math] A [/ math] con su fila [math] i ^ {th} [/ math] y [math] j ^ {th} [/ math] columna eliminada Así que finalmente

[matemáticas] tr (A ^ {- 1} B) = 2 (-1) ^ {i + j} \ alpha \ frac {\ det A_ {ij}} {\ det A} [/ matemáticas]

donde [math] \ alpha [/ math] es una de las dos entradas distintas de cero de [math] B [/ math] que se encuentra en la fila [math] i ^ {th} [/ math] y [math] j ^ {th} [/ math] columna de [math] B [/ math]. Esto debería ser mucho más eficiente.

Answer 2

Parece que usar el método de gradiente Conjugate para resolver A \ B es lo que estás buscando. Debe ser muy eficiente en su caso, ya que las únicas acciones son de tipo A * B.