Cholesky decomposition of the inverse of a matrix I have the Cholesky decomposition of a matrix $M$. However, I need the Cholesky decomposition of the inverse of the matrix, $M^{-1}$. Is there a fast way to do this, without first computing $M^{-1}$? In other words, is there a relationship between the Cholesky decompositions of a matrix and of its inverse?
My matrix is a covariance matrix and, hence, positive-definite.
 A: If $L^T L = R$ is the available Cholesky decomposition, then inverting both sides of the equation you get,
$$L^{-1}(L^{T})^{-1} = R^{-1} $$
And since transposition and inverse are interchangeable:
$$L^{-1}(L^{-1})^{T} = R^{-1} $$
So if you define $P = (L^{-1})^T$ this is your desired answer. In other words,
$$P^{T}P=R^{-1}$$
A: I do not believe there is any way to do it without some $O(n^3)$ operation. Different choices can have different constants. In particular, assuming $M=LL^T$ and you already have the Cholesky factor $L$, computing $L^{-1}$ costs ~$n^3/3$ flops, and given that, you can form $M^{-1}$ = $L^{-T}L^{-1}$ in ~$n^3/3$ flops and take its Cholesky in another ~$n^3/3$ flops, which is ~$n^3/3$ flops cheaper than pretending you don't have $L$, forming $M^{-1}$ directly and taking its Cholesky. But it's still $O(n^3)$.
A: To add to previous answers, if we view $X$ as covariance matrix of data, the relationship between two decompositions reduces to relationship between coefficients of "right-to-left" autoregressive model and "left-to-right" one (details)
In general, switching order of "inverse" and "Cholesky" gives different results. IE
$$
\text{X=}\left(
\begin{array}{ccc}
 10 & 0 & 4 \\
 0 & 10 & -2 \\
 4 & -2 & 15 \\
\end{array}
\right)
$$
Using Cholesky and inverting factors, gives this decomposition
$$X^{-1}=
\left(
\begin{array}{ccc}
 1 & 0 & -\frac{2}{5} \\
 0 & 1 & \frac{1}{5} \\
 0 & 0 & 1 \\
\end{array}
\right)\left(
\begin{array}{ccc}
 \frac{1}{10} & 0 & 0 \\
 0 & \frac{1}{10} & 0 \\
 0 & 0 & \frac{1}{13} \\
\end{array}
\right)\left(
\begin{array}{ccc}
 1 & 0 & 0 \\
 0 & 1 & 0 \\
 -\frac{2}{5} & \frac{1}{5} & 1 \\
\end{array}
\right)
$$
While Cholesky on the inverse directly gives
$$X^{-1}=
\left(
\begin{array}{ccc}
 1 & 0 & 0 \\
 -\frac{4}{73} & 1 & 0 \\
 -\frac{20}{73} & \frac{2}{15} & 1 \\
\end{array}
\right),\left(
\begin{array}{ccc}
 \frac{73}{650} & 0 & 0 \\
 0 & \frac{15}{146} & 0 \\
 0 & 0 & \frac{1}{15} \\
\end{array}
\right),\left(
\begin{array}{ccc}
 1 & -\frac{4}{73} & -\frac{20}{73} \\
 0 & 1 & \frac{2}{15} \\
 0 & 0 & 1 \\
\end{array}
\right)
$$
notebook
