[GSoC] Week 6: Cholesky and LDL Algorithms

This week I implemented Cholesky decomposition and LDL decomposition. In addition to that I fixed two errors In CSymPy. I was also bale to finish work with LU decomposition and merge it to master. Also, I could solve the system Ax = b using fraction free LU factorization.

Cholesky Decomposition

Cholesky decomposition can be applied to a Hermitian positive definite matrix. Hermitian matrix is a matrix with complex entries that is equal to it’s conjugate transpose [1]. Hence a symmetric matrix with real entries can be considered as a Hermitian matrix and can be decomposed using Cholesky decomposition if it’s positive definite. A Symmetric matrix A is positive definite if z^TAz is greater than zero for every non zero column matrix z [2]. If the above conditions are satisfied, Cholesky decomposition for a matrix A can be written as A = LL^* where L is an lower triangular Matrix. This is equal to A = LL^T when L is a real matrix. This factorization can be used for fast solution of the system Ax = b. I am yet to use this decomposition in solving above mentioned system.

LDL Factorization

LDL decomposition is closely related to Cholesky decomposition. As the name implies, in LDL decomposition of a matrix A can be written as A = LDL^* where L is a lower triangular matrix and D is a diagonal matrix [3]. This decomposition can be used for some matrices which don’t have a Cholesky decomposition.

CSymPy printing error and simplification errror

I also worked on a printing error of CSymPy and a simplification error in Mul class which is used to represent multiplication types in CSymPy. There is still some work to be done to fix simplification error completely. The most important thing was that we were able to introduce a fix which doesn’t create a considerable slow down in speed after being applied.

References

[1] Hermitian Matrix, Wikipedia Article: http://en.wikipedia.org/wiki/Hermitian_matrix

[2] Positive definite Matrix, Wikipedia Article: http://en.wikipedia.org/wiki/Positive-definite_matrix

[3] LDL Decomposition, Wikipedia Article: http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: