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).
- (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).
- (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).
- Suppose you wanted to design a special data structure for band matrices
(not general sparse) matrices. How would you suggest storing the data?
- 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.
- How does your answer to the previous question change if pivoting takes
place? Assume the worst case for simplicity.