How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric $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?

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?

How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric $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. (The quantity here measures how well $B$ approximates $A$.)

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

How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric $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?