Gaussian Elimination Example (with partial pivoting): GEE, it's simple!

A set of simple functions that illustrate Gaussian Elimination with partial pivoting

Description

The "GEE! It's Simple" package illustrates Gaussian elimination with partial pivoting, which produces a factorization of P*A into the product L*U where P is a permutation matrix, and L and U are lower and upper triangular, respectively.

The functions in this package are accurate, but they are far slower than their MATLAB equivalents (x=A\b, [L,U,p]=lu(A), and so on). They are presented here merely to illustrate and educate. "Real" production code should use backslash and lu, not this package.

For a detailed derivation of Gaussian elimination with partial pivoting, see Sections 3.1 and 6.3 of "Direct Methods for Sparse Linear Systems", Davis, SIAM, 2006 ( http://www.ec-securehost.com/SIAM/FA02.html ), or "Numerical Computing with MATLAB" by Cleve Moler, SIAM, 2004. You can obtain the PDF version of Cleve's book at http://www.mathworks.com/moler or you can buy a hard copy at http://ec-securehost.com/SIAM/ot87.html . See also Nick Higham's Matrix Computation Toolbox (File ID 2360), and his related book, Accuracy and Stability of Numerical Algorithms (SIAM, Second edition, August 2002, xxx+680 pp.).

I have tested this on MATLAB 7.5, but it should work on "any" MATLAB version. If you find a back-porting problem on older MATLAB versions, please let me know.

Acknowledgements

Using Numerical Computing With Matlab In The Classroom inspired this file.

• MATLAB release: MATLAB 7.5 (R2007b)

[Nikola Toljic]

Great. Thanks.

[John D'Errico]

As you might expect, this is good code. For a student, you should be able to read through this to see how a well written method for matrix factorization/solution is composed.

One of the things that you would learn from this submission is to use the capabilities of matlab to vectorize your computations. Look in these codes to find that row operations are done in single operations, not using heavily nested loops. The loops are still there of course, but they are implicit loops, and so will be more efficiently executed by matlab. Its easier to read code like this too.

Next, look in gee_its_simple_factorize to see the useful comments before each line. These comments explain what is done in the next step, clearly and readably. They allow you to visualize what is happening, how this code works. And next year, when you need to modify/repair a nasty piece of your own code, you will be very glad that you added comments like this.

Other things to emulate from this code are the copious references. Did I mention LOTS of comments? Help and comments are cheap, but at the same time, priceless.

In general, this is well worth reading. I'll bet that many people will learn something new here, even if you think you already know what an LU factorization is and how to use it. (I picked up something myself.) Of course, if you only want code to use, then the built in \, lu, etc., are the places to look.