期刊
COMPUTERS & GEOSCIENCES
卷 90, 期 -, 页码 41-48出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cageo.2016.02.003
关键词
Invasion percolation; Trapping; Cluster labeling; Algorithm; Hoshen Kopelman; Two phase flow
资金
- European Research Council under the European Community's Seventh Framework Programme (FP7-IDEAS-ERC)/ERC Advanced Grant (WAVETOMO)
I present a fast algorithm for modeling invasion percolation (IP) with trapping (TIP). IP is a numerical algorithm that models quasi-static (i.e. slow) fluid invasion in porous media. Trapping occurs when the invading fluid (that is injected) forms continuous surfaces surrounding patches of the displaced fluid (that is assumed incompressible and originally saturates the invaded medium). In TIP, the invading fluid is not allowed to enter the trapped patches. I demonstrate that TIP can be modeled in two steps: (1) Run an IP simulation without trapping (NTIP). (2) Identify the sites that invaded trapped regions and remove them from the chronological list of sites invaded in NTIP. Fast algorithms exist for solving NTIP. The focus of this paper is to propose an efficient solution for step (2). I show that it can be solved using a disjoint set data structure and going backward in time, i.e. by un-invading all sites invaded in NTIP in reverse order. Time reversal of the invasion greatly reduces the computational complexity for the identification of trapped sites as one only needs to investigate sites neighbor to the latest invaded/un-invaded site. This differs from traditional approaches where trapping is performed in real time, i.e. as the IP simulation is running, and where it is sometimes necessary to investigate the whole lattice to identify newly trapped regions. With the proposed algorithm, the total computational time for the identification and the removal of trapped sites goes as O(N), where N is the total number of sites in the lattice. (C) 2016 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据