Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
Given an LU decomposition of $A\in \mathbb{R}^{n\times n}$, is there a way to compute $\operatorname{trace}(A^{-1})$ with lower complexity than that of the inversion ($O(n^3)$ in practice)?
This question has been asked already on Mathoverflow twice and on Math.SE, but the answers there are not useful.
Base case: Computing the factorization requires $\frac 2 3n^3$ operations and the inverse requires $\frac 4 3n^3$ operations. Computing the trace adds $O(n)$. Let's round that to $2n^3$.
LU case: Computing the factorization requires $\frac 2 3n^3$ operations. If you were to compute $L^{-1}$ and $U^{-1}$, those operations each require $\frac 1 3n^3$ operations. The trace of the matrix product $U^{-1}L^{-1}$ is essentially a dot product of two vectors with length $n^2$, call that $O(n^2)$. Let's round that to $\frac 4 3n^3$.
Asymptotically, you're no better off. But, you can calculate the trace with approximately 33% fewer operations.
