BAP: Lecture 5 (Feb 26, 2002)

The notes for this lecture are available in
In today's lecture, we finished our examination of the smoothed complexity of Gaussian Elimination without pivoting. The point of the analysis is that typically one doesn't need to carry out the calculations in many bits of precision.

We then compared with with some experimental data of what happens with partial pivoting.

Get the code you need at the BAP matlab code directory.

We first generated a matrix for which partial pivoting does poorly: 

a = kahan2(25);
[l,u] = lu(a);
max(max(abs(u)))
We then perturbed this matrix, and saw that it was much better 
ap = a + randn(25)/1000;
[l,u] = lu(a);
max(max(abs(u)))
We then tried this many many times, and tablulated the results. Note that v(i) is the number of matrices for which max(max(abs(u))) > 300*i. 
ppCond;
plot(300*[1:100],sqrt(log(v)));
If you want to look at the data which I generated (and saved), try 
load ppDat;
plot(300*[1:100],sqrt(log(v)));