Advanced Linear Algebra for Computing Numerical Analysis: Linear Algebra Spring 2021
Take Home Final
Name: EID:
This is an open notes exam. You are allowed to consult external re- sources.
Please acknowledge the following (initial each)
I will not and have not consulted any individuals (other than course staff) regarding this exam.
The answers to this exam are wholy my own.
I will not share this exam or any information about this exam with any other person in the class nor outside the class other than the teaching staff. This includes sharing the exam with anyone (other than course staff) at anytime, even after the class has completed, for all of eternity, and beyond, unless explicit permission has been granted by Maggie Myers or Robert van de Geijn
Signed: Date:
Don’t Panic!
The instructions in this document are a lot longer than the actual solution should be. You can take as much time until the due time (May 12, 11:59pm Texas Time ) as you wish, and you do not need to finish in one “sitting.”
You do NOT need to typeset solutions with LaTeX (handwritten is fine).
Programming Help, Add QQ: 749389476
1. In this first problem, you will implement, in Matlab, a number of functions for computing the SVD of a square matrix. There are three matlab files you will download from canvas:
• test_svd.m
• Implicit_bidiag_QR.m
• Implicit_bidiag_QR_SVD.m
You can find these at
• http://www.cs.utexas.edu/users/rvdg/ALA_Final/test_SVD.m
• http://www.cs.utexas.edu/users/rvdg/ALA_Final/Implicit_bidiag_QR.m
• http://www.cs.utexas.edu/users/rvdg/ALA_Final/Implicit_bidiag_QR_SVD.m
Here is your assignment:
(a) Implement the reduction to bidiagonal form, BiRed discussed in ”Ponder This 11.2.3.3”. All you need to implement and test this function is discussed in that exercise.
What to turn in (on Canvas): BiRed.m (there may be additional instructions on what else to upload to make it easier for the grader.)
(b) Once you have this, you can also test it with the file test_SVD.m, which also will help you test other components of this first part of the exam. In particular, in test_SVD.m, find the section where you are asked to compute UA and VA such that A = UABVAT , where B is the bidiagonal matrix computed by BiRed. In the script, enter the lines needed to compute UA and VA. (You will eventually upload test_SVD.m, but only after you complete other parts of it as well.) Note: you will want use routines you wrote in Week 3 for computing Q from the Householder transformations.
(c) Next, you are to implement a function Bidiag_Francis_Step that implements the in- troduction of the bulge into the bidiagonal matrix and the chasing out of that bulge. You will again use test_SVD.m to test your implementation. In test_SVD.m, there are hints as to how to do the implementation so that you slowly make it more sophisticated. Once completed, you upload Bidiag_Francis_Step.m to Canvas.
Note: It would be tempting to use the Francis step routine from Week 10. However, that routine is greatly complicated by the fact that only the lower triangular part of the tridiagonal matrix T is to be updated. Here, you are allowed to change the entire matrix and hence you don’t have to extract parts of the matrix, make them symmetric, compute, and then reinsert. If you do go that route (using the routine from Assignment 10 as your template), you will greatly complicate your implementation and extend the amount of time to do this part of the final by many, many hours.
Do notice that you will be partially graded on how many computations you perform. Do not compute unnecessarily with entries that are zeroes!
Matlab syntax: A( 2:3,4:6) in Matlab refers to the submatrix with entries (2,4), (2,5), (2,6) for the first row and (3,4), (3,5), (3,6) for the second row (starting indexing at 1, as Matlab does). To address, for example, the entire second column, you use A(:,2). Hopefully you get the idea how indexing in Matlab works. (There is no particular meaning to this example. Just meant to illustrate Matlab syntax.)
Code Help, Add WeChat: cstutorcs
(d) Next, you copy Bidiag_Francis_Step.m into Bidiag_Francis_Step_U_V.m and modify
this copy so that you also update UA and VA by applying the Givens’ rotations, thus accu- mulating the U and V such that A = U ΣV T . Look at how Bidiag_Francis_Step_Update_U_V is called in Implicit_bidiag_QR_SVD.m to see how your function should order its inputs
and outputs There are additional instructions in test_SVD.m. When finished, upload Bidiag_Francis_Step_Update_U_V.m to Canvas.
Make sure you understand how Givens’ rotation have to be applied to what columns of UA and VA. This is where in the past a lot of people got confused and spent a lot of time.
(e) In the end, you will also want to upload your final test_SVD.m to Canvas.
While initially you will want to just get it running, in the end you need to make sure that operating on the bidiagonal matrix is only O(n) and updating UA and VA is only O(n2) per call to the routine that implements the Francis step.
To help you out, I will post some output that I get if I print out intermediate results on the edX discussion board.
2. The second part of the exam is an exploration of some of the techniques behind the Method of Multiple Relative Robust Representations (MRRR), which is mentioned in the enrichment in Unit 10.4.5. This exercise requires you to go through a somewhat lengthy document that gives context. Don’t feel intimidated: we walk you through the steps.
Use the document in
• http://www.cs.utexas.edu/users/rvdg/ALA_Final/TwistedFactorization.pdf.
While you should do all exercises in that document (we give answers to those that are not graded as part of the exam), you will be graded on
(a) Exercise 5.2. (b) Exercise 6.1. (c) Exercise 7.1.
Upload a PDF with these answers to both Canvas and Gradescope.
CS Help, Email: tutorcs@163.com