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$

2 Answers 2

11
$\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 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.

$\endgroup$
1
  • 1
    $\begingroup$ Let me add that Julia has a very clean factorize interface that selects the best factorization method for each class of matrices and lets you write F = factorize(A); x = F \ b; d = det(F); ld = logdet(F), where the only $\mathcal{O}(n^3)$ operation is the decomposition in factorize. Matlab has a similar decomposition method, but it does not support det (sad trombone). $\endgroup$ Apr 16, 2023 at 8:23
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}) - \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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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