Assignment 6

An Abstract Matrix Class w/ Derivatives

Due Date: April 13, 2012

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 is to have you expand your experience with base classes and their derivatives. You have already written your abstract base matrix class and at least one derived class, the tridiagonal. You will now implement several other derived types. At the same time, you are going to learn a little (perhaps a lot) more linear algebra and more about numerical computation. Specifically, we are going to attempt calculating eigenvalues for a matrix. I say attempt because this is NOT a trivial problem in mathematics. But it is a very important topic as it finds applications in so many varied problems in applied mathematics.

Resources:

• UML Quick Reference

• Documentation for the Standard Template Library

  • Unix help This is an UMR 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 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

  • As usual, we will have an application part of this assignment covering concepts that you may or may not have seen before this. If you have taken linear algebra (as most of you I believe have) then you might have worked with eigenvalues and eigenvectors. You probably calculated them by hand through analytical means. It probably wasn't fun. So, any way that you can make that process more automated will almost certainly make your life better. So let's give it a whirl. I should warn you once again that this is NOT an easy problem. In fact, the method you will apply here will only work under certain very restricted conditions. To start, the matrix we start with, A, must be real (all elements of A are real numbers) and we assume n distinct eigenvalues A or dimension n.

  • The method we'll implement here is the QR Method. Does that sound familier? It should. It is from this iterative method for finding eigenvalues that I derived the QR decomposition technique for your 3rd assignment. I modified a matrix operation to work for a set of vectors. If you can imagine (I hope so) that the set of vectors you started with for that assignment are the columns of a matrix A, and that the other two sets of vectors you generated are the columns of two other matrices, Q and R, then you get the picture. To summarize, a matrix A can be decomposed into the product of two matrices Q and R where Q is orthogonal and R is upper triangular. You know what a set of orthonormal vectors is, so you know what an orthogonal matrix is now (one whose columns form an orthonormal set of vectors). So, you will need to recode your QR decomposition for a matrices. But this isn't all.

  • Here is the QR Method:

  • Let A₁ = A A_k = Q_kR_k A_k+1 = R_kQ_k k = 1, 2,...

• So, you start with A₁ = A. Decompose it into its Q₁ and R₁. Then switch the order of multiplication and set A₂ to R₁ * Q₁. Now decompose A₂ into its Q₂ and R₂ and so forth and so on. This is called an iterative technique. You will repeat it until you are satisfied with the result. That means you need "stopping criteria" for the process. You should at least control the number of iterations.

  • Convergence: Under nice conditions, this process will converge to something we can use. If it is the case that A has n distinct eigenvalues λ_i such that |λ₁| > . . . > |λ_n| and A is real symmetric, then the sequence {A_k} will converge to a diagonal matrix with the eigenvalues along the diagonal. If we relax the requirement for symmetry, then the sequence converges to a triangular matrix with eigenvalues on the diagonal. Take away the demand for distinctly ordered eigenvalues and the sequence will converge to a block diagonal matrix with blocks of order 1 or 2. This isn't perfect, but its pretty nice and we can extract the eigenvalues fairly easily at that point. But I'll talk more about it in class.

Program Specifications:

• Now, as before, 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. Start there; that is, pick up where you left off with program #5. You will have the following derived classes for this assignment:

  • 1. tridiagonal

    2. diagonal: a_i,j = 0 if i ≠ j

    3. upper triangular: a_i,j = 0 if i > j

    4. lower triangular: a_i,j = 0 if i < j

    5. symmetric dense: a_i,j = a_j,i

• • 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. For example, you should realize that a triangular matrix should use far less storage than a "regular" (dense) matrix.

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

    4. 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. As discussed above, you are to apply the QR method for finding eigenvalues of a matrix. Have your program take command line argumens for the name of an input data file. The file is to contain an integer corresponding to the size of the matrix to follow. I will post test data:

  • 3 -4 14 0 -5 13 0 -1 0 2 3 2 1 0 1 3 1 0 1 4

  • Notice there is more than one matrix in this file. The eigenvalues for these two matrices are: 6, 3, 2 and 4.7321, 3.0, 1.2679. Use this info to test your program. Output the eigenvalues of the matrix.

  • Addendum to Output Specs: Output the fifth, tenth, and final iteration of the A_k matrix and what you believe to be the eigenvalues of the matrix. State the iteration number and/or stopping criterion (i.e. why it was your last iterate). Also, output a test of your new derived matrix types by multiplying an upper triangular by an upper triangular, a diagonal by a diagonal. Using a 4 x 4 is good enough.

  • Submit the usual: all code including a driver.

Deliverables:

• 1. 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.

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