Using Cholesky decomposition to solve a system of equaions $A^TAx=b$

Question

I am looking for a way to use $LL^T$ decomposition of a tridiagonal and symmetric positive definite $n$ by $n$ matrix $A$ to solve $$A^TAx=b.$$ In this case, thanks to $A$ being symmetric, the sysytem is equal to $A^2x=b$. I am not sure how to use the factorization to solve the system though. Does anybody know how to do that?

Answer 1

I'm not sure this is the most efficient, but assuming you don't wan't to just recalculate the new Cholesky decomposition for $A^2$, you can simply use three forward / back substitutions instead of the usual two, noting that $L^2$ is also triangular: $$A^T A x = L^T L^2 L^T x = b$$ $$\text{Forward substitute to get $y$:}\quad L^T y = b,\ y = L^2 L^T x$$ $$\text{Backward substitute to get $z$:}\quad L^2 z = y, \ z = L^T x$$ $$\text{Forward substitute to get $x$:}\quad L^T x = z$$

Addendum: As you may already know, the Cholesky decomposition for a tridiagonal symmetric matrix is composed of bidiagonal matrices.