Homework assignments for Math 221, Spring 2016

Homework answers will be posted at bcourses.berkeley.edu.
  • Homework #1 due Monday, Jan 25, Delayed to Wednesday Jan 27
  • 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 Wednesday, Feb 3
  • 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, Feb 10
  • 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, Feb 17
  • 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.
  • Questions 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 Wednesday, Feb 24
  • 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 1, Part 3: Now suppose that A is symmetric, and that only the upper triangle of A is stored in CSR to save space (triu(A,0) in Matlab notation). 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.
  • Question 2, Part 1: 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 2, Part 2: Consider just G_r. Show that the number of paths of length k from vertex i to vertex j in G_r is the (i,j) entry of A_r^k.


  • Homework #6 due Wednesday, Mar 2
  • Question 3.1
  • Question 3.3 (parts 1, 2 and 3)
  • Question 3.4 (just the normal equations part)
  • Questions 3.12, 3.15
  • Extra Credit: Question 3.17


  • Homework #7 due Wednesday, Mar 9
  • Question 3.7, 3.11, 3.13, 3.14, 3.18
  • Work on your class project proposals!

  • Homework #8 due Friday, Mar 18 at 11:59pm
  • Question 4.2, 4.4, 4.5, 4.6, 4.11, 4.13
  • Note the unusual due date. You can either submit your homework by email, or put it in a box outside Eric Hallman's office in 1058 Evans.
  • Work on your class projects!

  • Homework #9 due Wednesday, Mar 23 30
  • 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!

  • Homework #10 due Wednesday, Apr 6
  • Question 5.4 (Part 1 only)
  • Question 5.5
  • Question 5.18
  • Work on your class projects!

  • Homework #11 due Wednesday, Apr 13
  • Questions 6.1, 6.4, 6.5
  • Work on your class projects!

  • Homework #12 due Wednesday, Apr 20 Friday, Apr 22
  • Question 6.10
  • 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.