Lab assignment 2: Due Friday March 2, 18:00 EST

In this assignment, we will do an experimental study of the growth factor for Gaussian elimination with partial pivoting. Given the factorization $PA=LU$, define the growth factor by $$ g(A) = \frac{\max_{i,j}|u_{ij}|}{\max_{i,j}|a_{ij}|} , $$ where $u_{ij}$ and $a_{ij}$ are the elements of $U$ and $A$, respectively.
  1. A relevant paper is L.N. Trefethen and R.S. Schreiber. Average-case stability of Gaussian elimination. Please read this paper in sufficient detail to understand the main points.
  2. Write a function that takes $n$ as its parameter and generates an $n\times n$ matrix, whose entries are random numbers uniformly distributed in $[-1,1]$.
  3. Implement Gaussian elimination with partial pivoting, and test it on a number of cases to be sure of its correctness.
  4. Plot the growth factor against the matrix size, in logarithmic scale, where the matrices are generated as in (a). The sample of matrices should be large enough to be a good representative of random matrices with $n$ ranging between, say $10$ and $1000$ (larger sizes are welcome, if it does not take too long). In particular, for each $n$, one should experiment on a generous number of matrices. From the experimental plot, estimate the power $\alpha$ in the assumed dependence $g\approx cn^\alpha$, where $g$ is the growth factor, $n$ is the matrix size, and $c$ is a constant. Compare this with the worst case scenario $g\approx2^n$.
  5. Now we study the probability distribution of the growth factor for a fixed $n$. Fix $n$, say $n=10$ or $n=16$, and generate an abundant number of random matrices, as in (a), to measure their growth factors. Then by subdividing the value-space of the growth factors into small subintervals of equal length, and by counting the number of matrices with growth factor lying in each of those subintervals, produce an approximation of the probability density function of the growth factor (the usual "histogram" technique). Plot it against the growth factor value, with the vertical axis in logarithmic scale. Make a conjecture on how the probability density decays as the growth factor becomes large. Note that the number of matrices and the length of the subintervals should be so that most of the subintervals individually contain a large number of matrices, and that there are enough subintervals to give a meaningful approximation of the probability density function (i.e., the width of bars in the histogram must be small, but most of the bars must still include a large number of cases). Repeat the experiment for several values of $n$, say $n=20, 40, 80$, or $n=32, 64, 128$.
  6. Repeat the preceding 2 items for matrices whose entries are random numbers with a normal distribution. Pick the parameters ($\mu$ and $\sigma$) at your convenience.

How and what to submit

Please submit a link to your Jupyter notebook on GitHub by email, before Friday March 2, 18:00 EST. The subject line of the email should be: