Random butterfly matrices and growth factors
The recursive structure of butterfly matrices has been exploited to accelerate common methods in computational linear algebra. Recent interest in butterfly matrices has spiked in the machine learning and AI communities, where butterfly structures have been integrated into architecture used in learning fast solvers for large linear systems and in image recognition. These growing applications have often eclipsed the mathematical understanding on how or why butterfly matrices are able to accomplish these tasks. I will focus on the particular application to remove the need for pivoting in Gaussian elimination. I will explore the impact of preconditioning a linear system by butterfly matrices on the growth factor, which controls the numerical stability of Gaussian elimination. These results will be compared to other common methods found in randomized linear algebra.