Homework assignments for Math 221, Fall 2020

Homework should be turned in at bcourses.berkeley.edu. Homework answers will also be posted there.
  • Homework #1 due Friday Sep 4, by 11:59pm
  • From Chapter 1: 2, 4, 10, 11
  • Extra credit from Chapter 1: 18
    See List of Errata for the Textbook
    Hint: Prove the following Lemma: If floating point numbers x and y satisfy 2*y >= x >= y >= 0, then fl(x-y) = x-y, i.e. x-y is an exact floating point number.

  • Homework #2 due Friday, Sep 11, by 11:59pm
    Again, please check List of Errata for the Textbook
  • From Chapter 1: 3, 5, 7, 13, 14, 15
  • From Chapter 1: 16 (parts 1, 2, 4, 5, 6, 8, 10)
  • From Chapter 3: 9
  • Extra Credit: From Chapter 1: 20

  • Homework #3 due Friday, Sep 18, by 11:59pm
  • Question 2.13, parts 1 and 2
  • Consider the problem of solving L*X = B where B is a given n-by-n matrix, L is a given n-by-n nonsingular lower triangular matrix, and X is an unknown n-by-n matrix.
  • Write down the simplest algorithm you can, and count the flops.
  • Analogous to the blocked matrix-multiplication algorithm presented in class, write down a blocked version of this algorithm, and analyze the number of words moved; can you make it move as few words as matrix-multiply (in the Big-Oh sense)?
  • Does it satisfy the same backward error analysis as the simple algorithm (as in Q. 1.11)?
  • Analogous to the recursive matrix-multiplication algorithm presented in class, write down a recursive version of this algorithm, and analyze the number of words moved; can you make it move as few words as matrix-multiply (in the Big-Oh sense)?
  • Does it satisfy the same backward error analysis as the simple algorithm (as in Q. 1.11)?
  • (Extra credit) Show that you can't communicate fewer words to solve L*X=B than in matrix-multiply, namely Omega(n^3/sqrt(M)). Hint: Show that any routine for solving L*X=B can be used to do matrix-multiplication (of slightly smaller matrices), so the lower bound for matrix-multiplication applies (perhaps with a smaller constant, all hidden in the Big-Omega notation).

  • Homework #4 due Friday, Sep 25, at 23:59 Pacific time
  • Questions 2.2, 2.7
  • Question 2.8. Hint: Write a matlab program to generate random examples according to the hint in the book, and compute the backward error of the solutions computed by Cramer's Rule.
  • Question 2.12
  • Question 2.19. Hint for Part 1: To show A is nonsingular, we need to show that if the column vector x is nonzero, so is x'*A. Suppose x(i) is the largest component of x in absolute value. What can you say about the i-th component of x'*A?
  • Extra Credit: Analyze the cost of recursive LU (RLU) presented in lecture, deriving and solving recurrences for A(n) = #arithmetic operations and W(n) = #words moved.
  • Extra Credit: Derive a recursive algorithms for Cholesky, and similarly derive and solve recurrences for A(n) = #arithmetic operations and W(n) = #words moved.

  • Homework #5 due Friday, Oct 2, at 23:59 Pacific time
  • Question 1, Part 1: Consider an n by m matrix A in Compressed Sparse Row (CSR) data format: if A has nnz nonzero entries then
  • val(1:nnz) contains the nonzero entries packed row by row, from left to right in each row
  • colindex(1:nnz) contains the column index of each nonzero entry, i.e. val(i) is in column colindex(i) of A
  • rowbegin(1:n+1) points to where each row begins: the nonzeros of row j are contained in val( rowbegin(j) : rowbegin(j+1)-1 )

    • Write, in Matlab, or your preferred language, explicit loops to compute the matrix-vector product y = A*x, where x and y are (dense) vectors of length m and n. (In other words, don't use any of Matlab's built in function for sparse matrices, though you may use notation like sum(a(i:j).*b(i:j)) or (a(i:j))'*b(i:j) for the dot product of parts of two column vectors.) Test it by running it on a few (small) sparse matrices, and comparing to Matlab's built-in routine for y=A*x. Make sure to test a matrix A with one or more zero rows. (Matlab has a built in sparse-matrix-vector-multiplication routine, that is called when doing A*x in Matlab on a matrix A that has been declared "sparse." But the point of this question is to understand CSR format, which is very commonly used.)
  • Question 1, Part 2: Now suppose that A is stored in Compressed Sparse Column (CSC) data format; this means storing A^T in CSR. Again write in Matlab explicit loops to compute y = A*x.
  • Question 3.1
  • Question 3.3, parts 1, 2 and 3
  • Question 3.4, just the normal equations part
  • Question 3.18
  • Extra Credit: Question 3.17

  • Homework #6 due Friday, Oct 9, at 23:59 Pacific time
  • Questions 3.11, 3.12, 3.13, 3.14
  • One of the inventors of the Moore-Penrose pseudo-inverse just won the Nobel Prize in Physics this morning (Oct 6), but for something else :) .
  • In lecture, we discussed how to solve the ridge regression problem using both a version of the normal equations, and the SVD. In practice, one may want to solve the same ridge regression problem for several values of the parameter lambda, to choose the best one. The SVD makes it quite cheap to do this, but requires an expensive SVD first. The normal equations require an additional O(n^3) work for each lambda, for Cholesky, which can be much cheaper than initially forming A^T*A for O(m*n^2) if m >> n, but it is not backward stable. Show how to use QR to solve ridge regression for an additional cost of O(n^3) per lambda. Hint: use Givens rotations to update R.
  • Work on your class project proposals!

  • Homework #7 due Friday, Oct 16, at 23:59 Pacific time, Modified 10/13, 6am
  • Questions 4.1, 4.8

  • Homework #8 due Friday, Oct 23, at 23:59 Pacific time,
  • Questions 4.2, 4.4, 4.5, 4.6, 4.11, 4.13

  • Homework #9 due Friday, Oct 30, at 23:59 Pacific time,
  • Questions 5.4 (Part 1 only), 5.5, 5.14, 5.18
  • Work on your class projects!

  • Homework #10 due Friday Nov 6 at 23:59 Pacific Time
  • Question 6.1
  • Question 6.4 (only need to do parts not done in class)
  • Question 6.5 (see items on pages 357 and 358 of errata)
  • Work on your class projects!


  • Homework #11 due Friday, Nov 13 at 23:59 Pacific Time, Modified Nov 9, 6am
  • Consider the slight variation on the 2D Model Problem, gotten by discretizing the slightly different PDE
    -a * d^2 v(x,y)/dx^2 - b * d^2 v(x,y)/dy^2 = f(x,y)
    where a and b are some positive constants. Briefly justify your answers to the following questions. (Hint: Use Matlab to confirm that your answers are correct for small examples.)
  • Using Kronecker product notation, write down the matrix; call it T(a,b).
  • Write down explicit formulas for the eigenvalues and eigenvectors of T(a,b), again using Kronecker product notation. Is T(a,b) symmetric and positive definite? What is its 2-norm condition number?
  • Does Jacobi's method converge for T(a,b)? What is rho(R_J), the spectral radius of the Jacobi iteration matrix R_J?
  • Repeat the last question for the 3D problem gotten by discretizing
    -a * d^2 v(x,y,z)/dx^2 - b * d^2 v(x,y,z)/dy^2 - c * d^2 v(x,y,z)/dz^2 = f(x,y,z)
    where a, b and c are some positive constants.
  • Extra Credit: Question 6.10

  • Homework #12 due Friday, Nov 20 at 23:59 Pacific Time
  • Consider the same slight variation on the 2D Model Problem, T(a,b), defined in last week's homework.
  • Is there an ordering of the equations and unknowns for which SOR(w) converges, for T(a,b), for some values of w? What ordering, and which values of w?
  • What value w_opt minimizes rho(R_SOR(w))? What is the value of rho(R_SOR(w_opt))?
  • Question 6.15, parts 1 and 2
  • Extra Credit: Question 6.15, part 3
  • Keep working on your class projects!

  • There will be no homework due during the week of Thanksgiving, Nov 27. The last homework assignment of the semester will be due Friday, Dec 4.

  • Homework #13 due Friday, Dec 4, at 23:59 Pacific Time
  • Question 6.14 (note the correction on page 317 of the text)
  • Extra Credit: Question 6.7 (note the correction on page 296 of the text)
  • Keep working on your class projects!