论文标题
随机蝴蝶矩阵的生长因子和避免枢转的稳定性
Growth factors of random butterfly matrices and the stability of avoiding pivoting
论文作者
论文摘要
帕克（Parker）于1995年引入了随机蝴蝶矩阵，以消除使用高斯消除时旋转的需求。蝴蝶矩阵的日益增长的应用通常使人们对蝴蝶矩阵如何或为什么能够完成这些给定的任务的数学理解。为了帮助开始使用理论和数值方法缩小这一差距，我们探讨了蝴蝶矩阵对线性系统进行预处理的影响。将这些结果与在随机数值线性代数中发现的其他常见方法进行比较。在这些实验中，我们显示使用蝴蝶矩阵的预处理对大型生长因子的影响比其他常见的预处理更大，并且对最小生长因子系统的增加较小。此外，我们能够确定随机蝴蝶基质子类的生长因子的完整分布。 Trefethen和Schreiber与随机生长因子的分布有关的先前结果仅限于Ginibre矩阵第一刻的经验估计。
Random butterfly matrices were introduced by Parker in 1995 to remove the need for pivoting when using Gaussian elimination. The growing applications of butterfly matrices have often eclipsed the mathematical understanding of how or why butterfly matrices are able to accomplish these given tasks. To help begin to close this gap using theoretical and numerical approaches, we explore the impact on the growth factor of preconditioning a linear system by butterfly matrices. These results are compared to other common methods found in randomized numerical linear algebra. In these experiments, we show preconditioning using butterfly matrices has a more significant dampening impact on large growth factors than other common preconditioners and a smaller increase to minimal growth factor systems. Moreover, we are able to determine the full distribution of the growth factors for a subclass of random butterfly matrices. Previous results by Trefethen and Schreiber relating to the distribution of random growth factors were limited to empirical estimates of the first moment for Ginibre matrices.
