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.
- I need to find the solution of the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$.
- 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.