cálculo eficiente de Trace (AB^{- 1}) dado A y B

Question

Tengo dos matrices cuadradas A y B. A es simétrica, B es positivo simétrico definido. Me gustaría calcular $ trace (A.B^{- 1}) $. Por ahora, calculo la descomposición de Cholesky de B, resuelva C en la ecuación $ A = C.B $ y sume los elementos diagonales.

¿Hay una forma más eficiente de proceder?

Planeo usar Eigen. ¿Podría proporcionar una implementación si las matrices son dispersas (A a menudo puede ser diagonal, B a menudo es diagonal de banda)?

Answer 1

Si B es escasa, puede ser eficiente (es decir, O (n), suponiendo buen estado número de B) para resolver para x_i en

B x_i = a_i 

(muestra Conjugate Gradient código se da en Wikipedia). Tomando a_i para ser los vectores columna de A, obtienes la matriz B^{-1} A en O (n^2). Luego puede sumar los elementos diagonales para obtener la traza. En general, es más fácil hacer esta multiplicación inversa dispersa que obtener el conjunto completo de valores propios. Para comparar, Cholesky decomposition es O (n^3). (ver el comentario de Darren Engwirda a continuación sobre Cholesky).

Si sólo necesita una aproximación a la huella, en realidad se puede reducir el costo de O (q n) promediando

r^T (A B^{-1}) r 

sobre q vectores aleatorios r. Por lo general, q << n. Esta es una estimación no sesgada a condición de que los componentes del vector aleatorio r satisfacen

< r_i r_j > = \delta_{ij} 

donde <...> indica un promedio sobre la distribución de r. Por ejemplo, los componentes r_i podrían ser independientes gaussianos distribuidos con la unidad de varianza. O podrían seleccionarse uniformemente desde + -1. Normalmente, las escalas de traza como O (n) y el error en la estimación de traza se escalan como O (sqrt (n/q)), por lo que el error relativo se escala como O (sqrt (1/nq)).

Answer 2

Si los valores propios generalizados son más eficientes para calcular, puede calcular los valores propios generalizados, A*v = lambda* B *v y luego sumar todas las lambdas.