Assignment 3

Parameterized Vector Class and The QR Decomposition

Due Date: Feb. 17, 2012 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. Note: you've already handed in your very last hand-drawn UML diagram

Purpose:

  • The purpose of this exercise is to give you more practice with the basics of C++. In addition, I want you to have some experience coding the necessary constructs using the OOP paradigm for some basic vector analysis. You might recall studying Jacobi and/or Gauss-Seidel iteration to solve a linear system of linear equations? Ok, maybe not. But it doesn't matter; this assignment has nothing to do with that topic. However, you are going to learn how to transform one set of vectors into another set of vectors which possess a special property. At the same time, a third set of vectors will be produced; these little gems will just knock your socks off! with their special brand of specialness. So, you will be reviewing the following topics:

      1. templated classes

      2. templated functions

      3. overloading operators

      4. the STL; in particular, the vector class

      5. the concept of possibly implementing algorithms as classes

      6. The QR decomposition

Resources:

The Concept:

    • It is common in mathematics that n-tuples of values are used. You see this in just about every branch of scientific investigation. This is the reason we spend so much time in our classes studying vectors and arrays. Now, one of the key questions when working with a set of vectors of real numbers is whether or not they are linearly independant. This is a key concept as a set of linearly independent vectors forms a basis (a set of basic building blocks) for the vector space spanned by this set. (We'll talk about this in class in the coming weeks.) We define linear dependence of a set of non-zero vectors

    • S = {v1, v2, .... ,vn}

  • as follows: S is linearly dependent if there exist real constants α1, α2, ... ,αn not all zero such that

    • α1v1 + α2v2 + ...+ αnvn = 0

  • Furthermore, S is linearly independent if the only solution to the above equation is α1 = α2 = ... = αn = 0. An alternative way of stating this is: if any one of the vectors vk can be written as a linear combination of the other vectors, then the set is linearly dependent. What this means is that for, say vk, there are constants β1, β2, etc. such that

    • vk = β1v1 + β2v2 + ... + βjvj, for some j != k.

  • The QR Decomposition algorithm will produce from a set of n linearly independent vectors Ai a set of n linearly independent orthonormal vectors Qi, and a set of vectors Ri whose components are multipliers produced by the decomposition. The Qis will be an orthonormal set. What this means is that Qi . Qj = 1 for i = j, and Qi . Qj = 0 for i != j. This is a very important and useful property for vectors. Now, for 1 <= k <= n, Rk = [r1, r2, . . . , rn] will be such that rj = 0 for j > k. So, for example, R3 would be of the form [r1, r2, r3, 0, . . . , 0]. I will discuss the algorithm with you in class. You are going to code this method. Once you code it, you will be able to check how well it works on a set of vectors by finding all the dot products of the Q vectors, Qi . Qj, to see if you get what you expect.

Program Specifications:

    • You will start by writing a templated vector class. For your vector class, I suggest that you start with the text authors' array class and add functionality you think appropriate. It is mandatory to have the following:

      • overloaded operators +, - binary, - unary, * dot product, * scalar-vector product, [ ], =

      • appropriate constructors

      • stream operators << and >>

  • You will write function classes to perform the above operations (QR). How? You decide an appropriate structure for your program. Sit back tonight with a tall glass of warm milk and a cookie and use your UML to design a really awesome program. You will need a vector of your vectors. You decide whether you will use the STL vector class or your vector class to contain your set of vectors.

    • Among other considerations for this assignment, you will have to give attention to memory dynamics -- the allocation and use of that very resource. Consider how you will use memory, how you will program your vector class, how STL vectors use memory, etc.

    • Again, I want you to have your program read in data from a file. Some data to run your program on is:

    • 10 44 -2 -6 6 6 0 9 8 -2 3 9 34 -2 -6 -6 -1 1 -4 5 -5 -9 5 33 -4 4 0 -6 -1 -2 2 -3 -7 -9 50 6 4 6 -7 7 -1 2 -8 7 6 54 5 8 8 -3 9 -7 2 9 9 4 61 5 -8 9 1 -8 3 -2 3 -4 5 35 -9 1 7 3 5 7 -7 -9 5 6 54 -4 0 8 2 7 1 0 -6 0 -5 35 7 1 -9 -2 6 -7 8 2 3 0 -8 10 1 2 1 1 0 0 1 0 -1 0 2 6 4 2 1 0 2 2 0 1 3 14 12 3 4 1 4 9 6 5 1 2 1 2 2 3 1 1 1 3 0 2 2 -1 1 3 2 0 1 -1 2 4 3 3 -2 -7 -1 4 0 2 1 2 0 1 0 1 1 0 -1 0 0 2 4 0 -1 -4 3 9 0 7 1 0 -3 2 1 2 -1 -3 -1 0 0 2 2 1 3 4 0 4 5 7

    • The format of the file is this: the first number is an integer giving the dimension of the vectors to follow. You can assume that the number of vectors in the set is the same as the dimension of the vectors. Whitespace separates each value. You can also assume that your program will be tested on double precision data.

    • Use command line arguments (argc and argv[ ]) to give the user (you and the grader) the ability to pass a file name to the program for reading in data.

    • Your program is to output the following:

      1. a testing of your vector class that includes:

          • the sum, difference, and dot product of the first two vectors in the data set read in

          • demonstration of your output stream operator

          • demonstration of your [ ] operator

      2. the orthonormal set of vectors, Q, and the vectors R

      3. the n2 dot products of the Qis

  • Make sure that your output is in very readable format.

Deliverables:

    1. Code: We 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 (during class).

    4. DO NOT turn in a script printing.