Computational method to compute both the (log) determinant and inverse of a matrix

Question

Suppose I have a square matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ and a vector $\mathbf{b}\in\mathbb{R}^n$. In my application I need to accomplish two things.

1. I need to find the solution of the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$.
2. I need to compute the log-determinant of $\mathbf{A}$.

Naively, I could accomplish this by computing an eigen-decomposition of $\mathbf{A} = \mathbf{Q}\Lambda\mathbf{Q}^{-1}$ and use this to obtain both the inverse $\mathbf{A}^{-1}=\mathbf{Q}\Lambda^{-1}\mathbf{Q}^{-1}$ and the log-determinant as $\sum_{i=1}^n \log \Lambda_{ii}$. In this approach I require one $\mathcal{O}(n^3)$ operation to compute the eigen-decomposition and another $\mathcal{O}(n^3)$ operation to obtain the inverse of $\mathbf{Q}$. Is this the best way? Is there a procedure that involves only a single $\mathcal{O}(n^3)$ operation?

The matrix $\mathbf{A}$ does have a certain amount of special structure. It is of the form $\mathbf{A} = \mathrm{Id}_n + \epsilon \mathbf{B}$ where $\mathbf{B}\in\mathbb{R}^{n\times n}$, so $\mathbf{A}$ is not far off from the identity.

Answer 1

The LU decomposition will give you what you want with only $\tfrac{2}{3}n^3 + \mathcal{O}(n^2)$ FLOPs. The linear system is solved by solving two triangular systems. The determinant is the product of the determinants of L and U, which, in turn, are the products of the diagonal elements.

I should also add that we can't really say anything about the performance of two $\mathcal{O}(n^3)$ operations versus one $\mathcal{O}(n^3)$; they're both just $\mathcal{O}(n^3)$. For example, SVD takes roughly $20n^3 + \mathcal{O}(n^2)$ flops. So, two LU decomposition (or even ten) will be much cheaper.

Answer 2

If your matrix $A$ is close to the identity I guess that you could try the following approximation

\begin{align} \log(\det(I + \epsilon B)) &= \log\det(I + \epsilon_0 B) + (\epsilon - \epsilon_0)\operatorname{tr}(B (I + \epsilon_0 B)^{-1}) - \frac{(\epsilon - \epsilon_0)^2}{2} \operatorname{tr}(B (I + \epsilon_0 B)^{-1} B (I + \epsilon_0 B)^{-1}) + O(\epsilon^3) \end{align}

If the expansion is around $\epsilon = 0$, you get

$$\log(\det(I + \epsilon B)) \approx \epsilon \operatorname{tr}(B) \, ,$$

at first order. And

$$\log(\det(I + \epsilon B)) \approx \epsilon \operatorname{tr}(B) - \frac{\epsilon^2}{2} \operatorname{tr}(B^2) \, ,$$

at second order.