[GSoC] Week 4: Fraction Free Algorithms
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. 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  and . One disadvantage in these fraction free methods is that the resulting matrix entries tends to grow larger than the naive algorithm described in . These can be avoided by observing that certain entries are divisible by other entries in the matrix. This is described in detail in .
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 .
 Fraction-free algorithms for linear and polynomial equations (1997) by George Nakos, Peter Turner, Robert Williams
 A Simplified Fraction-Free integer Gauss elimination algorithm, Peter R. Turner, Ph.D.
 Modified Gauss Algorithm for Matrices with Symbolic Entries, Benno Fuchssteiner.