[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.
Advertisements

2 Comments

  1. 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. 🙂

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: