Numerically Safe Gaussian Elimination with No Pivoting
Numerically Safe Gaussian Elimination with No Pivoting
复制标题
无旋转的数值安全高斯消去法
DOI：
10.1016/j.laa.2017.04.007
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Liang Zhao
中科院分区：
文献类型：
--
作者：
V. Pan;Liang Zhao
没有中心的高斯消去法和块高斯消去法是通常的但通信密集型的部分中心1的高斯消去法的有吸引力的替代方案，只要计算安全和数值安全地进行，即既不会遇到除以0的问题，也不会遇到数值问题。从经验上看，GENP的安全性和数值安全性在许多论文中都得到了一致的观察，其中输入矩阵是通过特别选择的各种结构乘数进行预处理的。我们的这篇论文为这一经验观察提供了缺失的正式支持，并解释了为什么到目前为止它是难以捉摸的。也就是说，我们证明了尽管GENP使用了一些著名的和经过良好测试的结构化乘子进行了预处理，但是对于一类特定的输入矩阵，GENP和BGE对于用任何非奇异且条件良好的乘子进行了预处理的平均输入矩阵是安全的和数值安全的。这应该会鼓励人们寻找稀疏和结构化的乘数，我们列出并测试了其中的一些新类别。我们还寻求普遍(即，对于所有输入矩阵)支持(I)概率为1的安全GENP和BGE和/或(Ii)概率接近于1的数值安全的GENP和BGE的随机化预处理。我们使用高斯结构乘子实现目标(I)，使用高斯非结构乘子实现目标(Ii)，或者使用高斯结构增强。我们不断地用我们对基准投入的GENP测试来确认所有这些正式结果。我们已经将我们的方法扩展到其他基本矩阵计算，并继续进行进一步的扩展。
Gaussian elimination with no pivotingandblock Gaussian eliminationare attractive alternatives to the customary but communication intensiveGaussian elimination with partial pivoting1provided that the computations proceedsafelyandnumerically safely, that is, run into neither division by 0 nor numerical problems. Empirically, safety and numerical safety of GENP have been consistently observed in a number of papers where an input matrix was pre-processed with various structured multipliers chosen ad hoc. Our present paper provides missing formal support for this empirical observation and explains why it was elusive so far. Namely we prove that GENP is numerically unsafe for a specific class of input matrices in spite of its pre-processing with some well-known and well-tested structured multipliers, but we also prove that GENP and BGE are safe and numerically safe for the average input matrix pre-processed with any nonsingular and well-conditioned multiplier. This should embolden search for sparse and structured multipliers, and we list and test some new classes of them. We also seek randomized pre-processing that universally (that is, for all input matrices) supports (i) safe GENP and BGE with probability 1 and/or (ii) numerically safe GENP and BGE with a probability close to 1. We achieve goal (i) with a Gaussian structured multiplier and goal (ii) with a Gaussian unstructured multiplier and alternatively with Gaussian structured augmentation. We consistently confirm all these formal results with our tests of GENP for benchmark inputs. We have extended our approach to other fundamental matrix computations and keep working on further extensions.