@booklet {,
	title = {Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes},
	year = {2023},
	month = {2023-12},
	publisher = {arXiv},
	abstract = {Parker and L{\^e} introduced random butterfly transforms (RBTs) as a preprocessing technique to replace pivoting in dense LU factorization. Unfortunately, their FFT-like recursive structure restricts the dimensions of the matrix. Furthermore, on multi-node systems, efficient management of the communication overheads restricts the matrix{\textquoteright}s distribution even more. To remove these limitations, we have generalized the RBT to arbitrary matrix sizes by truncating the dimensions of each layer in the transform. We expanded Parker{\textquoteright}s theoretical analysis to generalized RBT, specifically that in exact arithmetic, Gaussian elimination with no pivoting will succeed with probability 1 after transforming a matrix with full-depth RBTs. Furthermore, we experimentally show that these generalized transforms improve performance over Parker{\textquoteright}s formulation by up to 62\% while retaining the ability to replace pivoting. This generalized RBT is available in the SLATE numerical software library.},
	url = {https://arxiv.org/abs/2312.09376},
	author = {Neil Lindquist and Piotr Luszczek and Jack Dongarra}
}
