Fast trace of inverse of a square matrix - MathOverflow

Fast trace of inverse of a square matrix

2010-11-18T22:52:57Z

Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix?

In my particular problem I also have a LU decomposition of H already available, which was used in a previous context to solve a system of linear equations. My current approach is to simply use the LU to compute the inverse and then calculate the trace. Is there any other more efficient way to achieve this, considering I already have this matrix factorized?

I could have first computed the inverse and then made a multiplication by the inverse to solve my previous system of linear equations, but I was trying to avoid multiplication by the inverse to avoid numerical inaccuracies.

Edit: Forgot to mention that under normal conditions H should be symmetric.

Answer by Agol for Fast trace of inverse of a square matrix

2010-11-19T02:04:22Z

If you have an $n\times n$ matrix $A$ with eigenvalues $\lambda_1,\ldots, \lambda_n$, then the characteristic polynomial of $A$ is $det(\lambda I-A)=\prod_{i=1}^n (\lambda-\lambda_i) = \sum_{i=0}^n a_i \lambda^i$. Then $det(A^{-1})=- a_1/a_0$, since the coefficient $a_{n-i}$ is the sum of all products of $i$ eigenvalues, so $a_1/a_0 = \sum_{i=1}^n \lambda_i^{-1}= trace(A^{-1})$. I'm not sure if it helps to compute the characteristic polynomial if you have an LU decomposition though.

Answer by J. M. for Fast trace of inverse of a square matrix

2010-11-19T12:35:07Z

Given that the poster has specified that his matrix is symmetric, I offer a general solution and a special case:

Eigendecomposition actually becomes more attractive here: the bulk of the work is in reducing the symmetric matrix to tridiagonal form, and finding the eigenvalues of a tridiagonal matrix is an O(n) process. Assuming that the symmetric matrix is nonsingular, summing the reciprocals of the eigenvalues nets you the trace of the inverse.
If the matrix is positive definite as well, first perform a Cholesky decomposition. Then there are methods for generating the diagonal elements of the inverse.