Homework assignments for Math 221, Spring 2020

Homework answers will be posted at bcourses.berkeley.edu.
  • Homework #1 due Tuesday Jan 28
  • From Chapter 1: 2, 4, 10, 11
  • Extra credit from Chapter 1: 18
    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 Tuesday, Feb 4
  • 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 Tuesday, Feb 11, at 23:59 Pacific time
  • 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 Tuesday, Feb 18, 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.

  • Homework #5 due Tuesday, Feb 25, 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.
  • There are many more ways to store and operate on sparse matrices than the ones we are exploring in this question. In fact, the best (fastest) data structure and algorithm can depend in complicated ways on both the matrix and the computer. For more information about some systems that try to automatically pick the best data structure and algorithm for a particular matrix on a particular computer, see the webpages for the OSKI and pOSKI projects. (OSKI stands for Optimized Sparse Kernel Interface, and completely coincidentally is also the name of the Cal Bear mascot :) .)
  • Question 2: In class we defined a weighted undirected graph G=(V,E,W) where V is the set of vertices, E the set of edges and W is the set of edge weights. Now we define a directed graph, where each edge (u,v) is considered to be directed from u to v (think of an arrow pointing from vertex u to vextex v). Since (u,v) and (v,u) are now different, we see that there is a natural correspondence between a general, possibly unsymmetric square matrix A and a graph G=(V,E,W) with
  • one vertex for each row/column
  • an edge (i,j) if A(i,j) is nonzero, with weight A(i,j)

    • Recall also that a path of length k from vertex v(1) to vertex v(k+1) in a graph is a set of k edges that connect end to end
  • (v(1),v(2)), (v(2),v(3)) ,..., (v(k),v(k+1))
    • where, for a directed graph, the directions of the edges have to match as shown.
    Now consider two nxn matrices and their associated graphs on the same set of vertices:
  • A_r and G_r = (V, E_r, W_r) (the "red" edges)
  • A_b and G_b = (V, E_b, W_b) (the "blue" edges)
    • with all edges weights equal to 1; i.e. the nonzeros entries of A_r and A_b are all ones.
    Show that the number of paths consisting of one red edge followed by one blue edge connecting vertex i to vertex j is the (i,j) entry of A_r * A_b. In other words, multiplying matrices counts paths. This observation underlies some fast algorithms for graphs, such as the Floyd-Warshall Algorithm for All-Pairs-Shortest-Paths.
  • Question 3.1
  • Question 3.3 (parts 1, 2 and 3)
  • Question 3.4 (just the normal equations part)

  • Homework #6, Due Tuesday, Mar 3, at 23:59 Pacific Time
  • Questions 3.11, 3.12, 3.13, 3.14, 3.18
  • Extra Credit: Question 3.17

  • Project Proposals due Tuesday, Mar 10, in class

  • Homework #7, Due Friday, Mar 13 at 23:59 Pacific Time
  • Questions 4.2, 4.4, 4.5, 4.6, 4.11, 4.13

  • Homework #8 due Wednesday, Mar 18 Friday, Mar 20 at 23:59 Pacific Time
  • Question 4.14, just matrices 1, 3 and 6
  • Question 4.16, just the mathematical questions in the second paragraph, no programming
  • Work on your class projects, feedback to be provided

  • Homework #9 due Friday Apr 3 at 23:59 Pacific Time
  • Question 5.4 (Part 1 only)
  • Question 5.5
  • Question 5.14
  • Question 5.18
  • Work on your class projects!

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

  • Homework #11 due Friday, Apr 17 at 23:59 Pacific Time (Corrected 4/12 at 8:45am)
  • 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?
  • 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))?
  • 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 Apr 24 at 23:59 Pacific Time
  • Question 6.15, parts 1 and 2
  • Extra Credit: Question 6.15, part 3
  • Keep working on your class projects!
  • Homework #13 due Friday May 1 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!