@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}
}
@conference {,
	title = {Using Additive Modifications in LU Factorization Instead of Pivoting},
	booktitle = {37th ACM International Conference on Supercomputing (ICS{\textquoteright}23)},
	year = {2023},
	month = {2023-06},
	publisher = {ACM},
	organization = {ACM},
	address = {Orlando, FL},
	doi = {10.1145/3577193.3593731},
	author = {Neil Lindquist and Piotr Luszczek and Jack Dongarra}
}
@conference {,
	title = {Threshold Pivoting for Dense LU Factorization},
	booktitle = {ScalAH22: 13th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems },
	year = {2022},
	month = {2022-11},
	publisher = {IEEE},
	organization = {IEEE},
	address = {Dallas, Texas},
	abstract = {LU factorization is a key approach for solving large, dense systems of linear equations. Partial row pivoting is commonly used to ensure numerical stability; however, the data movement needed for the row interchanges can reduce performance. To improve this, we propose using threshold pivoting to find pivots almost as good as those selected by partial pivoting but that result in less data movement. Our theoretical analysis bounds the element growth similarly to partial pivoting; however, it also shows that the growth of threshold pivoting for a given matrix cannot be bounded by that of partial pivoting and vice versa. Additionally, we experimentally tested the approach on the Summit supercomputer. Threshold pivoting improved performance by up to 32\% without a significant effect on accuracy. For a more aggressive configuration with up to one digit of accuracy lost, the improvement was as high as 44\%.},
	doi = {10.1109/ScalAH56622.2022.00010},
	author = {Neil Lindquist and Mark Gates and Piotr Luszczek and Jack Dongarra}
}
@article {,
	title = {Accelerating Restarted GMRES with Mixed Precision Arithmetic},
	journal = {IEEE Transactions on Parallel and Distributed Systems},
	year = {2021},
	month = {2021-06},
	abstract = {The generalized minimum residual method (GMRES) is a commonly used iterative Krylov solver for sparse, non-symmetric systems of linear equations. Like other iterative solvers, data movement dominates its run time. To improve this performance, we propose running GMRES in reduced precision with key operations remaining in full precision. Additionally, we provide theoretical results linking the convergence of finite precision GMRES with classical Gram-Schmidt with reorthogonalization (CGSR) and its infinite precision counterpart which helps justify the convergence of this method to double-precision accuracy. We tested the mixed-precision approach with a variety of matrices and preconditioners on a GPU-accelerated node. Excluding the incomplete LU factorization without fill in (ILU(0)) preconditioner, we achieved average speedups ranging from 8 to 61 percent relative to comparable double-precision implementations, with the simpler preconditioners achieving the higher speedups.
},
	keywords = {Convergence, Error correction, iterative methods, Kernel, linear systems, Stability analysis},
	doi = {10.1109/TPDS.2021.3090757},
	author = {Neil Lindquist and Piotr Luszczek and Jack Dongarra}
}
@conference {1482,
	title = {Improving the Performance of the GMRES Method using Mixed-Precision Techniques},
	booktitle = {Smoky Mountains Computational Sciences \& Engineering Conference (SMC2020)},
	year = {2020},
	month = {2020-08},
	abstract = {The GMRES method is used to solve sparse, non-symmetric systems of linear equations arising from many scientific applications. The solver performance within a single node is memory bound, due to the low arithmetic intensity of its computational kernels. To reduce the amount of data movement, and thus, to improve performance, we investigated the effect of using a mix of single and double precision while retaining double-precision accuracy. Previous efforts have explored reduced precision in the preconditioner, but the use of reduced precision in the solver itself has received limited attention. We found that GMRES only needs double precision in computing the residual and updating the approximate solution to achieve double-precision accuracy, although it must restart after each improvement of single-precision accuracy. This finding holds for the tested orthogonalization schemes: Modified Gram-Schmidt (MGS) and Classical Gram-Schmidt with Re-orthogonalization (CGSR). Furthermore, our mixed-precision GMRES, when restarted at least once, performed 19\% and 24\% faster on average than double-precision GMRES for MGS and CGSR, respectively. Our implementation uses generic programming techniques to ease the burden of coding implementations for different data types. Our use of the Kokkos library allowed us to exploit parallelism and optimize data management. Additionally, KokkosKernels was used when producing performance results. In conclusion, using a mix of single and double precision in GMRES can improve performance while retaining double-precision accuracy.},
	keywords = {Kokkos, Krylov subspace methods, linear algebra, mixed precision},
	author = {Neil Lindquist and Piotr Luszczek and Jack Dongarra}
}
@conference {,
	title = {Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques},
	booktitle = {2020 IEEE/ACM 11th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA)},
	year = {2020},
	month = {2020-11},
	publisher = {IEEE},
	organization = {IEEE},
	address = {Atlanta, GA},
	abstract = {Gaussian elimination is a key technique for solving dense, non-symmetric systems of linear equations. Pivoting is used to ensure numerical stability but can introduce significant overheads. We propose replacing pivoting with recursive butterfly transforms (RBTs) and iterative refinement. RBTs use an FFT-like structure and randomized elements to provide an efficient, two-sided preconditioner for factoring. This approach was implemented and tested using Software for Linear Algebra Targeting Exascale (SLATE). In numerical experiments, our implementation was more robust than Gaussian elimination with no pivoting (GENP) but failed to solve all the problems solvable with Gaussian elimination with partial pivoting (GEPP). Furthermore, the proposed solver was able to outperform GEPP when distributed on GPU-accelerated nodes.},
	keywords = {linear systems, Randomized algorithms},
	author = {Neil Lindquist and Piotr Luszczek and Jack Dongarra}
}
@conference {,
	title = {Scalable Data Generation for Evaluating Mixed-Precision Solvers},
	booktitle = {2020 IEEE High Performance Extreme Computing Conference (HPEC)},
	year = {2020},
	month = {2020-09},
	publisher = {IEEE},
	organization = {IEEE},
	address = { Waltham, MA, USA},
	abstract = {We present techniques of generating data for mixed precision solvers that allows to test those solvers in a scalable manner. Our techniques focus on mixed precision hardware and software where both the solver and the hardware can take advantage of mixing multiple floating precision formats. This allows taking advantage of recently released generation of hardware platforms that focus on ML and DNN workloads but can also be utilized for HPC applications if a new breed of algorithms is combined with the custom floating-point formats to deliver performance levels beyond the standard IEEE data types while delivering a comparable accuracy of the results.},
	doi = {https://doi.org/10.1109/HPEC43674.2020.9286145},
	author = {Piotr Luszczek and Yaohung Tsai and Neil Lindquist and Hartwig Anzt and Jack Dongarra}
}
@techreport {,
	title = {A Survey of Numerical Methods Utilizing Mixed Precision Arithmetic},
	journal = {SLATE Working Notes},
	number = {15, ICL-UT-20-08},
	year = {2020},
	month = {2020-07},
	publisher = {University of Tennessee},
	type = {SLATE Working Notes},
	author = {Ahmad Abdelfattah and Hartwig Anzt and Erik Boman and Erin Carson and Terry Cojean and Jack Dongarra and Mark Gates and Thomas Gruetzmacher and Nicholas J. Higham and Sherry Li and Neil Lindquist and Yang Liu and Jennifer Loe and Piotr Luszczek and Pratik Nayak and Sri Pranesh and Siva Rajamanickam and Tobias Ribizel and Barry Smith and Kasia Swirydowicz and Stephen Thomas and Stanimire Tomov and Yaohung Tsai and Ichitaro Yamazaki and Urike Meier Yang}
}
