[GSoC] Week 4: Fraction Free Algorithms

Hi All,

As the week 4 of the GSoC comes to an end I was able to start implementing Matrix decompositions, starting with the LU decomposition.

Fraction Free Algorithms

Gaussian elimination is the procedure for reducing a given matrix to an echelon form. In Gauss-Jordan elimination, we reduce a given matrix into a reduced row echelon form. I implemented quite a few algorithms for Gaussian elimination and Gauss-Jordan elimination. The conventional algorithm for Guassian elimination is a very straight forward one and can be found in[1]. There are two problems in this algorithm. One is that we have to perform division which is not a good thing to do if the divisor is too small. Also, the above implementation doesn’t allow pivoting, which makes the algorithm not applicable to non-singular matrices.

To avoid the problem with division, I implemented a set of algorithms which results in fraction free matrix entries. These algorithms are described in detail in [2] and [3]. One disadvantage in these fraction free methods is that the resulting matrix entries tends to grow larger than the naive algorithm described in [1]. These can be avoided by observing that certain entries are divisible by other entries in the matrix. This is described in detail in [3].

Pivoting is also a concern in these algorithms. Since we are mostly dealing with symbolic matrices, first row below the current pow which has a non-zero element is chosen as the pivot row.

Also, I implemented a fraction free version of LU decomposition.

Plan for upcoming week

I hope to implement some other Matrix decomposition algorithms like QR and Cholesky in the coming week. Also, I wish to implement a Gaussian elimination algorithm which is more suited to matrices with symbolic entries. For the time being I am studying about it in [4].

References

[1] http://www.cs.rutgers.edu/~venugopa/parallel_summer2012/ge.html#algo
[2] Fraction-free algorithms for linear and polynomial equations (1997) by George Nakos, Peter Turner, Robert Williams
[3] A Simplified Fraction-Free integer Gauss elimination algorithm, Peter R. Turner, Ph.D.
[4] Modified Gauss Algorithm for Matrices with Symbolic Entries, Benno Fuchssteiner.