对于两相渗流顺序求解格式中的饱和度计算,采用排序的方法可以将离散的全局非线性系统分解为一系列局部非线性系统来加速非线性求解过程.运用图论中的广度优先算法(Breadth First Algorithm,BFS)和深度优先搜索(Depth First Search,DFS)来实现饱和度的并行计算.在两相流动方向一致时,基于BFS,使得同时参与计算的网格划分为一组,组与组之间满足拓扑排序的要求.在考虑重力和毛管力引起的两相流动方向不一致情况下,根据势能大小建立关于网格的有向有环图(Directed Cyclic Graph,DCG),利用强连通分量搜索的Tarjan算法找出耦合的网格,将耦合的网格视为一个网格并重新建图,从而得到有向无环图(Directed Acyclic Graph,DAG).最终实现饱和度排序求解的并行化.
Research on Parallel Strategy in the Topological Sorting Algorithm of Solving Two-Phase Seepage Flow Based on Graph Theory
In the saturation calculation of the two-phase flow in porous media using Sequential Fully Implicit(SFI)method,the topological sorting algorithm can be used to speed up the nonlinear solution procedure by decomposing the discrete global nonlinear system into a sequence of local nonlinear systems.In this article,we employ the breadth first algorithm(BFS)and the depth first search(DFS)method in graph theory to implement the parallel solution of the saturation distributions.For the cocurrent flow,where both bi-phase velocities have the same direction in the whole calculation domain,the grid system is divided into different groups,where based on the BFS algorithm the grids simultaneously participating in the calculation belong to the same group and the topological sorting solving can be performed simultaneously.For the countercurrent flow caused by gravity and capillary forces,the directed cyclic graph(DCG)is constructed according to the potential energy of the grids,and then the Tarjan algorithm for searching the connected components is utilized to find the groups composed of the coupling grids.Treating each group of the coupling grids as one element,a new graph can be constructed to obtain a directed acyclic graph(DAG).Finally,the parallelization for the topological sorting solution of the saturation is achieved.
NETL
NSTL
万方数据
