基于坐标分割的聚集型代数多重网格预条件研究

RESEARCH OF THE COORDINATES-PARTITIONING BASED AGGREGATION-TYPE ALGEBRAIC MULTIGRID PRECONDITIONS

针对基于坐标分割的聚集型代数多重网格预条件,给出了三种进行坐标分割的方法,即正方分割、最小界面分割与逐步单向分割,并对其进行了高效实现。正方分割以每个子图接近于正方体或正方形的方式进行分割。最小界面分割遍历所有可能的分割,并以每个子图表面积或周长之和最短的方式进行实际分割。逐步单向分割以分割数的素因子分解为基础,并按素因子从大到小的顺序,每次沿不同坐标数最大的方向进行分割,直到所有素因子遍历完为止。之后对从模型偏微分方程离散得到的稀疏线性方程组,通过V型、W型与K型等多种循环,从多重网格预条件共轭斜量法的效率上,对这三种分割算法进行了实验对比分析。结果表明,逐步单向分割更适合于Jacobi光滑、K-循环与强各向异性等情形。最小界面分割算法更适合于Gauss-Seidel光滑、系数矩阵具有较多非零元素等情形。

In this paper,we proposed three methods for coordinate partitioning based on aggregate-type algebraic multigrid preconditions,ie,square partitioning,minimum interface partitioning,and gradual unidirectional partitioning,and implement them efficiently. Square partitioning was performed in such a way that each subgraph was close to a cube or a square. The minimum interface partition traversed all possible partitions and performed the actual segmentation in the shortest way of the sum of the surface areas or perimeters of each subgraph. Stepwise one-way segmentation was based on the prime factor decomposition of the segmentation number,and the segmentation was performed along the direction with the largest number of different coordinates in order of the prime factors from the largest to the smallest,until all prime factors had been traversed. Afterwards,for the sparse linear equations discretized from the partial differential equations of the model,through V-type,W-type,and K-type cycles,from the efficiency of the multi-grid pre-conditional conjugate skew method,these three segmentation algorithms were used. Experiments were compared and analyzed. The results show that stepwise unidirectional segmentation is more suitable for Jacobi smooth,K-cycle,and strong anisotropy. The minimum interface segmentation algorithm is more suitable for Gauss-Seidel smoothing,and coefficient matrix has more non-zero elements and so on.