Assignment 4

A Parameterized Matrix Class and the Vandermonde

Due Date: Wednesday, Mar. 7, 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 give you more practice with the first few items listed below. And, as stated with the previous assignment, you will do good NOT to delay the implementation of the your solution to this assignment.

  • 1. templated classes

    2. templated functions

    3. overloading operators

    4. interactions between objects of differing classes

    5. math

Resources:

• UML Quick Reference

  • Unix help This is an UMR help site for the basics of Unix.

  • mathworld.wolfram.com Cool stuff about math

The Concept:

• In the last assignment, you had to write and use array classes. In a mathematical sense, there isn't much difference between an array and a vector. But in the programming world, there is. For a vector class you need to add functionality to reflect how vectors are used in mathematics. In the last assignments, you were using arrays of arrays, or vectors of vectors, or arrays of vectors, or .... Well, that situation isn't so uncommon. They are called matrices. And for this assignment, you are to code up a general (parameterized) matrix class for dense matrices (no assumption that some significant part of the matrix is a bunch of zeros). But to do this, you will have to modify drastically your array class to include the functionality of vectors. If it's already there, much the better. The most popular matrix is the square matrix (contrary to the socially accepted norm - nobody likes a square - but we don't care). So, you can assume that the number of rows and the number of columns will be the same, but you can code your class for differing row and column sizes if you like.

  • In order to make this assignment really exciting, you are going to use your matrix and vector classes to solve a problem. (Note: Also write your own vector class.) You remember how to solve linear systems using Gaussian elimination? Yes, I thought so; we've all been doing that since 8th grade. Now is the time to code this process using OOP. I want you to code Gaussian elimination in at least two ways. You are to code the process using no (or "trivial") pivoting and then using a more advanced pivoting method such as partial pivoting or scaled partial pivoting. If you are unfamiliar with these techniques, they are presented in many texts on elementary numerical methods and you certianly should have seen it in your cs 228 course. I have several such texts, if you need to borrow one. If you are unable to find any reference to this technique, you can ask me. You can always try the "mathworld" link above.

  • The problem you will be applying your linear system solver to is that of finding the coefficients of an interpolating polynomial. You learned how to do this in Cs 228 using Lagrange and Newton polynomial techniques. The technique you skipped is that of solving the Vandermonde matrix because it is computationally difficult, though conceptually simplistic. To wit: you are trying to find the n+1 coefficients of the n degree unique interpolating polynomial to fit the set of n+1 points (x_i, y_i) by solving the system:

  • a₀ + a₁x₀ + a₂x₀² + . . . + a_nx₀ⁿ = y₀ . . . a₀ + a₁x_n + a₂x_n² + . . . + a_nx_nⁿ = y_n

• This is a system of n equations in n unknowns, and solving it is equivalent to solving the interpolating polynomial problem. That is, you are finding the n coefficients for the polynomial by solving the system

  • Xa = y, where X = [x_i^j] for i, j = 0, 1, ... , n. a = [a₀, a₁, . . . ,a_n]^T and y = [y₀, y₁, . . . , y_n]^T

• X is called the Vandermonde matrix.

  • I will provide a data set for you containing an integer n representing the number of (x, y) pairs to follow (white space between each number):

  • 11 -1 0.09090909091 -.8 0.1351351351 -.6 0.2173913043 -.4 0.3846153846 -.2 0.7142857143 0 1 .2 0.7142857143 .4 0.3846153846 .6 0.2173913043 .8 0.1351351351 1 0.09090909091

  • The format of this file is what you should code your project to accept. Your driver should take as a command line argument the name of the file containing such data.

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. I wanted you to experience the STL to know the reason you should consider building your own data structures. It may be difficult, but once you understand the benefits, you will agree that it is worth the trouble. I will discuss in class several different ways to build your class. You can choose one of these or you can use some other way that you believe is better. Of course, you will be graded on your implementaions. There are pros and cons to the various methods. You may discover these on your own.

  • 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 object use of overloaded stream operators

    • provides operators for the standard matrix arithmetic operations of addition, subtraction, matrix multiplication, scalar multiplication

    • provides 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 templated class allowing the user of the class to parameterize the matrix with whatever type he/she/it wishes. Thus, you could have a matrix of floats or ints or bobs (the general, all-purpose variable).

  • So for this assignment, you are going to have several classes: matrix, vector, gaussian_solver, and any other you deem appropriate. Some details to consider:

• • 1. You don't have to provide indexing into the matrix with [ ]'s, but it's nice

    2. Make sure that your operations are provided for in the proper location. For example, multiplication of a matrix by a vector should be provided in the matrix class.

    3. If you overload insertion and extraction (and you WILL), use them. By the way, it's good to have two versions: one for files and one for others.

    4. Follow the reasonable guidelines for overloading operators (make multiplication the * and not the +).

    5. Make sure that your matrix multiplication checks for appropriate size considerations and delivers the properly dimensioned resultant.

• So, your submission needs to include your classes and a driver that uses your constructions to solve a linear system using your two pivoting techniques. Also, in order that we know your matrix multiplication is working, first demonstrate that operation in your driver by multiplying the Vandermonde (matrix) by its transpose. (You could wow us by including functionality to return the transpose of a matrix.)

  • As always, make your output easy to read. Pay particular attention to this requirement as your grader will have to read that output and it is so important to keep him happy.

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