Assignment 5
An Abstract Matrix Class and Some Derivatives
Due Date: March 25, 2011
Required for submitting:
Grade Sheet Print this sheet and bring it to class the day the program is due.
Bring your UML diagram to class.
Purpose:
The purpose of this exercise has many faces. Most importantly, you need to have experience writing an abstract interface base class from which you will derive "specialized" classes. To this end, you will write a generalized matrix class - an interface base - for representing the many kinds of matrices commonly encountered in numerical recipes. This will be a good exercise in applying polymorphism to the matrix operations problem. Furthermore, you will experience the use of (pure) virtual functions. And from the point of view of mathematics, you will become familiar with these various categories of matrices and hopefully discover how to take advantage of their characteristics in solving problems, like Ax = b. (Applying these techniques to solve personal problems is little more tricky.) Combining the above noted ideas, you will see how polymorphism can improve the efficiency of your code for solving these problems and others.
Resources:
The Concept:
When learning about matrix operations in your elementary linear algebra or matrix algebra class or introductory numerical methods class, you probably tended to see one matrix as pretty much like the next matrix. Yes, you may have recognized the outward difference in the appearance of banded, diagonal and triangular matrices, but didn't really think about the mathematical / computational impact that these special attributes might have. Certainly you did notice that if a coefficient matrix for the problem Ax = b had a bunch of 0's in it then the generation of a solution with the usual hand-calculating techniques would be vastly simplified. Well, if you don't take advantage of this type of info in the way you program your solution techniques using the computer, then you pass up the opportunity to cash in on the savings of time and resources offered. At the same time, though, you don't really want to think of any matrix as being profoundly different from any other matrix on the face of it.
To this end, your abstract matrix class will allow its user to view a matrix as a matrix but also to take advantage any special attributes of any particular matrix type. Thus, you will use polymorphism to implement differing techniques for
data storage
matrix arithmetic operations
matrix-vector arithmetic operations
matrix element access
Program Specifications:
Now, you are free to use the design for your implementation as you like. There are many possibilities. Some are good methods; some are not. ... and some are really not. Don't use the STL vector class to contain your data. Your matrix class isn't very useful unless it can function like a matrix is expected to function, in the traditional mathematical ways. Thus, it is expected for this assignment that your class:
allows examination (can't be useful if you don't know what is in it)
provides objects use of overloaded stream operators (you must be able to output/input information)
provide operators for the standard matrix arithmetic operations of addition, subtraction, matrix multiplication, scalar multiplication
provide functionality for matrix - vector multiplication.
For this assignment, you may assume that the matrices will be square; num rows = num cols. That may change for future assignments. If you wish to include more functionality, please feel free to do so. And, of course, your class is to be a templateded class allowing the user of the class to parameterize the matrix with whatever type he/she/it wishes.
So for this assignment, you are going to have several classes and a driver. Use the "object-oriented" paradigm as it was really meant to be used. I am leaving the design considerations up to you. But you must use an abstract base class and polymorphism. You will have derived classes for upper and lower triangular matrices (aij = 0, for i > j and aij = 0, for i < j, respectively).
Considerations to think about:
make as many of your matrix operations pure virtual functions as possible
use data storage techniques that are as efficient as possible. Of course, you should realize that a triangular matrix should use far less storage than a "regular" (dense) matrix.
derived classes should function correctly in all manners: e.g. if A is upper triangular, then a query of A[6,5] had better return 0.
arithmetic operations should be efficient; e.g. multiplying a vector times a triangular matrix should have only n(n+1)/2 multiplies and not a bunch of 0-multiplies.
Of course, creating the working tools isn't any fun unless you use them to solve some profound problem. Therefore, as part of this assignment, you are going to solve Ax = B for x. I know it's mighty tempting to divide by A, but if you do that this campus will look like "the night of the living dead mathematician" as all the great mathematicians of centuries gone by will roll over in their graves and come after you. No, instead we'll use another method. You've already coded Gaussian elimination, so that isn't interesting anymore. We're going to revisit another method you learned in CS 228: the method of LU - decomposition. You need to read up on it. I will discuss it in class next week. In its simplest form, it is fairly easy and without complications. However, not all matrices have an LU - decomposition that doesn't require permutations during the process. This makes the process a bit more sticky and you'll have to be careful how you keep track of this information. In any case, you'll solve the system Ax = b using the LU method and your really nifty abstract matrix class(es).
Submit the usual: all code including a driver. The driver is to test the abstract class and test it thoroughly. You design the test. Also, make the driver able to take command line arguments for the name of a file containing data: an int giving the size of the problem (N), an N x N matrix A, a vector B. In the future I will post a sample file HERE . With this data, you will solve the system.
Deliverables:
Code: I will test that the code you submit does indeed compile and run. You are to copy all your source code along with a makefile into your cs328 directory. How to do this is explained in Submission procedure.
makefile: Supply the makefile which compiles and builds your program as detailed above. I really suggest that you play around with and use the third of the makefiles I posted.
Your gradesheet and UML (in class, of course).