Assignment 6

An Abstract Matrix Class and Derivatives

Due: April 25, 2014 at class time

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 several "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. Combining the above noted ideas, you will see how polymorphism can improve the efficiency of your code for solving these problems and others.

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.

• 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 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. I urge you to try to use an abstract base class and polymorphism. You will have derived classes for these types: diagonal matrix (a_ij = 0, for i != j); symmetric matrix (a_ij = a_ji); banded matrix (a_ij = 0, for i > j + 1 and j > i + 1). Considerations to think about:

    1. make as many of your matrix operations pure virtual functions as possible

    2. use data storage techniques that are as efficient as possible; i.e. a diagonal matrix should only require n memory units and a symmetric matrix should only use n(n+1)/2 memory units.

    3. derived classes should function correctly in all manners: e.g. if A is diagonal, then a query of A[4,5] had better return 0.

    4. arithmetic operations should be efficient; e.g. multiplying a vector times a diagonal matrix should have only n 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 the method of "steepest descent". I will give you documentation regarding this method in class; I just don't have it in me to word process it here and now. Let's all give thanks to Xerox for copy machines. Now, you should all understand that the method of steepest descent is an iterative method that works ok (just ok), but only for systems Ax = B where A is positive definite. What's that you say? A matrix A is positive definite if, for all vectors X, XAX^T > 0. Well this idea is difficult to work with, so let's cast it in a different light. This condition is satisfied by A being symmetric and diagonally dominant. That means that, for each row in A, the absolute value of the diagonal element is greater than the sum of the absolute values of the remaining elements in the row.

  • Thus, you should include in your program submission a method to determine that a matrix is indeed diagonally dominant. Given that it is, you may apply your code to solve the system Ax = B, for the input matrix A and vector B, using the method described above.

  • 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. Here's a sample file HERE .

Deliverables:

• 1. Code: I will test that the code you submit does indeed compile and run. You are to submit all your source code along with a makefile. How to do this is explained in Submission procedure.

  2. 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.

  3. Your gradesheet and UML (in class, of course).