[GSoC] Week 2: Gaussian Elimination

Hi All, sorry for a late blog post. During the past week I worked on implementing
gaussian elimination and correcting some bugs. I had a very slow progress during
the past week due to the time spent on correcting the bugs and because of the busy
schedule I had during the week. I wish to cover up for that during this week.

Row Reduction

Gaussian Elimination is a method for solving matrix equations of the form
Ax = b. It is done by perfroming a sequence of operations on the matrix
entries. This method can be used to find the determinant and inverse of a matrix. The
method is named after great mathematician Carl Friedrich Gauss.

The set of operations allowed on the matrix entries are called elementary row
operations. Below are the three operations that are allowed.

1. Add a.(row~j) to (row~i) of the matrix.
2. Interchange (row~i) and (row~j).
3. Multiply (row~i) by a constant c.

The simplest non-zero matrices are called matrix units and they are denoted
by e_{ij}. This denotes the matrix where only the {ij}^{th} entry is
one and every other entry is zero. With this definition, above three row
operations are equal to the left multiplying a given matrix by the following
matrices respectively. These matrices are called **elementary matrices**.

1. I~+~ae_{ij}
2. I~+~e_{ij}~+~e_{ji}~-~e_{ii}~-~e_{jj}
3. I~+(c-1)e_{ii}

Here I is the identity matrix of appropriate size.

Row reduction algorithm

I implemented the algorithm in SymPy that gives the reduced row echelon form
of the given matrix. It is a very naive algorithm not suited for symbolic matrices.
I wish to implement an elimination algorithm that’s more suited for symbolic
matrices during upcoming weeks.

Bugs in CSymPy

We found some bugs with `div` which were mainly originated in the constructor
for `Rational`. Currently, for performance reasons, there is an assertion in the
constructor for `Rational` that the input should actually be a rational number with
denominator greater than one. If the denominator is one, the assertion fails and
we get an error. We had to make sure that we are calling `Rational` with actual
rationals, not Integers.

Advertisements

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: