Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.09376 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912068563632128 |
|---|---|
| author | Lindquist, Neil Luszczek, Piotr Dongarra, Jack |
| author_facet | Lindquist, Neil Luszczek, Piotr Dongarra, Jack |
| contents | Parker and Lê 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'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'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's formulation by up to 62\% while retaining the ability to replace pivoting. This generalized RBT is available in the SLATE numerical software library. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_09376 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes Lindquist, Neil Luszczek, Piotr Dongarra, Jack Numerical Analysis 65F05 G.1; G.4 Parker and Lê 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'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'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's formulation by up to 62\% while retaining the ability to replace pivoting. This generalized RBT is available in the SLATE numerical software library. |
| title | Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes |
| topic | Numerical Analysis 65F05 G.1; G.4 |
| url | https://arxiv.org/abs/2312.09376 |