The danger of combining block red?black ordering with modified incomplete factorizations and its remedy by perturbation or relaxation
The danger of combining block red?black ordering with modified incomplete factorizations and its remedy by perturbation or relaxation
复制标题
将块红黑排序与改进的不完全因式分解相结合的危险及其通过扰动或松弛的补救措施
DOI：
10.1007/s13160-017-0277-5
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yamamoto Yusaku
中科院分区：
文献类型：
--
作者：
Shioya Akemi;Yamamoto Yusaku
修正的不完全LU/Cholesky分解是Krylov子空间方法的常用预条件子，因为它不需要额外的存储空间，并且比简单的ILU/IC预条件子更有可能加速收敛。对于并行预处理器，块红-黑排序是有吸引力的，由于其高度并行的性质和少量的同步点。因此，它们的组合似乎产生了强大的和可并行的预处理器。然而，事实上，这种组合可能会由于零枢轴的出现而导致因子分解的崩溃。我们分析了这一现象，并给出了规则网格下零枢轴的充要条件。我们还表明，从理论上和实验上，增加扰动的对角元素或放松下降填充的补偿是有用的，以减轻问题。数值试验表明，所得到的预条件子是高效的，适用于最高并行度。
Modified incomplete LU/Cholesky factorizations without fill-ins are popular preconditioners for Krylov subspace methods, because they require no extra memory and have more potential of accelerating the convergence than simple ILU/IC preconditioners. For parallelizing preconditioners, the block red–black ordering is attractive due to its highly parallel nature and small number of synchronization points. Hence, their combination seems to produce powerful and parallelizable preconditioners. In fact, however, this combination can cause breakdown of the factorization due to the occurrence of zero pivots. We analyze this phenomenon and give necessary and sufficient conditions of zero pivots in the case of a regular grid. We also show both theoretically and experimentally that adding perturbation to the diagonal elements or relaxing the compensation of dropped fill-ins is useful to alleviate the problem. Numerical tests show that the resulting preconditioners are highly effective and are applicable for up tolevel of parallelism.