Multilevel Graph Partitioning for Three-Dimensional Discrete Fracture Network Flow Simulations

• Published in: Mathematical geosciences 2021-11, Vol.53 (8), p.1699-1724
• Main Authors: Ushijima-Mwesigwa, Hayato, Hyman, Jeffrey D., Hagberg, Aric, Safro, Ilya, Karra, Satish, Gable, Carl W., Sweeney, Matthew R., Srinivasan, Gowri
• Format: Article
• Language: English
• Subjects: Algorithms; Chemistry and Earth Sciences; Communication; Computation; Computational grids; Computer applications; Computer Science; Discrete fracture networks; Earth and Environmental Science; Earth Sciences; Finite element method; Flow simulation; Fractures; GEOSCIENCES; Geotechnical Engineering & Applied Earth Sciences; Graph partitioning; Graph representations; Graphical representations; Hydrogeology; Mathematics; Mesh generation; Mesh partitioning; Network topologies; Partitioning; Permeability; Physics; Processors; Run time (computers); Simulation; Statistics for Engineering; Subsurface flow and transport; Three dimensional flow; Topology; Transport
• ISSN: 1874-8961; 1874-8953
• DOI: 10.1007/s11004-021-09944-y

We present a topology-based method for mesh-partitioning in three-dimensional discrete fracture network (DFN) simulations that takes advantage of the intrinsic multi-level nature of a DFN. DFN models are used to simulate flow and transport through low-permeability fractured media in the subsurface by explicitly representing fractures as discrete entities. The governing equations for flow and transport are numerically integrated on computational meshes generated on the interconnected fracture networks. Modern high-fidelity DFN simulations require high-performance computing on multiple processors where performance and scalability depends partially on obtaining a high-quality partition of the mesh to balance work-loads and minimize communication across all processors. The discrete structure of a DFN naturally lends itself to various graph representations, which can be thought of as coarse-scale representations of the computational mesh. Using this concept, we develop two applications of the multilevel graph partitioning algorithm to partition the mesh of a DFN. In the first, we project a partition of the graph based on the DFN topology onto the mesh of the DFN and in the second, this DFN-based projection is used as the initial condition for further partitioning refinement of the mesh. We compare the performance of these methods with standard multi-level graph partitioning using graph-based metrics (cut, imbalance, partitioning time), computational-based metrics (FLOPS, iterations, solver time), and total run time. The DFN-based and the mesh-based partitioning methods are comparable in terms of the graph-based metrics, but the time required to obtain the partition is several orders of magnitude faster using the DFN-based partitions. The computation-based metrics show comparable performance between both methods so, in combination, the DFN-based partitions are several orders of magnitude faster than the mesh-based partition. Moreover, the method which uses the DFN-partition solution as the initial condition of the mesh partition provided cut and imbalance values that were close to the mesh-based partition but in a fraction of the time. In turn, this hybrid method outperformed both of the other methods in terms of the total run time.