pipette
ENEnglish

Random permutations using GEPP

Kenji Gunawan, John Peca-Medlin, Chenyang Zhong

Preprint

En palabras de los autores

Gaussian elimination with partial pivoting (GEPP) remains the most widely used solver for dense linear systems for . We study the permutation that arises in the GEPP factorization , encoded by the permutation matrix factor . When the input matrix is random, so is . For random scalar butterfly matrices of size (a recursively defined family originally introduced to eliminate the need for pivoting altogether), we give the exact GEPP factorization and fully classify the induced permutation as an element of a -Sylow subgroup of contained in the separable permutations. Moreover, the uniform-angle model induces the uniform distribution on this subgroup. For the GOE, GUE, and iid Bernoulli models, the induced permutation is never exactly uniform for . We give the precise rate of departure from uniformity at the leading pivot for the GOE and GUE, and give evidence that this non-uniformity vanishes asymptotically in the permuton sense. In contrast, for banded random matrices of sublinear bandwidth, including the tridiagonal -Hermite ensembles, the induced permutation converges to the diagonal permuton. We further show that the resulting pivot probabilities are sensitive to implementation choices: standard LAPACK routines compare complex pivot candidates using the rather than norm, changing the GUE(2) pivot probability from to . Together these results establish a new connection between random matrix theory and permutation combinatorics through numerical linear algebra.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Supersedes arXiv:2506.20470 and incorporates part of arXiv:2410.20952, with substantially expanded results. First of three articles that together will supersede arXiv:2410.20952