# [GSoC] Week 5: Matrix Decompositions

Hi All,

Week 5 of the GSoC is over and I have made some progress in Matrix factorizations. I implemented LU factorization and QR factorization. Still I have to implement Cholesky factorization. I hope to do it during the Weekend.

## LU factorization

LU factorization was invented by Alan Turing and this is very important when solving a system of equations. In LU decomposition we try to factorize a given square matrix into a product of two matrices, L and U where L is a lower triangular matrix and U is a upper triangular matrix. The factorization can be a true factorization i.e. A = LU or it may be the process of finding two matrices L, U which can be used in solving the system Ax = B. In the latter case we don’t have A = LU. I implemented three different algorithms for LU decomposition.

#### Fraction Free LU decomposition in [1]

Fraction free version described in [1] results in two matrices, a lower triangular matrix L and a upper triangular matrix U. But this is not a true factorization i.e. A != LU in this case. The algorithm is more focused in a factorization that helps to solve a system Ax = B. So we are only interested in finding two matrices which can be used in backward / forward substitution to solve the system.

#### Normal and Fraction Free version in SymPy

I also implemented the normal and fraction free version of the algorithm in SymPy which gives an exact factorization A = LU. Normal algorithm results in fractions and not good for numerical calculations if you are not using arbitrary precision arithmetic. In contrast fraction free versions do not generate these kinds of fraction as a result of the decomposition. These algorithms can be found in [2] and [3] respectively.

## QR decomposition

In QR decomposition we find two matrices, an [orthogonal matrix](http://en.wikipedia.org/wiki/Orthogonal_matrixand  a upper triangular matrix R such that A = QR. Here A doesn’t have to be a square matrix.There are several method to calculate QR factorization but SymPy uses Gram–Schmidt process. The Algorithm can be found in [4].

## Issues

QR decomposition is not a `symbolic friendly` algorithm as it involves finding square root. I searched thoroughly for an algorithm that is suited for symbolic entries but couldn’t find one.

## References

[1] Algorithm 3, page 14, Nakos, G. C., Turner, P. R., Williams, R. M. (1997). Fraction-free algorithms for linear and polynomial equations. ACM SIGSAM Bulletin, 31(3), 11–19. doi:10.1145/271130.271133.