CS 621: Fall 2002

| News | General Information | Syllabus | Assignment and Solutions | 

|Exams and Solutions |Book Errata | CVL Home |

Dec 20. The Final Exam (PS/PDF) and grading guide (PS/PDF) are available. You can pick up your exam in 4130 beginning January 6.

Dec 17. The exam is closed book.  

Dec. 11. A6 is graded. You may pick up your assignments from Nora or me (during office hours).

Dec 9.  Office Hours...

Dec 4. A6 comments. The P3 solution is used to solve P4. You are allowed to use schur in P3.  

Dec 4. The final exam is Wednesday, December 18, 3-5:30pm in Phillips 403. 

Dec 2. There will be a timed final exam: Dec 18, 3-5:30. Most exam questions will be tightly coupled with your assignments. Solution functions for such problems will be available during the exam.

Dec. 2. In A6, P1 there is a typo.The eigenvalues of [lambda beta;alpha lambda] are

           lambda +  i*sqrt(-alpha*beta)         and                   lambda -  i*sqrt(-alpha*beta)

In the same problem, the educational value of normalSchur is diminished upon realizing that in Matlab 6 it has a one-line implementation: [Q,T] = schur(A). So we'll grade the entire problem according to how well your normalSchur2 performs. (The test script is adequate for this.).

You are not allowed to use schur in your implmentation of normalSchur2.

In P2, you are not allowed to use expm in your implementation of MyExpM.

Nov. 18 In A5, you cannot use the Matlab gsvd function in P4. And in P2 exploit structure when you update A (i.e., A = Qk'*AQk) and Q (i.e., A = Q*Qk). "Structure" means skew symmetry and the fact that Qk is "nearly the identity".

Nov. 12.  The A5 scripts are ready and so is the handout (PS/PDF). A note about the second problem P2. Don't expect your skew34 to be as good as schur when the P2 script is run. This was a constructive mistake. In classical Jacobi one always chooses the smaller rotation angle. This has the effect of minimizing s = sin(theta) or (equivalently) minimizing the frobenius distance between the rotation and the identity. When we go to the block situation as in P2, these two criteria are no longer equivalent. Stick with skew34 minimizing the Frobenius distance. What should have been done is to choose that Q which has the smallest off-diagonal blocks. This generalizes the "minimize the sine" idea that drives the classical Jacobi process. Like all my mistakes, this one is extremely enlightening! You will see rather inferior convergence when skew34 is used to solve the subproblems. The Matlab schur function does not take any special steps to return a "nice" Q in [Q,D] = schur(B). However, it seems to make the cyclic-by-block row Jacobi process quite happy.

Nov. 5. Comments about problem 3-4. In ridge regression the idea is to choose a ridge parameter lambda and then solve

                (A'*A + lambda I) x = A'*b

instead of just (A'*A)x = A'*b. Cross validation is one approach for choosing lambda. The idea is to let lambda be the minimizer of the function C(lambda) which is defined on the top of page 584. The SVD can be used to simplify the evaluation of this function and the result is on the top of page 585. (There are two typos there. The upper limit on the summation is n = r = rank(A). Second, it is b_{k} in the numerator, not \tilde{b}_{k}.)

Now to minimize C you should use the Matlab minimizer fmin. An objective function must be passed to fmin and sometimes this objective function has parameters. For example, to minimize the quadratic ax^2 + bx + c across the interval [L,R], we write a Matlab function

          function z = f(x,a,b,c)              

          z = x*(a*x + b) + c

The script

     a=2;b=3;c=4;L=-1;R=7; xmin=fmin('f',L,R,[],a,b,c)

will return the x that minimizes 2x^2 + 3x + 4 on [-1,7].

In your problem you will do something similar, perhaps with matrix and/or vector parameters. I'm also asking that you pay a little attention to the termination criteria. help fmin will explain your options. 

Nov 4. The Assignment 4 scripts are available. The midterm solution scripts are available. The midterm solution guide is available (PS/PDF)

Oct 23. The generalized Yule-Walker system has a kp-by-p rhs and a kp-by-p solution. To see the relevance to the general rhs problem, mimic the derivation of the Levinson algorithm that is in the text. It'll involve block matrices and the block exchange matrix.

Oct 22. In the Levinson algorithm on page 197 (at the top) there is a typo in the expression that prescribes alfa. Should be alfa = -(r(k+1) etc) instead of (-r(k+1) etc.

Oct. 22. Some comments on indexing. 

Suppose R is a cell with entries that are p-by-p matrices. If A is an mp-by-mp matrix (thought of as a m-by-m block matrix with p-by-p blocks) then

    A((i-1)*p+1:i*p,(j-1)*p+1:j*p) = R{abs(i-j)}   (i neq j)

assigns R{abs(i-j)} to the  (i,j) block of A.

--------------------------------

Suppose f is kp-by-1 and E is the k-by-k block exchange matrix with p-by-p blocks. Then E*f = f(idx) where idx is computed as follows

    U = reshape(1:k*p,p,k); idx = reshape(U(:,k:-1:1),k*p,1)

Oct 21. P1: Take a look at the Sherman Morrison Formula!

Oct 21. P4. In the (regular) Durbin algorithm there is a place where you divide by something like (1+r'*y). Positive definiteness insures that this quantity is positive. (See the bottom of P. 194.)You will come to a point in your generalized algorithm where you'll have to assume some properties about a particular p-by-p linear system. You don't have to prove anything. However, you should at least offer some ideas/conjectures about the structure of this system.

Oct. 21. In P1 the calling sequence should be BlockSolve(A,B,u,v,c,d) not BlockSolve(A,u,v,c,d)

Oct 18. The take-home Midterm is available (PS/PDF).

Oct 11. The A3 due date is Friday, October 18. Hints on the problems can be obtained by looking at the revisions of the A3 handout. (PS/PDF). Do that!

Oct 7 A3 is available. Here are some hints/tips. 

P1: At the start of the j-th step we have the factorization 

                      [A11 A12;A21 A22] = [G11 0; G21  I]*[I  0; 0  C]*[G11 0;G21 I]' 

where G11 (j-1)-by-(j-1) and G21 are known. What if C(1,1)<=0?

P3:  Derive an n-by-n linear system that defines the s-vector, e.g., Ms = c. Trouble is, M can be rank deficient. So always solve Ms = c in the least squares sense using the SVD. Set a computed singular value sigma_k to zero if sigma_k <= 10*eps*sigma_1. Also, feel free to compute toeplitz-times-vector products using the Matlab Toeplitz function, e.g., Toeplitz(r)*x.

Sept 23. The final exam is Wednesday, December 18, 3:00-5:30pm. Make your travel plans accordingly.

Sept 11. Comments on Assmt 1. Being able to accomodate p = 'inf' is nice but not required in P1. For the required matrix vector operations in that problem you should NOT just let Matlab handle the matrix-vector products. Use a loop with saxpys features and exploitaion of the the band structure. The use of " normalized time"  just helps us eyeball the efficiency of your code by normalizing out the speed of your machine. Finally, I cited p 568 so that you would be aware of the Horner idea. What you apply in the problem is for you to decide! By the way, it should be b_{sr}I not b_{k}I in the last equation on that page.

Sept 9 Assignment 1 is ready. The following constraint is added to P2: Your implementation of KrylovProd should not require any additional 2-dimensional arrays. Exploit the fact that T=M'*M is symmetric and Toeplitz. (see section 4.7.) 

Meeting Times: MWF 11:15-12:05, Hollister 306

Instructor:  Professor Charles Van Loan, 4130 Upson Hall, 255-5418, cv@cs.cornell.edu . There are walk-in office hours.

TA: Siddharth Alexander, 255-4195, 657 Rhodes,  alexande@cam.cornell.edu.Ofice hours = Tuesday 10-11 and Thursday 1:30-2:30.

Text: Matrix Computations, 3rd Edition by G.H. Golub and  C. Van Loan.

Grading: Six Matlab assignments (40%), Midterm (30%), and a Final Exam (30%).

 Top