The goal of this assignment was to compare the error obtained from using variations of the Gaussian Elimination method for solving linear systems of equations.

Four variations of Gaussian Elimination to solve linear systems (along with a test program):

• Version 1: Gaussian Elimination with Backwards Substitution and Partial Pivoting using first pass reduction to row-echelon form (upper triangular matrix with 1's along the diagonal - sort of normalization step to obtain a leading one for the top row of the kth submatrix).
• Version 2: Gaussian Elimination with Backwards Substitution and Partial Pivoting using first pass reduction to upper-triangular form only.
• Version 3: Gauss-Jordon Elimination where the first pass reduces the matrix to reduced row-echelon form (identity in the coefficient matrix) and the solution is obtained by a trivial pass through the resulting matrix.
• Version 4: Gaussian Elimination with Backwards Substitution, FULL Pivoting, and upper-triangular matrix reduction only.
• Test program showing how the modules are used.

The following routines provide more extensive testing, timing performance measures, and comparison of accuracy:

• main.cpp: the main test driver program (see comments in code for details).
• dsvdcmp.cpp: singular-value decomposition routine.
• svdtest.cpp: module providing various supporting routines for testing purposes.
• unif_rand_dbl.cpp: module that aid in the generation of uniformly random numbers (for test cases).
• utils.cpp: another module of various supporting routines including the computation of norms and other error metrics.
• utils.h: header file for all modules.
• The test matrix creation routines for the well-conditioned (goodboy), ill-conditioned 1 (badboy1), and ill-conditioned 2 (badboy2).

How were the test matrices created?

• test 1 (goodboy): well-conditioned matrices were created by adding small random number (between -0.25 to 0.25) to each entry of a permutation matrix.
• test 2 (badboy1): ill-conditioned matrices were created by multiplying a lower triangular matrix by an upper triangular matrix both having small diagonal entries (in [0,1]) and larger off-diagonal values (in [0,10]).
• test 3 (badboy2): another set of ill-conditioned matrices were created specifically to defeat the partial-pivoting strategy by using the form shown below. A few iterations of the Gaussian elimination process shows why partial pivoting fails and full pivoting excels. Notice the right hand column values increase by powers of two as a function of the matrix size; full-pivoting would have selected one of these values and avoided this rapidly increasing value behavior. When the final column is reached the larger values near the bottom of the last column will cause a great deal of inaccuracy for the partial pivoting strategy.

[  1  0  0  1 ]   [  1  0  0  1 ]   [  1  0  0  1 ]   [  1  0  0  1 ] 
[ -1  1  0  1 ]   [  0  1  0  2 ]   [  0  1  0  2 ]   [  0  1  0  2 ]
[ -1 -1  1  1 ]   [  0 -1  1  2 ]   [  0  0  1  4 ]   [  0  0  1  4 ]
[ -1 -1 -1  1 ]   [  0 -1 -1  2 ]   [  0  0 -1  4 ]   [  0  0  0  8 ]

Graphs showing the condition number, forward error (L2 norm of diff between actual and computed solution), and relative speed of the four versions of the solver for varying matrix sizes n from 1 to 80:

• Condition Number
• Forward Error
• Relative Speed