So, in class so far we’ve learned about naive Gaussian Elimination, which doesn’t work if the rows are arranged badly. Section 7.2 explains a way to fix this problem: pivoting, which is a process to order the rows so that none of the coefficients on the diagonal (pivot elements) of the matrix are 0 when it’s time to reduce with them (the matrix is degenerate if this happens). Pivoting turns out to have high overhead, especially complete pivoting, though complete pivoting pretty much isn’t used. The book explains partial pivoting, which takes less work and seems to be good enough in practice. Well, I’m sure everyone reading either knows this already or will soon enough, so it’s time to get to the point of this post: pivoting makes algorithms complex and can be eliminated with randomization.

Randomizing means that instead of performing Gaussian Elimination on nonsingular n x n matrix A, Gaussian Elimination can be done on UAV, where U and V are nonsingular n x n random matrices. This transformation must accomplish these 4 things in order to replace/be better than pivoting:

1. The result of the randomization must be Gauss eliminable
2. The cost must be reasonable
3. The process should be easily invertible
4. Roundoff errors must be acceptable

A transformation that satisfies these goals is called the Random Butterfly Transform. It uses random matrices that can be expressed as a product of butterfly matrices. You can read more about butterfly matrices and randomization and how they work here:

http://www.cs.ucla.edu/~stott/ge/

D. Stott Parker in the first of these papers claimed that randomization was suited for high performance machines, put since it was written in 1995, what does “high performance” then refer to anyway?

Also… I hope “between the date in the second column and the date in the
third column” is inclusive.