Efficient computation of Cholesky decomposition during tridiagonal matrix inverse I have a symmetric, block tridiagonal matrix $A$. I am interested in computing the Cholesky decomposition of $A^{-1}$ (that is, I want to compute $R$, where $A^{-1}=RR^T$). I know how to compute the blocks of the inverse efficiently using an iterative algorithm. However, is there an efficient algorithm for computing the Cholesky factors $R$ directly (rather than first computing the inverse, and then performing the Cholesky decomposition)?
 A: Let $J$ denote the anti-diagonal identity matrix. Essential properties of $J$ are $$J = J^T = J^{-1}.$$ Moreover, if $T$ is lower triangular, then the matrix $JTJ$ is upper triangular. The matrix $JAJ$ is still block tridiagonal because we have reversed the order of the rows and columns. It is symmetric because $J=J^T$. It is positive definite because $J=J^{-1}$. Now, let $$JAJ = GG^T$$ denote the Cholesky decomposition of $JAJ$. Here $G$ is not only lower triangular, it is lower block bidiagonal. We have $$A = (JGJ)(JG^TJ).$$ It follows that $$A^{-1} = (JG^{-T}J)(JG^{-T}J)^T.$$ Now the matrix $G^{-1}$ is lower triangular and almost certainly dense. It follows that $G^{-T}$ is upper triangular and $JG^{-T}J$ is again lower triangular. In other words, we have produced the standard Cholesky factorization of $A^{-1}$ without first computing $A^{-1}$. 

I suspect that the "new" scheme is faster and more accurate than the original. In the original scheme you first factor $A = LL^T$, compute $L^{-1}$, form $A^{-1} = L^{-T} L^{-1}$ and factor again. In the "new" scheme you first form $JAJ$, factor $JAJ = GG^T$, compute $G^{-1}$ and form $JG^{-T}J$. However, forming $JAJ$ in distributed memory is a non-trivial operation.
A: Here is my matlab code 
     function[L]=MyChol(A)

     [n,m]=size(A);
     L=eye(n);
     for k=1:n-1
           L(k,k)=sqrt(A(k,k));
           L(k+1:n,k)=(A(k+1:n,k))/L(k,k);
           A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-L(k+1:n,k)*L(k+1:n,k)';
     end
     L(n,n)=sqrt(A(n,n));
     end

$A=LL^T$
