Solving Linear Equations with Modified Cholesky Decomposition

In our previous tutorial, we have discussed about Cholesky decomposition which is a very important matrix factorization to solve a linear equation. But this technique has some drawbacks which are also discussed in the same tutorial. In this tutorial, we will discuss about modified Cholesky Decomposition which is an alternative version of Cholesky decomposition. This technique alleviates the requirement of square root operation which is a complex arithmetic operation. Similar to the Cholesky decomposition, the co-efficient matrix $A$ has to be a symmetric positive definite matrix in this technique. But in general, the co-efficient matrix can be rectangular or square and it may not be symmetric. Thus, traditional linear equation is not suitable for modified Cholesky based techniques. In order to solve the linear equations by modified Cholesky based technique, the traditional linear equation is multiplied by $A^T$ in both sides. New equation becomes.

(1)

where $y_{new} = A^Ty$ and $C = A^T\times A$ . Now, matrix $C$ is symmetric positive definite of size $n\times n$ . This matrix can be factored using modified Cholesky decomposition as

(2)

Here, $L$ is a lower triangular matrix having all the diagonal elements equal to 1 and $D$ is a diagonal matrix with off-diagonal elements equal to 0. This decomposition technique also known as LDL decomposition. Modified Cholesky decomposition is said to be efficient than both Cholesky and LU decomposition. Inverse of the matrix $C$ can be computed as

(3)

The elements of the $L$ matrix are computed by the following equations.

(4)

Here, variable $j$ can be varied from 1 to $n$ and variable $i$ can be varied from $j+1$ to $n$ . The following equation computes the elements of the matrix $D$

(5)

In order to calculate the inverse of the matrix $C$ , inverse of both the matrix $L$ and $D$ should be computed. The inverse of the matrix $L$ is computed by the following equation.

(6)

Matrix $D$ is a diagonal matrix where all the off-diagonal elements are zero. Thus, computation of reciprocal of the diagonal elements are enough. This can be done by a dedicated reciprocal unit.

Comparison with Cholesky Factorization: Modified Cholesky Factorization is more popular than Cholesky Factorization. This is because, Cholesky Factorization involves square root operation as well as reciprocal operation to evaluate the elements of L and inverse of L respectively. Both these operations have higher computational complexity. In modified Cholesky decomposition, only reciprocal operation is required.

MATLAB code for Modified Cholesky (4006 downloads )

Related Posts