Assignment 5
An Abstract Matrix Class and A Derivative
Due Date: April 8, 2016
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 a 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 (but not your personal problems).
Resources:
Documentation for the Standard Template Library
Unix help This is an S&T help site for the basics of Unix.
mathworld.wolfram.com Cool stuff about math
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. 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 of 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: you were exposed to this when contemplating your code for the last assignment. Some are good methods; some are not. ... and some are really not. Once again, 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 templatededed class allowing the user of the class to parameterize the matrix with whatever type he/she/it/them/those wishes.
So for this assignment, you are going to have several classes and a driver.1 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 (at least) one derived class for this assignment; others will follow in later assignments. The one required derived class is to be a tridiagonal. A tridiagonal matrix is characterized this way:
nAn = [aij], where aij = 0 when i > j + 1 or j > i + 1.
This means that every element off the sub-, main, and super-diagonals is 0. It should be noted that this doesn't say anything about those elements on the diagonals; they might have 0's and they might not.
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. For example, 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 once again solve a system Ax = b, but for a different system using a different technique to determine a different interpolating polynomial for the same data! Wow, what can that possibly mean? Well, in program #4 you produced a single(interpolating) polynomial that passes through some data. The idea was that this polynomial closely approximates the function that produced the data. At least, that's the hope. Did it? Well, you don't know since you don't know where the data came from. If it was empirical data, there is no mathematical function that produced it. But in this case, there was. So how closely did your polynomial approximate the function I used to generate the data? You're going to find out. But in this assignment you are going to generate a much better approximating polynomial. You are to generate a cubic spline to fit this data. Then you will compare the values of the spline, program #4 polynomial, and "true" functional value to see which interpolating polynomial (the spline or the polynomial from program #4) is a better fit.
So what is a cubic spline? You covered this in CS 228. Look it up. You'll find that a cubic spline is a piece-wise defined cubic polynomial for which you must determine the 4 coefficients for each pair of points. So if you have N+1 points, then you will have to find 4N coefficients for the N cubic polynomials, si:
si = a0 + a1x + a2x2 + a3x3 i = 1, 2, ... , N.
Now, as shown in CS 228, this boils down to solving a system Ax = b where A and b are determined (by some ugly formula) and A turns out to be tridiagonal. Coool! You will also find that there are several "kinds" of cubic splines as determined by "end conditions". It is sufficient for you to produce a Natural Spline. If you get bored, you can add in options for other types. I can talk a little about cubic splines in class, if you ask me to. I'll try to make it warm and fuzzy so that it isn't too upsetting. A cup of hot tea or warm milk will help; you have my permission to bring one or the other.
As for the comparison of technique, I want you to compare the values of the single polynomial generated in program #4, your cubic spline, and the data generating function (the "true" value)
f(x) = 1 / (1 + 10x2)
at the four x values: -2.0, -0.9, - 0.7, and 0.1. You'll note that -2.0 is extrapolation and the others are interpolations. Present your results in some kind of tabular form and include the absolute error and the relative error for the four values. Put this in a data file with your other files. If you have a question about the format of this, ask the grader. If you want to generate some spiffy graphs of the curves, that would be fine; you can hand such in with your UML and gradesheet.
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), N pairs of numbers representing points in the plane for your cubic spline. I'll post the same data HERE as you used in the last assignment.
Deliverables:
Code: I will test that the code you submit does indeed compile and run. You are to submit as usual. 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).
1This is way cool. This puts you in the same league as those rich kids attending a high-priced ivy league schools in the East - a couple of classes and a chauffeur.