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 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
in both sides. New equation becomes.
(1) ![Rendered by QuickLaTeX.com \begin{equation*} y_{new} = Cx \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-77314c175f3d0282ed994ac4e46babff_l3.png)
where and
. Now, matrix
is symmetric positive definite of size
. This matrix can be factored using modified Cholesky decomposition as
(2) ![Rendered by QuickLaTeX.com \begin{equation*} C = LDL^T \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-68df5aef4a0929b4139908c7a90fab87_l3.png)
Here, is a lower triangular matrix having all the diagonal elements equal to 1 and
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
can be computed as
(3) ![Rendered by QuickLaTeX.com \begin{equation*} C^{-1} = (L^{-1})^TD^{-1}L^{-1} \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-8688a49228555be4a783da933cf0b936_l3.png)
The elements of the matrix are computed by the following equations.
(4) ![Rendered by QuickLaTeX.com \begin{equation*} L_{ij} = \frac{1}{D_{ij}}\{C_{ij} - \sum_{k=1}^{j-1}(L_{ik}L_{jk}D_{kk}) \} \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-1ad3b29d508ba2dd7100abe01dbcc558_l3.png)
Here, variable can be varied from 1 to
and variable
can be varied from
to
. The following equation computes the elements of the matrix
(5) ![Rendered by QuickLaTeX.com \begin{equation*} D_{ii} = C_{ii} - \sum_{k=1}^{i-1}(L^2_{ik}D_{kk}) \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-702ebc7656d54df959226b04a0104ca7_l3.png)
In order to calculate the inverse of the matrix , inverse of both the matrix
and
should be computed. The inverse of the matrix
is computed by the following equation.
(6) ![Rendered by QuickLaTeX.com \begin{equation*} L^{-1}_{ij} = -\sum_{k=j}^{i-1}L_{ik}L^{-1}_{kj} \end{equation*}](https://digitalsystemdesign.in/wp-content/ql-cache/quicklatex.com-c8bd7ca51812616306905ab363749046_l3.png)
Matrix 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 (3121 downloads )