Homework 8.

Assigned: Mon Nov 1. Due: Mon Nov 8, at midnight

As we saw in class, MATLAB has a convenient sparse matrix data structure (type "help sparse") that allows the built-in matrix factorizations LU, QR and Cholesky to be computed efficiently when the data matrix is sparse. A particularly common type of sparsity is band structure. A matrix has bandwidth 2p + 1 if A(i,j) = 0 when |i-j| > p . Assume that A is square (m by m).

  1. (See also Exercise 20.2 in text.) Assuming no pivoting takes place in the factorization A = LU, what are the band structures of L and U when A has bandwidth 2p+1? Prove your answer, and verify it experimentally by constructing a random band matrix in Matlab (use "help triu" and "help tril") and "spying" the factors (see spy_lu.m). Since this question assumes there is NO pivoting, add a (large enough) multiple of the identity matrix to your random band matrix to ensure that pivoting does not occur (i.e., P is the identity matrix).
  2. (See also Exercise 21.2 in text.) Supposing that pivoting MIGHT take place, so that the factorization is PA = LU. Then what are the band structures of L and U when A has bandwidth 2p+1? Again prove your answer, and verify it experimentally by "spying" the factors. This time, use an example where pivoting DOES occur (P is NOT the identity matrix), and look at the factors where L is really (not just psychologically) lower triangular, by computing them from [L,U,P] = lu(A) (as is done by spy_lu.m).
  3. Suppose you wanted to design a special data structure for band matrices (not general sparse) matrices. How would you suggest storing the data?
  4. Approximately how many flops (floating point operations) are required to compute the L and U factors of a band matrix using either your special data structure or Matlab's built-in sparse data structure, in terms of the dimension m and half-band-width p? Don't try to include non-floating-point operations such as indexing. Assume for this part that no pivoting takes place, and that m is much larger than p.
  5. How does your answer to the previous question change if pivoting takes place? Assume the worst case for simplicity.