DISTRIBUTION OF THE NUMBER OF PIVOTS NEEDED USING GAUSSIANELIMINATION WITH PARTIAL PIVOTING ON RANDOM MATRICES

• 成果类型: Article
• 署名作者: Peca-Medlin, John
• 署名单位: University of Arizona
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP2023
• 发表日期: 2024
• 页码: 2294-2325
• 关键词: circular law; UNIVERSALITY

摘要

Gaussian elimination with partial pivoting (GEPP) is a widely usedmethod to solve dense linear systems. Each GEPP step uses a row transposi-tion pivot movement if needed to ensure the leading pivot entry is maximalin magnitude for the leading column of the remaining untriangularized sub-system. We will use theoretical and numerical approaches to study how oftenthis pivot movement is needed. We provide full distributional descriptions forthe number of pivot movements needed using GEPP using particular Haarrandom ensembles as well as compare these models to other common trans-formations from randomized numerical linear algebra. Additionally, we in-troduce new random ensembles with fixed pivot movement counts and fixedsparsity,alpha. Experiments estimating the empirical spectral density (ESD) ofthese random ensembles leads to a new conjecture on a universality class ofrandom matrices with fixed sparsity whose scaled ESD converges to a mea-sure on the complex unit disk that depends on alpha and is an interpolation of theuniform measure on the unit disk and the Dirac measure at the origin