Homework assignments for Math 221, Fall 2023

Homework should be turned in on gradescope. Homework answers will be posted on bcourses.berkeley.edu.
  • Homework #1 due Monday Sep 4, by 11:59pm (changed 8/29)
  • 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.
  • In the last version of the IEEE 754 Floating Point Standard from 2019, we voted to include a new recommended instruction that implements a single operation performing the computation in this question. The motivation was to support both higher precision arithmetic as described in the question, and reproducibility, i.e. getting the bitwise identical answer no matter the order in which a sum is computed. Here is a short news article about why this is important. Here is a link to work on implementing reproducible dot products, etc., using existing floating point operations predating the latest IEEE 754 standard. Finally, this article describes how to implement reproducible summation both with and without the new operation in the latest IEEE 754 standard.

  • Homework #2 due Monday, 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 Wednesday, Sep 20, by 11:59pm (changed 9/15)
  • 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 Wednesday, Sep 27, by 11:59pm
  • Questions 2.2, 2.6, 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
  • Analyze the cost of recursive LU (RLU) presented in lecture, deriving and solving recurrences for A(n) = #arithmetic operations and W(n) = #words moved.

  • Homework #5 due Wednesday, Oct 4, by 11:59pm
  • 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 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?

  • Homework #6 due Wednesday, Oct 11, by 11:59pm
  • Question 3.1
  • Question 3.3, parts 1, 2 and 3
  • Questions 3.4, 3.7, 3.15
  • Question 3.17, part 1

  • Homework #7 due Wednesday, Oct 18, by 11:59pm
  • Questions 3.11, 3.12, 3.13, 3.14
  • One of the inventors of the Moore-Penrose pseudo-inverse won the Nobel Prize in Physics in 2020, 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.

  • Homework #8 due Wednesday, Oct 25, by 11:59pm
  • Questions 4.1, 4.2, 4.3, 4.4, 4.5

  • Homework #9 due Wednesday, Nov 1, by 11:59pm
  • Questions 4.6, 4.8, 4.11, 4.13

  • Homework #10 due Wednesday, Nov 8, by 11:59pm
  • Questions 5.4 (Part 1 only), 5.5, 5.14, 5.18
  • Work on your class projects!

  • Homework #11 due Wednesday, Nov 15, by 11:59pm
  • 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 #12 due Wednesday, Nov 22 at 23:59 Pacific Time
  • 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 #13 due Wednesday, Nov 29 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!

  • Homework #14 due Wednesday, Dec 6 at 23:59 Pacific Time
  • Question 6.14 (note the correction on page 317 of the text)
  • Keep working on your class projects!