Skip to main content
3 of 3
added PSD
Jeff
  • 500
  • 4
  • 13

Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?

How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-zero entries in $A$ and $B$ can be the same.

Alternatively, is there a tight upper bound on this quantity that I can compute efficiently, e.g. in $O(n \log(n) )$ time?

Jeff
  • 500
  • 4
  • 13