Programming Assignment II

Due on Friday, November 12, 2010 @ 11pm

100 points

In this programming assignment, you are to compare the three Gaussian elimination based methods: LU-Decomposition without pivoting, LU-Decomposition with partial pivoting, and LU-Decomposition with complete pivoting. More precisely, write a program to read in matrices A and b and solve for x in Ax = b with all three methods and do an accuracy analysis.

You should write one internal SUBROUTINE for each method and no subroutines and functions should use identifiers declared in the main program. More precisely, name your SUBROUTINEs as follows:

SUBROUTINE LUNP(...) for LU-Decomposition without pivoting.

SUBROUTINE LUPP(...) for LU-Decomposition with partial pivoting.

SUBROUTINE LUCP(...) for LU-Decomposition with complete pivoting.

You may choose the formal arguments and add other subroutines and functions as they fit. Use single precision only. In this way, the impact of pivoting would be clearer.

Input and Output

The input to your program has the following format. The first line contains a positive integer, giving the number of rows and columns of the input matrix A. You may assume that this value is greater than or equal to 2 and less than or equal to 10.


n  <-- a positive integer <= 10, the number of rows/columns
xx.xx  xx.xx  ....  xx.xx  values for row #1
xx.xx  xx.xx  ....  xx.xx  values for row #2
    .................      values for other rows
xx.xx  xx.xx  ....  xx.xx  values for row #n
xx.xx  xx.xx  ....  xx.xx  values for matrix b

After reading in n and matrices A and b, your program should solve this system with LU-decomposition without pivoting, LU-Decomposition with partial pivot, and LU-Decomposition with complete pivoting. For LU-Decomposition, your program output should follow the pattern shown below. Replace LU-Decomposition with LU-Decomposition with Partial Pivoting for LU-Decomposition with partial pivoting, and LU-Decomposition with Complete Pivoting for LU-Decomposition with complete pivoting. The last portion marked as Pivoting Elements shows the pivot elements. This portion should be blank for LU-Decomposition without pivoting. For partial pivoting, their is no column number because only rows are swapped. For complete pivoting, since rows and columns are swapped, row numbers and column numbers must be shown.


a blank line
*** LU-Decomposition ***
a blank line
Input Matrix A:
xx.xx  xx.xx  ....  xx.xx  values of row #1
xx.xx  xx.xx  ....  xx.xx  values of row #2
    .................      values of other rows
xx.xx  xx.xx  ....  xx.xx  values of row #n
a blank line
Input Matrix b:
xx.xx  xx.xx  ....  xx.xx  values of matrix b
a blank line
Matrix L and U After the Elimination Step: This is a single matrix with L in its lower diagonal part
xx.xx  xx.xx  ....  xx.xx  values of row #1
xx.xx  xx.xx  ....  xx.xx  values of row #2
    .................      values of other rows
xx.xx  xx.xx  ....  xx.xx  values of row #n
a blank line
Matrix b After the Elimination Step:
xx.xx  xx.xx  ....  xx.xx  values of the modified matrix b
a blank line
Number of row pivoting = XX  partial and complete pivoting only
a blank line
Number of column pivoting = XX  complete pivoting only
a blank line
Pivot Elements:
1:  Row=XX   Column=YY   Value=ZZZ  the location and value of max to be swapped to a_1,1
2:  Row=XX   Column=YY   Value=ZZZ  the location and value of max to be swapped to a_2,2
    other values
n-1:  Row=XX   Column=YY   Value=ZZZ  the location and value of max to be swapped to a_n-1,n-1
a blank line
Solution Matrix x:
xx.xx  xx.xx  ....  xx.xx  values of matrix x (the solution)
a blank line

Finally, print the following comparison results. In this summary, each row has the solutions from different methods and their absolute errors. On each row, the first value is the x_i computed with complete pivoting (C_i below), the second is the x_i computed with partial pivoting (P_i below), the third is the absolute difference between C_i and P_i (i.e., |C_i-P_i|)), the fourth is the x_i from LU-Decomposition without pivoting (G_i below), the fifth is the absolute difference between the LU-Decomposition result and the result with complete pivoting (i.e., |C_i-G_i|), and, finally, the sixth is the absolute difference between the LU-Decomposition result and the result with partial pivoting (i.e., |P_i-G_i|).


two blank lines
*** Summary Table ***
C₁   P₁   |C₁-P₁|   G₁   |C₁-G₁|   |P₁-G₁|
C₂   P₂   |C₂-P₂|   G₂   |C₂-G₂|   |P₂-G₂|
    .... other values ......
C_n   P_n   |C_n-P_n|   G_n   |C_n-G_n|   |P_n-G_n|

The complete output for one input should look like the following:


*** CS3911 Programming Assignment #2 ***
******* LU-Decomposition Methods *******

--- output of LU-Decomposition ---

--- output of LU-Decomposition with partial pivoting  ---

--- output of LU-Decomposition with complete pivoting ---

--- output of the summary table ---

You should use the format editors I, F, E, or G to align the columns so that they are readable.

Matrices L and U should occupy the space for the input matrix A. You will receive 0 point if you use separate matrices for L and U.

Sample Input Matrices

The first test matrix is a simple one. The following shows matrix A and matrix b. The solution is x₁ = 1, x₂ = 2, x₃ = 3, x₄ = 4, x₅ = 5 and x₆ = 6. Click here to download this file input-1.

The second test matrix is the so-called Pascal Matrix because it is generated from the Pascal triangle. Check the "anti"-diagonals (i.e., entries running from upper-right to lower-left). The following shows matrix A and matrix b. The solution is x₁ = x₂ = x₃ = x₄ = x₅ = x₆ = x₇ = x₈ = 10000. Click here to download this file input-2.

The third test matrix is the well-known Hilbert Matrix. In fact, it is the upper-left 5×5 portion of the infinite Hilbert matrix. The following shows matrix A and matrix b. The solution is x₁ = x₂ = x₃ = x₄ = x₅ = 10000. Click here to download this file input-3. Note that the input matrices do not contain exact values of the Hilbert matrix A and matrix b, and, as a result, your solutions may be slightly different from 10000.

There are other A's and b's with known solutions in our textbook. See page 128, problems P3.36 to P3.39, and page 618 for the solutions.

Very Important Notes

The following is a list of very important notes. Without following these rules, you will receive ZERO point.

You MUST use LU-decomposition. Moreover, while LU-decomposition is being applied to matrix A, matrix b is NOT available. As a result, matrix b can only be processed after LU-decomposition completes.
The lower triangular matrix L and upper triangular matrix U MUST share the same matrix throughout the whole LU-decomposition computation. You should not produce L and U into different matrices, and copy/merge them into a single one.
Use the ALLOCATABLE attribute and ALLOCATE and DEALLOCATE statements to acquire memory. You should not use ALLOCATE and DEALLOCATE in a function or subroutine, because local arrays can serve the same purpose.
Use FUNCTION and SUBROUTINE only even though you know MODULE.
FUNCTIONs and SUBROUTINEs should only use their formal arguments and local variables, and should not use any global entities (i.e., entities declared in the main program).

Submission Guidelines

General Rules

All programs must be written in ANSI Fortran 90.
Use the submit command to submit your work. You can submit as many times as you want, but only the last on-time one will be graded.
Your program should be named as prog2.f90. Note that Unix filename is case sensitive. As a result, PROG2.f90, prog2.F90, pROG2.f90, etc are not acceptable.
We will use the following approach to compile and test your programs:
```
f90 prog2.f90 -o prog2  <-- compile your program
prog2 < our-test-file   <-- test your program
```
This procedure may be repeated a number of times with different input files to see if your program works correctly.
Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
A README file is always required.
No late submission will be graded.
Programs submitted to wrong class and/or wrong section will not be graded.

Compiling and Running Your Programs

This is about the way of compiling and running your program. If we cannot compile your program due to syntax error, wrong file names, etc, we cannot test your program, and, as a result, you receive 0 point. If your program compiles successfully but fails to run, we cannot test your program, and, again, you receive 0 point. Therefore, before submitting your work, make sure your program can compile and run properly.

Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, and so on. Double check your files before you submit, since I will not change your program. Note again: Unix filenames are case sensitive.
Compile-but-not-run programs receive 0 point. Compile-but-not-run usually means you have attempted to solve the problem to some degree but you failed to make it working properly.
A meaningless or vague program receives 0 point even though it compiles successfully. This usually means your program does not solve the problem but serves as a placeholder or template just making it to compile and run.

Program Style and Documentation

This section is about program style and documentation.

For each file, the first piece should be a program header to identify yourself like this:

! ----------------------------------------------------------- 
! NAME : John Smith                         User ID: xxxxxxxx 
! DUE DATE : mm/dd/yyyy                                       
! PROGRAM ASSIGNMENT #                                        
! FILE NAME : xxxx.yyyy.zzzz (your unix file name)            
! PROGRAM PURPOSE :                                           
!    A couple of lines describing your program briefly        
! -----------------------------------------------------------

Here, User ID is the one you use to login. It is not your social security number!

For each function in your program, include a simple description like this:

! ----------------------------------------------------------- 
! FUNCTION  xxyyzz : (function name)                          
!     the purpose of this function                            
! PARAMETER USAGE :                                           
!    a list of all parameters and their meaning               
! FUNCTION CALLED :                                           
!    a list of functions that are called by this one          
! -----------------------------------------------------------

Your programs must contain enough concise and to-the-point comments. Do not write a novel!
Your program should have good indentation.
Your program must use IMPLICIT NONE and INTENT properly, and should not use GOTO.

Program Specification

Your program must follow exactly the requirements of this programming assignment. Otherwise, you receive 0 point even though your program runs and produces correct output. The following is a list of potential problems.

Your program does not use the indicated algorithms/methods to solve this problem.
Your program does not follow the structure given in the specification. For example, your program is not divided into FUNCTION, SUBROUTINE, MODULE, etc when the specification says you should.
Your FUNCTIONs or SUBROUTINEs should not use identifiers/entities declared in the main program.
Any other significant violation of the given program specification.
Incorrect output format. This will cost you some points depending on how serious the violations are. The grader will make a decision. Hence, carefully check your program output against the required one.

Program Correctness

If your program compiles and runs, we will check its correctness. We normally run your program with two sets of input data, one posted on this programming assignment page (the public one) and the other prepared by the grader (the private one). You program must deliver correct results for both data sets. Depending on the seriousness of the problem(s), significant deduction may be applied. For example, if your program delivers all wrong results for the public data set, you receive 0 point for that component.

The README File

A file named README is required to answer the following questions:

Question: Elaborate your way of implementing complete pivoting.
Question: For each sample input, discuss the accuracy of each method. In particular, analyze the differences between the true solutions and the solutions computed by each method. You have these results in the summary table in your output. Remember to use absolute error and relative error properly. There is a formula discussed in class giving the number of accurate digits.
Question: Study the pivoting values. How small are they for each sample input? Analyze the "patterns" of these pivoting values related to the sample input.

You should elaborate your answer and provide details. When answering the above questions, make sure each answer starts with a new line and have the question number (e.g., Question X:) clearly shown. Separate two answers with a blank line.

Note that the file name has to be README rather than readme or Readme. Note also that there is no filename extension, which means filename such as README.TXT is NOT acceptable.

README must be a plain text file. We do not accept files produced by any word processor. Moreover, watch for very long lines. More precisely, limit the length of each line to no more than 80 characters with the Return/Enter key for line separation. Missing this file, submitting non-text file, file with long lines, or providing incorrect and/or vague answers will cost you many points. Suggestion: Use a Unix text editor to prepare your README rather than a word processor.

Final Notes

Your submission should include two files, namely: prog2.f90 and README. Please note the way of spelling filenames.
Always start early, because I will not grant any extension if your home machine, network connection, your phone line or the department machines crash in the last minute.
Since the rules are all clearly stated, no leniency will be given and none of the above conditions is negotiable. So, if you have anything in doubt, please ask for clarification.
Click here to see how your program will be graded.