# [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_matrix) **Q **and 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

- Posted in: GSoC-2014-CSymPy
- Tagged: CSymPy, Linear Algebra, LU factorization, Matrix factorization, QR factorization, SymPy

I believe what you published was actually very reasonable.

But, what about this? suppose you were to write a awesome headline?

I mean, I don’t wish to tell you how to run your blog, but what if

you added something that makes people desire more? I mean [GSoC] Week 5: Matrix Decompositions | Thilina’s SymPy Blog is a

little vanilla. You might peek at Yahoo’s front page and see how they write article headlines to grab people to open the

links. You might add a video or a pic or two to grab readers interested about what you’ve got to say.

In my opinion, it could bring your posts a little livelier.

Thanks for the advice, I thought it was more of a systematic and consistent.

But I’ll try to have a more live title from here on. 🙂