Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
复制标题
使用随机蝴蝶变换避免稀疏直接方法中的旋转
DOI：
10.1007/978-3-319-17353-5_12
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
François
中科院分区：
文献类型：
--
作者：
M. Baboulin;X. Li;François
本文利用LU分解的直接方法研究了稀疏线性系统的解。除非矩阵是正定的，否则通常需要数值枢轴来保证稳定性，特别是在稀疏情况下，实现它的成本很高。随机蝴蝶变换（RBT）技术提供了一种替代旋转的方法，并且很容易并行化。RBT将原始矩阵变换为另一个矩阵，该矩阵不需要旋转就可以因式分解，其概率为1。这种方法对于密集矩阵是成功的；在这项工作中，我们研究了稀疏情况。特别地，我们解决了在转换后的系统中填充的问题。
We consider the solution of sparse linear systems using direct methods via LU factorization. Unless the matrix is positive definite, numerical pivoting is usually needed to ensure stability, which is costly to implement especially in the sparse case. The Random Butterfly Transformations (RBT) technique provides an alternative to pivoting and is easily parallelizable. The RBT transforms the original matrix into another one that can be factorized without pivoting with probability one. This approach has been successful for dense matrices; in this work, we investigate the sparse case. In particular, we address the issue of fill-in in the transformed system.
影响因子：
2.1
作者：
通讯作者：
--