5
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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 versions 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.

$\endgroup$
2
$\begingroup$

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}) - (\epsilon - \epsilon_0)^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.

$\endgroup$

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.