Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes

Neil Lindquist, Piotr Luszczek, Jack Dongarra

Parker and Lê introduced random butterfly transforms (RBTs) as a preprocessing technique to replace pivoting in dense LU factorization. Unfortunately, their FFT-like recursive stru…