File Exchange

image thumbnail

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

version 1.2 (10.8 KB) by

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

10 Downloads

Updated

View License

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.

Comments and Ratings (3)

Raechel Cole

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.

Updates

1.2

Converted to a toolbox. Modified copyright statement and URL's in the comments. No change to the code itself.

1.1

Trivial change to Contents.m, to remove reference to GNU GPL. This package is now under the BSD license.

Update description only; file unchanged.

MATLAB Release
MATLAB 7.5 (R2007b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video