4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

Source: https://software.intel.com/content/www/us/en/develop/documentation/mkl-developer-reference-fortran/top/lapack-routines/lapack-linear-equation-routines/lapack-linear-equation-computational-routines.html

$\endgroup$
  • $\begingroup$ Good call. I edited my answer to include the factorization time for inversion. Fundamentally, inverting a triangular matrix is still $O(n^3)$, and you need every coefficient of $L$ and $U$ to compute the trace. However, reducing the run time of your routine by 30 or 50% is definitely worth the effort, even if you can't change the asymptotic behavior! $\endgroup$ – Charlie S Nov 13 '20 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.