2
$\begingroup$

Suppose that $A$ is a symmetric and positive definite tridiagonal matrix.

Question: how do I give an algorithm to compute the $LDL^T$ decomposition of $A$, where $l_{ii} = 1$ (all the diagonal elements of $L$ are equal to $1$)?

What I know:

  • A tridiagonal matrix is a band matrix that has non-zero elements only on the main diagonal.
  • Matrix $A$ is positive definite if for all $u\in\mathbb{R}^N\backslash\{0\}$ we have that $u'Au > 0$.

I have no clue how to handle/solve this, thanks in advance!

$\endgroup$
  • $\begingroup$ Have you previously partitioned matrices into blocks? In particular, have you multiplied two partitioned matrices together and expressed the result in terms of the individual blocks? $\endgroup$ – Carl Christian Nov 9 '17 at 10:15
  • $\begingroup$ @CarlChristian I have previously partitioned matrices into blocks, but I've never multiplied partitioned matrices! $\endgroup$ – titusAdam Nov 9 '17 at 10:32
  • $\begingroup$ You should give it a try and then see if you can not derive an algorithm for doing a Choleksy factorization. then move on to LDLT second. $\endgroup$ – Carl Christian Nov 9 '17 at 12:02
  • $\begingroup$ @CarlChristian I will, thank for the hint! $\endgroup$ – titusAdam Nov 9 '17 at 12:10
  • $\begingroup$ Golub and Van Loan give an implementation. $\endgroup$ – J. M. is a poor mathematician Nov 14 '17 at 11:13
2
$\begingroup$

I will show how an $LDL^T$ factorization can be computed inductively. You will still need to explain why you never divide by zero, but this is the essence of my original hint.

Write $$A = \begin{bmatrix} A_{11} & A_{21}^T \\ A_{21} & A_{22} \end{bmatrix} = \begin{bmatrix} 1 & \\ v & L \end{bmatrix} \begin{bmatrix} \alpha & \\ & D \end{bmatrix} \begin{bmatrix} 1 & v^T \\ & L^T \end{bmatrix} = \begin{bmatrix} \alpha & \alpha v^T \\ \alpha v^T & LDL^T + \alpha vv^T \end{bmatrix}$$ Here $A_{11}$ has dimension $1$, $A_{21}$ and $v$ are column vectors of dimension $n-1$ and $A_{22}$, $D$ and $L$ have dimension $n-1$ and $\alpha$ is simply a scalar. The matrix $D$ is diagonal, $L$ is lower unit triangular. Evidently, $$\alpha = a_{11}, \quad v = \frac{1}{\alpha}A_{21}$$ and $L$ can be computed the matrix. $$A' = A_{22} - \alpha vv^T$$ which is symmetric and has dimension $n-1$.

The fact that your matrix has a particular sparsity pattern, i.e., is tridiagonal has not been used at all. It will allow you to greatly reduce the cost of computing $v$ and applying the symmetric update.

$\endgroup$
0
$\begingroup$

Let

$$ L(i,j) = \begin{cases} 1 &,& i=j \\ l_{ij} &,& j<i \\ 0 \end{cases} $$

and $$ D(i,j) = \begin{cases} d_{i} &,& i=j \\ 0 \end{cases} $$

Thus $$ L^t(i,j) = L(j,i) = \begin{cases} 1 &,& i=j \\ l_{ij} &,& i<j \\ 0 \end{cases} $$

Hence $$ (LD)(i,j) = \begin{cases} d_j &,& i=j \\ d_jl_{ij} &,& j<i \\ 0 \end{cases} $$ So finnaly $$ (LDL^t)(i,j) = \begin{cases} d_i + \sum\limits_{k=1}^{j-1} d_k l_{ik}^2 &,& i=j \\ d_j l_{ij} + \sum\limits_{k=1}^{j-1} d_k l_{ik} l_{jk} &,& i < j \\ (LDL^t)(j,i) &,& j < i \end{cases} $$

As we want to make $A = LDL^t$ we equate elements and solve row by row or column by column starting by the diagonal element since both $A$ and $LDL^t$ are symmetric.

Illustratively, going row by row, in the first row we have $$ a_{1,1} = d_1 $$ $$ a_{1,2} = d_1 l_{2,1} \implies l_{2,1} = \frac{a_{1,2}}{d_1} $$ $$ 0 = a_{1,3} = d_1 l_{3,1} \implies l_{3,1} = 0 $$ and inductively $l_{i,1} = 0$ for $i > 2$.

Similarly for the second row we have $$ a_{2,2} = d_2 + d_1 l_{2,1}^2 \implies a_{2,2} - d_1 l_{2,1}^2 = d_2 $$ $$ a_{2,3} = d_1 l_{2,1} l_{3,1} + d_2 l_{3,2} \implies l_{3,2} = \frac{a_{2,3}}{d_2} $$ $$ 0 = a_{2,4} = d_1 l_{2,1} l_{4,1} + d_2 l_{4,2} \implies l_{4,2} = 0 $$ and inductively $l_{i,2} = 0$ for $i > 3$. And so on...

Because $A$ is positive-definite, it follows that $a_{ii} > 0$ and therefore we will not have branch decision problems involving zeros in the algorithm.

Now you need to work by yourself a few simple examples to grasp the algorithm. Let me know if you get stuck.

Furthermore, notice that $LDL^t$ is always symmetric positive-semi-definite and so we require $A$ to be symmetric positive-definite for if $LDL^t$ is symmetric positive-definite then both $L$ and $D$ are invertible, that is, the decomposition will be unique.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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