betaFeedback

WorksMathematics

Preconditioning and Reduced-Order Modeling of Navier-Stokes Equations in Complex Porous Microstructures

Abstract

We aim to solve the incompressible Navier-Stokes equations within the complex microstructure of a porous material. Discretizing the equations on a fine grid using a staggered (e.g., marker-and-cell, mixed FEM) scheme results in a nonlinear residual. Adopting the Newton method, a linear system must be solved at each iteration, which is large, ill-conditioned, and has a saddle-point structure. This demands an iterative (e.g., Krylov) solver, that requires preconditioning to ensure rapid convergence. We propose two monolithic algebraic preconditioners, aPLMMNSa\mathrm{PLMM_{NS}} and aPNMNSa\mathrm{PNM_{NS}}, that are generalizations of previously proposed forms by the authors for the Stokes equations (aPLMMSa\mathrm{PLMM_{S}} and aPNMSa\mathrm{PNM_{S}}). The former is based on the pore-level multiscale method (PLMM) and the latter on the pore network model (PNM), both successful approximate solvers. We also formulate faster-converging geometric preconditioners gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM}, which impose ∂nu ⁣= ⁣0\partial_n\boldsymbol{u}\!=\!0 (zero normal-gradient of velocity) exactly at subdomain interfaces. Finally, we propose an accurate coarse-scale solver for the steady-state Navier-Stokes equations based on gPLMMg\mathrm{PLMM}, capable of computing approximate solutions orders of magnitude faster. We benchmark our preconditioners against state-of-the-art block preconditioners and show gPLMMg\mathrm{PLMM} is the best-performing one, followed closely by aPLMMSa\mathrm{PLMM_{S}} for steady-state flow and aPLMMNSa\mathrm{PLMM_{NS}} for transient flow. All preconditioners can be built and applied on parallel machines.

Introduction

Porous media span a wide range of natural (e.g., soil, rock) and engineered (e.g., foamed metal, ceramic) materials with extreme microstructural complexity [1, 2]. High-resolution X-ray μ\muCT imaging [3] is often used to capture this complexity, for subsequent use in pore-scale modeling. Here, we concern ourselves with the Navier-Stokes equations:

ρ(∂tu+u⋅∇u)−μΔu+∇p=ρb(1)\rho(\partial_t\mathbf{u}+\mathbf{u}\cdot\nabla\mathbf{u})-\mu\Delta\mathbf{u}+\nabla p=\rho\mathbf{b} \tag*{(1)}
∇⋅u=0(2)\nabla\cdot\mathbf{u}=0 \tag*{(2)}

describing the flow of a single-phase, incompressible, and Newtonian fluid through the void space Ω\Omega of a porous sample. Eqs. 1a and 1b denote momentum and mass conservation, respectively. Variables u\mathbf{u}, pp, ρ\rho, μ\mu, and b\mathbf{b} represent velocity, pressure, density, viscosity, and body force per unit mass, respectively. The symbols ∇\nabla, Δ\Delta, and ∇⋅\nabla\cdot are the gradient, Laplacian, and divergence operators. Direct numerical simulation (DNS) methods discretize Eq. (1) on a fine grid over Ω\Omega. Popular choices are staggered finite volume (FVM) [4], marker and cell (MAC) finite difference [5], and mixed finite element (MFEM) [6, 7], due to their flux conservation properties essential to subsequent solute transport and two-phase flow simulations [8]. High-fidelity solutions obtained from these methods help characterize geologic sites for CO2_2 sequestration [9], underground H2_2 storage [10], and geothermal energy extraction [11], and design new porous components for fuel cells [12], electrolyzers [13], and heat exchangers and thermal insulators [14].

Algebraic systems arising from the above DNS methods are nonlinear, due to the inertia term u⋅∇u\mathbf{u}\cdot\nabla\mathbf{u}, and are often solved with Newton’s method. Linearization leads to the following saddle-point structure for the Newton update:

Jkδk=−rk⇒[FkGTGO][δukδpk]=−[rukrpk]⇒A^x^=b^(3)J^{k}\delta^{k}=-r^{k}\quad\Rightarrow\quad \begin{bmatrix}F^{k} & G^{\mathsf{T}}\\G& O\end{bmatrix} \begin{bmatrix}\delta_{u}^{k}\\\delta_{p}^{k}\end{bmatrix} =-\begin{bmatrix}r_{u}^{k}\\r_{p}^{k}\end{bmatrix} \quad\Rightarrow\quad\hat{A}\hat{x}=\hat{b} \tag*{(3)}

where rkr^{k} is the residual vector at iteration kk and JkJ^{k} is the corresponding Jacobian. The Newton update δk\delta^{k} consists of a velocity δuk\delta_{u}^{k} and a pressure δpk\delta_{p}^{k} component. The next iterate is obtained from uk+1=uk+δuku^{k+1}=u^{k}+\delta_{u}^{k} and pk+1=pk+δpkp^{k+1}=p^{k}+\delta_{p}^{k}. Residual vectors rukr_{u}^{k} and rpkr_{p}^{k} correspond to discretized momentum and mass balance in Eq. 1, respectively. For simplicity, we denote the linearized system by A^x^=b^\hat{A}\hat{x}=\hat{b}, which is often very large. Solving it requires iterative (e.g., Krylov) solvers, that depend on effective preconditioning to converge rapidly [15]. Our main goal is to develop such preconditioners.

The most common preconditioners are block-triangular [16] of the following form (dropping the index kk):

MB=[FGTOX]⇒MB−1=[F−1−F−1GTX−1OX−1]⇒A^MB−1x^=b^(4)M_{\mathrm{B}}= \begin{bmatrix}F&G^{\mathsf{T}}\\O&X\end{bmatrix} \quad\Rightarrow\quad M_{\mathrm{B}}^{-1}= \begin{bmatrix}F^{-1}&-F^{-1}G^{\mathsf{T}}X^{-1}\\O&X^{-1}\end{bmatrix} \quad\Rightarrow\quad \hat{A}M_{\mathrm{B}}^{-1}\hat{x}=\hat{b} \tag*{(4)}

applied here as a right-preconditioner, MBM_{\mathrm{B}}. If XX equals the Schur complement matrix −GF−1GT-GF^{-1}G^{\mathsf{T}}, convergence is in one step. Note GG is the discrete divergence operator, and its transpose the discrete gradient. The idea behind all block preconditioners is to approximate X−1X^{-1}, or more precisely its action on a given vector, because direct computation is equivalent to solving the system. Thus, left-multiplying a vector by MB−1M_{\mathrm{B}}^{-1} requires solving two smaller systems, one involving the coefficient matrix FF and another involving XX. Since these are elliptic, algebraic multigrid (AMG) [17, 18] is a preferred choice [19]. Approximate candidates for X−1X^{-1} abound in the literature [7, 16, 20–23], among which the scaled-BFBt approximation of [23] was found to exhibit robust performance in complex geometries [24]:

X−1=−(GDF−1GT)−1GDF−1FDF−1GT(GDF−1GT)−1(5)X^{-1}=-(GD_{\mathrm{F}}^{-1}G^{\mathsf{T}})^{-1}GD_{\mathrm{F}}^{-1}FD_{\mathrm{F}}^{-1}G^{\mathsf{T}}(GD_{\mathrm{F}}^{-1}G^{\mathsf{T}})^{-1} \tag*{(5)}

where DFD_{\mathrm{F}} is the diagonal matrix comprised of the diagonal entries of FF.

Unfortunately, using AMG to solve block systems associated with FF and XX, henceforth referred to as bAMG, was found by the authors [24] to result in GMRES stagnation for Stokes flow through complex porous geometries. The prefix b here stands for “block” preconditioner. A far more robust alternative to AMG was proposed by [24] based on the pore-level multiscale method (PLMM) [25] and the pore-network model [26], equipped with better prolongation/restriction matrices. We call these bPLMM and bPNM, which exhibit faster convergence and no stagnation. Even with these improvements, block-preconditioners remain prohibitively slow for practical pore-scale simulation [24].

To address this gap, monolithic preconditioners based on PLMM and PNM were formulated in [24] for the Stokes equations, which are direct algebraic translations of the geometric models these algorithms represent [25, 26]. We denote them by aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}}, where subscript “S” emphasizes the preconditioners are built from the discrete Stokes system. The term “monolithic” implies that velocity and pressure unknowns are solved simultaneously, without splitting the system into blocks. Both aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}} are two-level, consisting of a coarse preconditioner MGM_{\mathrm{G}} and a smoother MLM_{\mathrm{L}}. The former encapsulates the physical insights behind the original PLMM and PNM, and the latter is an additive-Schwarz smoother to wipe out high-frequency errors. A key feature of MGM_{\mathrm{G}} is that it doubles as an approximate Stokes solver, where x^aprx=MG−1b^\hat{x}_{\mathrm{aprx}}=M_{\mathrm{G}}^{-1}\hat{b} is usable in many applications. L2L_{2}-errors with the MGM_{\mathrm{G}} of aPLMMSa\mathrm{PLMM}_{\mathrm{S}} are <2%<2\% for velocity and <1%<1\% for pressure, and with aPNMSa\mathrm{PNM}_{\mathrm{S}} they are <6%<6\% for velocity and <5%<5\% for pressure [24].

Our first goal here is to extend aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}} to the Navier-Stokes equations (Eq. 1), referring to the resulting preconditioners as aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}. In PLMM and PNM, Ω\Omega is decomposed into subdomains called primary and dual grids. In PLMM, primary grids coincide with geometric enlargements of Ω\Omega (or pores), and dual grids (covering primary-grid interfaces) coincide with geometric constrictions (or throats). In PNM, the reverse is true: primary grids are throats and dual grids (and interfaces) are pores. Decompositions are achieved via the watershed segmentation algorithm [27]. Shape and correction vectors are built on each primary grid by solving local systems subject to closure boundary conditions (BCs) at interfaces between primary grids. These BCs are p=constp=\mathrm{const} and ∂nu=0\partial_{n}\mathbf{u}=0, with ∂n\partial_{n} denoting differentiation normal to the interface. For Stokes flow, the BCs are known to be very accurate for PLMM [25], due to converging-diverging flow patterns near throats. In constructing aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}} for Stokes equations, closure BCs are easily imposed via purely algebraic operations [24]. We show this is not the case for the Navier-Stokes equations, because ∂nu=0\partial_n u=0 can only be imposed approximately in building aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}. To impose ∂nu=0\partial_n u=0 exactly in a preconditioner, we show the residual rkr^k in Eq. (3) must be modified by removing the inertia term u⋅∇uu\cdot\nabla u in a small neighborhood of the primary-grid interfaces. This yields the geometric (not algebraic) preconditioners gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM}, where access to the code assembling rkr^k is required. Despite this need for mildly intrusive code access, we find gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM} outperform aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}. We test all preconditioners (aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}}, aPNMNSa\mathrm{PNM}_{\mathrm{NS}}, gPLMMg\mathrm{PLMM}, gPNMg\mathrm{PNM}) in GMRES for a range of 2D/3D porous geometries and benchmark them against state-of-the-art block (bAMGb\mathrm{AMG}, bPLMMb\mathrm{PLMM}, bPNMb\mathrm{PNM}) and Stokes-based (aPLMMSa\mathrm{PLMM}_{\mathrm{S}}, and aPNMSa\mathrm{PNM}_{\mathrm{S}}) preconditioners. In all cases, gPLMMg\mathrm{PLMM} emerges as the best-performing preconditioner. If algebraic preconditioning is desired, aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} are close seconds for the steady-state and unsteady-state Navier-Stokes equations, respectively.

Other monolithic preconditioners for Navier-Stokes equations exist, notably the generalized Dryja-Smith-Widlund (GDSW) [28, 29], but place no emphasis on the importance of decomposition (by watershed) and closure BCs. We show, by comparing aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}} for example, that these choices play outsize roles in Krylov convergence. A further demonstration of this fact was made in [30] for simpler elliptic equations arising from linear elasticity.

Our second contribution is a coarse-scale solver for the steady-state Navier-Stokes equations based on gPLMMg\mathrm{PLMM}. The algorithm yields an approximate solution iteratively, unlike the single-step x^aprx=MG−1b^\hat{x}_{\mathrm{aprx}}=M_{\mathrm{G}}^{-1}\hat{b} for Stokes flow. Iterations consist of Newton updates on coarse (pressure) unknowns only, with no recourse to the fine grid. The coarse solution is mapped onto the fine grid using a prolongation operator, which is not feasible with competing reduced-order models based on PNM [31–33]. Computations are an order of magnitude faster than required for the exact solution.

The paper’s outline follows: Section 2 describes the problem we aim to solve and the fine-grid solver employed. Section 3 details the formulations of the algebraic preconditioners aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}. Section 4 formulates the geometric preconditioners gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM}. The coarse solver for steady-state Navier Stokes is detailed in Section 5. In Section 6, we describe the set of 2D/3D domains considered for testing the preconditioners and the coarse solver. Results are presented in Sections 7–8 and discussed in Section 9. The paper concludes with takeaways in Section 10.

Problem and fine-grid solver

We aim to solve Eq. 1 on the complex void space Ω\Omega of a porous sample (white region in Figure 1a), which is often captured by a pore-scale image (e.g., X-ray CT). Eq. 1 requires an initial condition (IC) u=0u=0 and several boundary conditions (BCs). We impose no-slip (u=0u=0 and ∂np=0\partial_n p=0) on the fluid-solid interface Γw\Gamma_w (white-black boundary in Figure 1a) and inlet/outlet BCs (constant pressure and ∂nu=0\partial_n u=0) on the left/right external boundaries of Ω\Omega, respectively. The latter results in flow from left to right. Here, ∂n\partial_n denotes differentiation in the direction normal to the corresponding boundary. At moderate to low Reynolds numbers Re=ρUl/μRe=\rho Ul/\mu (where UU and ll are characteristic velocity and length), the equations admit a steady-state laminar solution with insufficient inertia, allowing one to drop the utu_t term. At even lower ReRe, flow becomes creeping, reducing Eq. 1 to the Stokes equations by further dropping u⋅∇uu\cdot\nabla u.

Figure 1. Schematic of a pore-scale image and its decomposition into primary grids and dual grids in the PLMM and PNM preconditioner. (a) The white regions of the image represent the void space and black regions represent the solid phase. The Navier-Stokes equations are solved in the void space. (b, d) Primary grids (or subdomains) obtained from PLMM (b) and PNM (d) decompositions. (c, e) Corresponding dual grids that overlap the contact interfaces shared between primary grids. (f, g) Each basis function is associated with one contact interface (yellow). In PLMM, each contact interface is shared by only two adjacent primary grids. While in PNM, each contact interface is shared among multiple primary grids.

We discretize Eq. 1 on a Cartesian fine grid that conforms to, or is an integer fraction of, the image pixels comprising Ω\Omega. We use a marker and cell (MAC) finite difference method, with velocity unknowns defined at cell faces and pressure unknowns at cell centers, as shown in Figure 2c. We remark that our proposed preconditioners in later sections are by no means limited to Cartesian grids or the MAC scheme. Other discretizations discussed in Section 1 (e.g., FVM, MFEM), where velocity and pressure are arranged in a spatially staggered fashion, are equally possible and would benefit from our preconditioners. The resulting discrete system, given by Eq. (3), is nonlinear and is solved with Newton’s method. At each iteration of Newton, a linearized system of the form A^x^=b^\hat{A}\hat{x}=\hat{b} is solved.

Figure 2. (a) Two primary grids, Ω1p\Omega_1^p and Ω2p\Omega_2^p, separated by a contact interface, Γ12\Gamma_{12}. (b) Partitioning of the cells and faces of the fine grid among the two primary grids and the contact interface is shown. Light/dark blue cells/faces belong to Ω1p\Omega_1^p, light/dark green cells/faces belong to Ω2p\Omega_2^p, and light/dark red cells/faces belong to Γ12\Gamma_{12}. (c) The cell unknowns correspond to pressure, pp, and the face unknowns correspond to velocity, uu.

The blocks FkF^k, GTG^\mathsf{T}, GG, and A^\hat{A} in Eq. (3) are discrete forms of the ρ∂t+ρL(u⋅∇u)−μΔ\rho\partial_t+\rho\mathcal{L}(u\cdot\nabla u)-\mu\Delta, gradient (∇\nabla), and divergence (∇⋅\nabla\cdot) operators, respectively. The symbol L(⋅)\mathcal{L}(\cdot) denotes the argument is linearized around the previous iterate, which is why only FkF^k has superscript kk. For Stokes flow, FF is symmetric and the residual rkr^k is linear, allowing Newton to converge in one step. For Navier-Stokes flow, neither symmetry nor linearity are present. For practical domain sizes of real porous microstructures, A^\hat{A} is large and poorly conditioned, caused by the geometric complexity of Ω\Omega and the small fine-grids needed to resolve it. This demands iterative solvers like GMRES, which require preconditioning.

Algebraic monolithic preconditioner

We extend the fully-algebraic monolithic preconditioners aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}} originally designed for the Stokes equations [24] to the Navier-Stokes equations. They are based on the pore-level multiscale method (PLMM) and the the pore network model (PNM). We refer to the extended preconditioners as aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}, where prefix “a” denotes “algebraic.” Both are two-level with a global (coarse) preconditioner MG\mathrm{M}_{\mathrm{G}} and a local (fine) smoother ML\mathrm{M}_{\mathrm{L}}. Section 3.1 outlines the overall structure of the two-level preconditioners, combining MG\mathrm{M}_{\mathrm{G}} and ML\mathrm{M}_{\mathrm{L}}. Since the mathematical structures of aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}} are identical, we detail aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} first in Section 3.2 then highlight

key differences of aPNMNSa\mathrm{PNM}_{\mathrm{NS}} in § 3.3. In § 3.2.1, we describe the domain decomposition central to MGM_{\mathrm{G}} and MLM_{\mathrm{L}}. § 3.2.2 formulates MGM_{\mathrm{G}}, and § 3.2.3 reviews the additive-Schwarz smoother MLM_{\mathrm{L}} by [24]. Since aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}} reduce to aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPNMSa\mathrm{PNM}_{\mathrm{S}} for Stokes flow, we drop subscripts “NS” and “S” below.

Overall structure

The monolithic aPLMMa\mathrm{PLMM} and aPNMa\mathrm{PNM} preconditioners M\mathrm{M} are formulated as:

M−1=MG−1+ML−1(I−A^MG−1)(6)\mathrm{M}^{-1}=\mathrm{M}_{\mathrm{G}}^{-1}+\mathrm{M}_{\mathrm{L}}^{-1}\left(\mathrm{I}-\widehat{\mathrm{A}}\mathrm{M}_{\mathrm{G}}^{-1}\right) \tag*{(6)}
ML−1=∑i=1nstML−1(I−A^ML−1)i−1(7)\mathrm{M}_{\mathrm{L}}^{-1}=\sum_{i=1}^{n_{\mathrm{st}}}\mathrm{M}_{\mathrm{L}}^{-1}\left(\mathrm{I}-\widehat{\mathrm{A}}\mathrm{M}_{\mathrm{L}}^{-1}\right)^{i-1} \tag*{(7)}

where the global preconditioner MG\mathrm{M}_{\mathrm{G}} and the smoother ML\mathrm{M}_{\mathrm{L}} are combined multiplicatively, with the former attenuating low-frequency errors and the latter high-frequency errors. The local smoother itself is a multiplicative (nstn_{\mathrm{st}}-stage) application of a base smoother Ml\mathrm{M}_{\mathrm{l}}, which can be any black-box preconditioner (e.g., block Gauss-Seidel) or a custom smoother compatible with MG\mathrm{M}_{\mathrm{G}}. Our numerical tests show that the additive-Schwarz smoother Mpd\mathrm{M}_{\mathrm{pd}} from [24] (reviewed in § 3.2.3) provides superior performance. Therefore, we adopt Ml=Mpd\mathrm{M}_{\mathrm{l}}=\mathrm{M}_{\mathrm{pd}} with nst=1n_{\mathrm{st}}=1 throughout this work.

Monolithic PLMM preconditioner

Domain decomposition

To build MG\mathrm{M}_{\mathrm{G}} and ML\mathrm{M}_{\mathrm{L}}, the domain Ω\Omega is first decomposed into NpN^{p} non-overlapping subdomains Ωip\Omega_{i}^{p}, called primary grids. The decomposition uses a modified watershed segmentation algorithm [34] that operates on a binary-image representation of Ω\Omega, as shown in Figure 1b for the pore-scale image in Figure 1a. Primary grids appear as randomly colored regions. The interfaces between adjacent primary grids, Γij\Gamma_{ij}, are called contact interfaces (thick yellow line in Figure 1f). Watershed segmentation ensures that Ωip\Omega_{i}^{p} correspond to local geometric enlargements of Ω\Omega and Γij\Gamma_{ij} to local constrictions. We also construct NdN^{d} complementary dual grids Ωid\Omega_{i}^{d} that overlap contact interfaces and cover a thin region around them (see Figure 1c). Dual grids are built by successive morphological dilations of the pixels comprising each contact interface [24, 25]. By construction, NdN^{d} equals the number of contact interfaces NcN^{c}. Dual grids are used only by ML\mathrm{M}_{\mathrm{L}} to remove high-frequency errors concentrated near Γij\Gamma_{ij} after each application of MG\mathrm{M}_{\mathrm{G}}. Notice the union of Ωid\Omega_{i}^{d} is much smaller than Ω\Omega. Unlike the PLMM algorithm of [25], where overlapping Ωid\Omega_{i}^{d} are merged (sometimes creating large sample-spanning regions with costly local problems), here Ωid\Omega_{i}^{d} are allowed to overlap, avoiding this computational drawback. Primary and dual grids are collectively termed coarse grids when the distinction is unimportant.

Global preconditioner

In iterative solvers, preconditioning means solving systems like A^x^=b^\widehat{\mathrm{A}}\widehat{x}=\widehat{b} approximately for x^\widehat{x} given b^\widehat{b}. The proposed MG\mathrm{M}_{\mathrm{G}} is presented first as a recipe for computing an approximate solution, involving three operations called permutation, reduction, and prolongation. These operations parallel those of [24] for the Stokes equations, with key differences highlighted below. We then provide a compact representation of MG−1\mathrm{M}_{\mathrm{G}}^{-1} as the composition of matrices and operators.

Permutation. The goal here is to reshuffle the rows and columns of A^\widehat{\mathrm{A}} such that the fine-grid entries associated with each primary grid, Ωip\Omega_{i}^{p}, and each contact interface Γij\Gamma_{ij}, are grouped together by applying a permutation matrix W\mathrm{W} to the linear system in Eq. (3). Consider the simple domain Ω\Omega depicted in Figure 2a, which is decomposed into two primary grids Ω1p\Omega_{1}^{p} and Ω2p\Omega_{2}^{p}, sharing the contact interface Γ12\Gamma_{12}. With reference to Figure 2b, fine-grid cells comprising Ω\Omega are partitioned into those that belong to: (1) Ω1p\Omega_{1}^{p} (light blue); (2) Ω2p\Omega_{2}^{p} (light green); and (3) Γ12\Gamma_{12} (light red). Here, Γ12\Gamma_{12} is defined by the thinnest 4-connected collection of pixels in 2D (and 6-connected in 3D) that topologically separate the two primary grids. Other definitions of Γ12\Gamma_{12} may be used without loss of generality. A similar partitioning of the fine-grid faces is performed as follows: (1) faces flanked by at least one cell from Ω1p\Omega_{1}^{p} belong to Ω1p\Omega_{1}^{p} (dark blue); (2) faces flanked by at least one cell from Ω2p\Omega_{2}^{p} belong to Ω2p\Omega_{2}^{p} (dark green); and (3) faces flanked by cells neither in Ω1p\Omega_{1}^{p} nor Ω2p\Omega_{2}^{p} belong to Γ12\Gamma_{12} (dark red). Given this labeling of cells and faces, the matrix W\mathrm{W} is constructed as follows:

WTA^W⏟AWTx^⏟x=WTb^⏟b⇒Ax=b(8)\underbrace{\mathrm{W}^{\mathsf{T}}\widehat{\mathrm{A}}\mathrm{W}}_{\mathrm{A}}\underbrace{\mathrm{W}^{\mathsf{T}}\widehat{x}}_{\mathrm{x}}=\underbrace{\mathrm{W}^{\mathsf{T}}\widehat{b}}_{\mathrm{b}} \quad\Rightarrow\quad \mathrm{A}\mathrm{x}=\mathrm{b} \tag*{(8)}

with the block structure below for AA, bb, and xx:

A=[AppAcpAfpApcAccAfcApfAcfAff]b=[bpbcbf]x=[xpxcxf](9)A=\begin{bmatrix} A_{p}^{p} & A_{c}^{p} & A_{f}^{p}\\ A_{p}^{c} & A_{c}^{c} & A_{f}^{c}\\ A_{p}^{f} & A_{c}^{f} & A_{f}^{f} \end{bmatrix} \qquad b=\begin{bmatrix} b^{p}\\ b^{c}\\ b^{f} \end{bmatrix} \qquad x=\begin{bmatrix} x^{p}\\ x^{c}\\ x^{f} \end{bmatrix} \tag*{(9)}

We remark that the matrix W\mathrm{W} is unitary and satisfies WWT=I\mathrm{W}\mathrm{W}^{\mathrm{T}}=\mathrm{I}.

The super/subscript pp in each block denotes the cell and face unknowns/residuals belonging to the primary grids. The super/subscript cc and ff denote the cell only and face only unknowns/residuals belonging to the contact interfaces, respectively. Recall that the cell and face unknowns correspond to pressure and velocity, respectively (Figure 2c).

Reduction. The goal of reduction is to introduce closure or localization assumptions that simplify and effectively decouple the permuted system in Eq.6. For the Stokes equations, the steps outlined below enforce the closure BCs p=constp=\mathrm{const} and ∂nu=0\partial_n u=0 on each contact interface. In [25], a local analysis was performed, demonstrating these BCs are nearly optimal for Stokes flow based on arguments that streamlines exhibit a converging-diverging pattern at geometric constrictions (Γ12\Gamma_{12} in Figure 1b). For the Navier-Stokes equations, we adopt the same reduction steps but with two caveats. The velocity closure no longer corresponds to ∂nu=0\partial_n u=0 due to the asymmetric upwind discretization of the inertia term in Eq.1a. Additionally, the suitability of these closures for Navier-Stokes flow is diminished given the more complex streamline patterns near geometric constrictions compared to Stokes flow, as we illustrate next.

To impose ∂u/∂n≈0\partial u/\partial n\approx0 (where “≈\approx” means “inexact”) at contact interfaces, we first approximate AA as follows:

A≈[A~ppAcpOApcA~ccOApfAcfAff]A~pp=App+diag⁡(csum⁡(Afp))A~cc=Acc+diag⁡(csum⁡(Afc))(10)A\approx \begin{bmatrix} \widetilde{A}_{p}^{p} & A_{c}^{p} & \mathrm{O}\\ A_{p}^{c} & \widetilde{A}_{c}^{c} & \mathrm{O}\\ A_{p}^{f} & A_{c}^{f} & A_{f}^{f} \end{bmatrix} \qquad \widetilde{A}_{p}^{p}=A_{p}^{p}+\operatorname{diag}\left(\operatorname{csum}\left(A_{f}^{p}\right)\right) \qquad \widetilde{A}_{c}^{c}=A_{c}^{c}+\operatorname{diag}\left(\operatorname{csum}\left(A_{f}^{c}\right)\right) \tag*{(10)}

where the operation csum⁡(⋅)\operatorname{csum}(\cdot) sums all columns of its argument matrix to yield a single column vector. The operation diag⁡(⋅)\operatorname{diag}(\cdot) takes an input vector and creates a diagonal matrix whose diagonal entries coincide with those of the vector. Notice by imposing ∂nu≈0\partial_n u\approx0 in Eq.7, the face-only unknowns xfx^{f} defined at contact interfaces are now decoupled from the system. Therefore, we may henceforth focus on solving the smaller system A~x~=b~\widetilde{A}\widetilde{x}=\widetilde{b} with:

A~=[A~ppAcpApcA~cc]b~=[bpbc]x~=[xpxc](11)\widetilde{A}= \begin{bmatrix} \widetilde{A}_{p}^{p} & A_{c}^{p}\\ A_{p}^{c} & \widetilde{A}_{c}^{c} \end{bmatrix} \qquad \widetilde{b}= \begin{bmatrix} b^{p}\\ b^{c} \end{bmatrix} \qquad \widetilde{x}= \begin{bmatrix} x^{p}\\ x^{c} \end{bmatrix} \tag*{(11)}

after which xfx^{f} can be obtained by back substitution (this is fast because AffA_{f}^{f} is a very small):

xf=(Aff)−1(bf−Apfxp−Acfxc)(12)x^{f}=\left(A_{f}^{f}\right)^{-1}\left(b^{f}-A_{p}^{f}x^{p}-A_{c}^{f}x^{c}\right) \tag*{(12)}

Focusing next on Eq.8, each block consists of the following sub-blocks:

A~pp=[A~p1p1⋯A~pnp1⋮⋱⋮A~p1pn⋯A~pnpn]A~cc=[A~c1c1⋯A~cmc1⋮⋱⋮A~c1cm⋯A~cmcm]Acp=[Ac1p1⋯Acmp1⋮⋱⋮Ac1pn⋯Acmpn]Apc=[Ap1c1⋯Apnc1⋮⋱⋮Ap1cm⋯Apncm](13)\widetilde{A}_{p}^{p}= \begin{bmatrix} \widetilde{A}_{p_{1}}^{p_{1}} & \cdots& \widetilde{A}_{p_{n}}^{p_{1}}\\ \vdots& \ddots& \vdots\\ \widetilde{A}_{p_{1}}^{p_{n}} & \cdots& \widetilde{A}_{p_{n}}^{p_{n}} \end{bmatrix} \qquad \widetilde{A}_{c}^{c}= \begin{bmatrix} \widetilde{A}_{c_{1}}^{c_{1}} & \cdots& \widetilde{A}_{c_{m}}^{c_{1}}\\ \vdots& \ddots& \vdots\\ \widetilde{A}_{c_{1}}^{c_{m}} & \cdots& \widetilde{A}_{c_{m}}^{c_{m}} \end{bmatrix} \qquad A_{c}^{p}= \begin{bmatrix} A_{c_{1}}^{p_{1}} & \cdots& A_{c_{m}}^{p_{1}}\\ \vdots& \ddots& \vdots\\ A_{c_{1}}^{p_{n}} & \cdots& A_{c_{m}}^{p_{n}} \end{bmatrix} \qquad A_{p}^{c}= \begin{bmatrix} A_{p_{1}}^{c_{1}} & \cdots& A_{p_{n}}^{c_{1}}\\ \vdots& \ddots& \vdots\\ A_{p_{1}}^{c_{m}} & \cdots& A_{p_{n}}^{c_{m}} \end{bmatrix} \tag*{(13)}
bp=[bp1⋮bpn]bc=[bc1⋮bcm]xp=[xp1⋮xpn]xc=[xc1⋮xcm](14)b^{p}=\begin{bmatrix}b^{p_{1}}\\ \vdots\\ b^{p_{n}}\end{bmatrix} \qquad b^{c}=\begin{bmatrix}b^{c_{1}}\\ \vdots\\ b^{c_{m}}\end{bmatrix} \qquad x^{p}=\begin{bmatrix}x^{p_{1}}\\ \vdots\\ x^{p_{n}}\end{bmatrix} \qquad x^{c}=\begin{bmatrix}x^{c_{1}}\\ \vdots\\ x^{c_{m}}\end{bmatrix} \tag*{(14)}

where n=Npn=N^{p} and m=Ncm=N^{c}, with NpN^{p} and NcN^{c} denoting the total number of primary grids and contact interfaces in Ω\Omega. Each sub-block corresponds to entries associated with either a primary grid, a contact interface, or a coupling between the two. To complete the imposition of ∂nu≈0\partial_n u \approx0, we further simplify the A~pp\widetilde{A}_p^p sub-block as follows:

A~pp≈Aˉpp=[Aˉp1p1O⋱OAˉpnpn]Aˉpipi=Aˉpipi+diag⁡(∑j≠icsum⁡(Aˉpjpi))(15)\widetilde{A}_p^p \approx\bar{A}_p^p = \begin{bmatrix} \bar{A}_{p_1}^{p_1} & O & \\ & \ddots& \\ O & & \bar{A}_{p_n}^{p_n} \end{bmatrix} \qquad \bar{A}_{p_i}^{p_i}=\bar{A}_{p_i}^{p_i}+\operatorname{diag}\left(\sum_{j\ne i}\operatorname{csum}(\bar{A}_{p_j}^{p_i})\right) \tag*{(15)}

where Aˉpp\bar{A}_p^p is block-diagonal matrix with the entries of each primary grid fully decoupled from those of other primary grids. Similar to Eq. (10), the off-diagonal blocks of each block-row in A~pp\widetilde{A}_p^p are column-summed and added to its main diagonal entries. We are now left with solving the simpler system A~x~=b~\widetilde{A}\widetilde{x}=\widetilde{b}, with:

A~=[AˉppAcpApcAˉcc](16)\widetilde{A}= \begin{bmatrix} \bar{A}_p^p & A_c^p\\ A_p^c & \bar{A}_c^c \end{bmatrix} \tag*{(16)}

To enforce p=constp=\mathrm{const} at contact interfaces, we introduce a reduction matrix, Q:

Q=[INfp×NfppOOQc]Qo=[1c1O⋱O1cm]Nfc×Nfc1ci=[1⋮1]Nfci×1(17)Q= \begin{bmatrix} I_{N_f^p\times N_f^p}^p & O\\ O & Q^c \end{bmatrix} \qquad Q^o= \begin{bmatrix} 1^{c_1} & & O\\ & \ddots& \\ O & & 1^{c_m} \end{bmatrix}_{N_f^c\times N_f^c} \qquad 1^{c_i}= \begin{bmatrix} 1\\ \vdots\\ 1 \end{bmatrix}_{N_f^{c_i}\times1} \tag*{(17)}

such that when applied, yields the following reduced system:

A~x~=b~,x~≃QxM⇒QTA~QxM=QTb~⇒AMxM=bM(18)\widetilde{A}\widetilde{x}=\widetilde{b},\qquad\widetilde{x}\simeq Qx_M \quad\Rightarrow\quad Q^{T}\widetilde{A}Qx_M=Q^{T}\widetilde{b} \quad\Rightarrow\quad A_Mx_M=b_M \tag*{(18)}

In Eq. 13a, NfpN_f^p, NfcN_f^c, and NfciN_f^{c_i} denote the number of fine-scale unknowns belonging to all primary grids, all contact interfaces, and the contact interface labeled cic_i, respectively. We remark that NfpN_f^p includes both velocity and pressure unknowns, whereas NfcN_f^c and NfciN_f^{c_i} include only pressure unknowns. The reduction matrix Q is block-diagonal and is comprised of only 0 and 1 entries. Left-multiplying (or right-multiplying) a matrix by QTQ^T (or Q) has the effect of performing a row-sum (or column-sum) of all fine-scale entries associated with each contact interface separately. As the entries belonging to the interface cic_i in Aˉ\bar{A} correspond to only pressure unknowns, the closure p=constp=\mathrm{const} over cic_i is imposed by the column-sum. The row-sum ensures overall (“weak”) mass conservation across each interface.

The reduced system has now the following block structure:

AM=[AˉppAˉcpAˉpcAˉcc]bM=[bpbˉc]xM=[xpxo](19)A_M= \begin{bmatrix} \bar{A}_p^p & \bar{A}_c^p\\ \bar{A}_p^c & \bar{A}_c^c \end{bmatrix} \qquad b_M= \begin{bmatrix} b^p\\ \bar{b}^c \end{bmatrix} \qquad x_M= \begin{bmatrix} x^p\\ x^o \end{bmatrix} \tag*{(19)}

where xox^o (with length Nc×1N^c\times1) contains coarse-scale pressure unknowns defined at contact interfaces (one per interface).

Prolongation. The goal here is to build a prolongation matrix, P, and a restriction matrix, R, such that a coarse-scale problem can be formulated to solve for the interface pressures xox^o. This is done as follows:

AMxM=bM,xM=P[xoyo]⇒RAMP[xoyo]=RbM(20)A_Mx_M=b_M,\qquad x_M=P \begin{bmatrix} x^o\\ y^o \end{bmatrix} \quad\Rightarrow\quad RA_MP \begin{bmatrix} x^o\\ y^o \end{bmatrix} =Rb_M \tag*{(20)}

where yoy^o are auxiliary coarse-scale unknowns associated with the primary grids.

The prolongation matrix P has the following block structure:

P=[BCIO]B=[pc1p1pc2p1⋯pcmp1pc1p2pc2p2⋯pcmp2⋮⋮⋱⋮pc1pnpc2pn⋯pcmpn]Nfp×NcC=[cp1O⋱Ocpn]Nfp×Np(21)P= \begin{bmatrix} B & C\\ I & O \end{bmatrix} \qquad B= \begin{bmatrix} p_{c_1}^{p_1} & p_{c_2}^{p_1} & \cdots& p_{c_m}^{p_1}\\ p_{c_1}^{p_2} & p_{c_2}^{p_2} & \cdots& p_{c_m}^{p_2}\\ \vdots& \vdots& \ddots& \vdots\\ p_{c_1}^{p_n} & p_{c_2}^{p_n} & \cdots& p_{c_m}^{p_n} \end{bmatrix}_{N_f^p\times N^c} \qquad C= \begin{bmatrix} c^{p_1} & & O\\ & \ddots& \\ O & & c^{p_n} \end{bmatrix}_{N_f^p\times N^p} \tag*{(21)}

where pcjpip_{c_j}^{p_i} and ccjpic_{c_j}^{p_i} are called shape and correction vectors, respectively. The shape vectors are defined as follows:

pcjpi={−(Aˉpipi)−1RpipiAcpiecjc,cj∈CpiO,cj∉Cpi(22)p_{c_j}^{p_i} = \begin{cases} -\left(\bar{A}_{p_i}^{p_i}\right)^{-1}R_{p_i}^{p_i}A_c^{p_i}e_{c_j}^{c}, & c_j \in C^{p_i}\\ O, & c_j \notin C^{p_i} \end{cases} \tag*{(22)}
ecjc=[δ1j,δ2j,⋯ ,δmj]Nc×1T(23)e_{c_j}^{c} = \left[\delta_{1j},\delta_{2j},\cdots,\delta_{mj}\right]^{\mathsf{T}}_{N_c\times1} \tag*{(23)}

The index set CpiC^{p_i} contains all contact interfaces that intersect the boundary of the primary grid pip_i. The Kronecker delta δab\delta_{ab} is used to define the unit vector ecjce_{c_j}^{c}, with 1 occupying its jjth entry and 0 elsewhere. The matrix RppiR_p^{p_i} is called a contraction matrix that restricts a fine-scale Nfp×1N_f^p \times1 vector defined over the union of all primary grids (excluding the contact interfaces) to a fine-scale Nfpi×1N_f^{p_i} \times1 vector defined over the primary grid pip_i only. More precisely:

Rppi=[Δp1pi,Δp2pi,⋯ ,Δpnpi]Nfpi×NfpΔpjpi={INfpi×Nfpi,if i=jONfpi×Nfpj,if i≠j(24)R_p^{p_i} = \left[ \Delta_{p_1}^{p_i},\Delta_{p_2}^{p_i},\cdots,\Delta_{p_n}^{p_i} \right]_{N_f^{p_i}\times N_f^p} \qquad \Delta_{p_j}^{p_i} = \begin{cases} I_{N_f^{p_i}\times N_f^{p_i}}, & \text{if } i=j\\ O_{N_f^{p_i}\times N_f^{p_j}}, & \text{if } i\ne j \end{cases} \tag*{(24)}

Similar to NfpN_f^p defined earlier, NfpiN_f^{p_i} is the number of fine-scale unknowns that belong to primary grid pip_i. From Eq. 16b, it is obvious that the matrix B is very sparse, because only two shape vectors per column contain non-zero entries. These two shape vectors belong to the two primary grids sandwiching the contact interface associated with each column (Figure 1f). As we shall discuss in § 3.3, this does not hold for the aPNM preconditioner (Figure 1g).

Returning back to Eq. 16a, the correction vectors are defined as follows:

cpi=(Aˉpipi)−1bBpi(25)c^{p_i}=\left(\bar{A}_{p_i}^{p_i}\right)^{-1}b_B^{p_i} \tag*{(25)}

where bBpib_B^{p_i} is a right-hand side (RHS) vector defined on primary grid pip_i that accounts for any non-homogeneous BCs and source terms (b≠0b \ne0) in Eq. 1. This does not equal bpib^{p_i} in Eq. 10b, which also includes non-zero entries associated with the PDE residual in the interior of Ωip\Omega_i^p, specifically bpi=bBpi+bfpib^{p_i}=b_B^{p_i}+b_f^{p_i}. To compute bBpib_B^{p_i}, we evaluate the residual of the steady-state form of Eq. 1 (dropping the time derivative, or equivalently using zero velocity at the previous time step) at the origin (i.e., r(u=0,p=0)r(u=0,p=0)), then subject the result to the same permutation in Eq. 6. We remark that for the Stokes equations, where Eq. 1 is linear, the discrete system A^x^=b^\hat{A}\hat{x}=\hat{b} yields a RHS vector b^\hat{b} that contains only the effect of non-homogeneous BCs, resulting in bpi=bBpib^{p_i}=b_B^{p_i}. Hence, no distinction between these two vectors was made in [24]. Here, we use bBpib_B^{p_i} instead of bpib^{p_i} in Eq. 16e because extensive numerical tests revealed the latter leads to poor GMRES convergence by introducing high-frequency errors in cpic^{p_i} over primary grids.

Having completed the definition of P, we now define the restriction matrix in Eq. (20) as:

R=[OIΠ(CT)O](26)R = \begin{bmatrix} O & I\\ \Pi(C^{\mathsf{T}}) & O \end{bmatrix} \tag*{(26)}

where I is the Nc×NcN^c\times N^c identity matrix, and Π(CT)\Pi(C^{\mathsf{T}}) is a matrix with 0 and 1 entries that reflects the sparsity pattern of CTC^{\mathsf{T}} in Eq. 16a (i.e., entries are 1 where CTC^{\mathsf{T}} is non-zero, and 0 elsewhere). Left-multiplying AMA_M by R performs a row-sum over each primary grid while leaving the rows associated with contact interfaces intact. Combined with the earlier row-sum performed through the application of Q in Eq. 13b over entries of each contact interface, mass conservation is imposed in a weak (integrated) sense within each primary grid and across each contact interface. Note that R≠PTR \ne P^{\mathsf{T}}. The choice of the restriction matrix in Eq. (26) is motivated by the fact that a Galerkin restriction (R=PTR=P^{\mathsf{T}}) leads to poor solver performance for (Navier-)Stokes equations discretized with MAC finite differences or similar schemes [24].

We note that constructing R is trivial, and constructing P is embarrassingly parallelizable. The latter follows because computing shape and correction vectors in Eqs. 16b and 16e involves solving fully decoupled local systems on primary grids. Since only RHS vectors differ between systems, local LU-decomposition can accelerate computations.

Summary. The above steps constitute a recipe for computing the action of the global preconditioner, MG−1M_G^{-1}, on a RHS vector b^\hat{b}. For notational simplicity, and ease of reference later, we express this action as:

MG−1=P^(R^A^P^)−1R^(27)M_{\mathrm{G}}^{-1}=\hat{P}(\hat{R}\hat{A}\hat{P})^{-1}\hat{R} \tag*{(27)}

where P^\hat{P} and R^\hat{R} are effective prolongation and restriction matrices, respectively, and A~\tilde{A} a transformation of A^\hat{A}:

P^=WQP(28)\hat{P}=WQP \tag*{(28)}
R^=RQTWT(29)\hat{R}=RQ^{\mathsf{T}}W^{\mathsf{T}} \tag*{(29)}
A~=WC(WTA^W)WT(30)\tilde{A}=WC(W^{\mathsf{T}}\hat{A}W)W^{\mathsf{T}} \tag*{(30)}

Recall WW, QQ, PP, and RR are the permutation (Eq.6a), reduction (Eq.13a), prolongation (Eq.16a), and restriction (Eq. (26)) matrices introduced earlier. The operator C(⋅)C(\cdot) is linear and encapsulates the column-sums performed in Eqs. (10) and (15) to impose the velocity closure BC. The csum(⋅)(\cdot) operation in Eqs. (10) and (15) does not admit a simple matrix representation. Left-multiplying a coarse-grid vector, like [xT,yT]T[x^{\mathsf{T}},y^{\mathsf{T}}]^{\mathsf{T}} in Eq. (20), by P^\hat{P} maps it onto the fine grid. Left-multiplication by R^\hat{R} maps in the inverse direction. The above representation of MGM_{\mathrm{G}} makes one of its key properties immediately clear:

Proposition 3.1. The matrix MG−1A^M_{\mathrm{G}}^{-1}\hat{A} is not a projection, where MG−1M_{\mathrm{G}}^{-1} is given by Eq. (27) for the saddle-point Stokes or Navier–Stokes equations. This lies in contrast to MG−1=P^(R^A^P^)−1R^M_{\mathrm{G}}^{-1}=\hat{P}(\hat{R}\hat{A}\hat{P})^{-1}\hat{R} for elliptic equations, where MG−1A^M_{\mathrm{G}}^{-1}\hat{A} is a projection.

Proof. A simple substitution of Eqs. (27)–19 into (MG−1A^)2(M_{\mathrm{G}}^{-1}\hat{A})^2 shows that the product does not equal MG−1A^M_{\mathrm{G}}^{-1}\hat{A}, unless C(⋅)C(\cdot) is the identity matrix. For elliptic equations, C(⋅)C(\cdot) is identity [35], but not for saddle-point equations studied herein. □

Remark 1. We found empirically that MG−1=P^(R^A^P^)−1R^M_{\mathrm{G}}^{-1}=\hat{P}(\hat{R}\hat{A}\hat{P})^{-1}\hat{R} performs almost identically to Eq. (27) (notice the difference in using A^\hat{A} versus A~\tilde{A}). In other words, the column-sum operator C(⋅)C(\cdot) in Eq.19c can be replaced by the identity matrix. We adopt this formulation to produce all results in § 8, because it saves the extra column-sum operation.

Local smoother

Application of the global preconditioner MGM_{\mathrm{G}} leaves behind high-frequency errors concentrated near contact interfaces [24]. Therefore, a compatible local smoother MLM_{\mathrm{L}} is needed to attenuate these errors. We adopt the dual-primary smoother2 ML=MdpM_{\mathrm{L}}=M_{\mathrm{dp}} of [24], which has exhibited superior performance over other black-box alternatives. The dual-primary smoother combines two additive-Schwarz (block-Jacobi) preconditioners multiplicatively:

Mdp−1=Mp−1+Mp−1(I−A^Md−1)(31)M_{\mathrm{dp}}^{-1}=M_{\mathrm{p}}^{-1}+M_{\mathrm{p}}^{-1}(I-\hat{A}M_{\mathrm{d}}^{-1}) \tag*{(31)}

where Md−1M_{\mathrm{d}}^{-1} is applied first to eliminate errors within dual grids, then Mp−1M_{\mathrm{p}}^{-1} is applied to remove errors within primary grids. Both MdM_{\mathrm{d}} and MpM_{\mathrm{p}} have standard additive-Schwarz formulations [15]:

Mp−1=∑i=1NpEfpi(RfpiA^Efpi)−1RfpiMd−1=∑i=1NcEfdi(RfdiA^Efdi)−1Rfdi(32)M_{\mathrm{p}}^{-1}=\sum_{i=1}^{N^{\mathrm{p}}}E_{f}^{\mathrm{p}i}(R_{f}^{\mathrm{p}i}\hat{A}E_{f}^{\mathrm{p}i})^{-1}R_{f}^{\mathrm{p}i} \qquad M_{\mathrm{d}}^{-1}=\sum_{i=1}^{N^{\mathrm{c}}}E_{f}^{\mathrm{d}i}(R_{f}^{\mathrm{d}i}\hat{A}E_{f}^{\mathrm{d}i})^{-1}R_{f}^{\mathrm{d}i} \tag*{(32)}

The matrices RfpiR_{f}^{\mathrm{p}i} and EfpiE_{f}^{\mathrm{p}i} restrict and extend vectors between Ωip\Omega_{i}^{\mathrm{p}} and Ω\Omega, respectively, while RfdiR_{f}^{\mathrm{d}i} and EfdiE_{f}^{\mathrm{d}i} operate between Ωid\Omega_{i}^{\mathrm{d}} and Ω\Omega. These restriction and extension matrices are transposes of each other and contain only 0 and 1 entries. For details, see [24]. Applying MdM_{\mathrm{d}} requires solving NdN^{\mathrm{d}} (=Nc=N^{\mathrm{c}}) decoupled problems on dual grids, and applying MpM_{\mathrm{p}} requires solving NpN^{\mathrm{p}} decoupled problems on primary grids. Both operations are embarrassingly parallelizable.

Monolithic PNM preconditioner

The overall structures of MGM_{\mathrm{G}} and MLM_{\mathrm{L}} for the monolithic aPNM preconditioner are identical to those of the monolithic aPLMM. The only difference lies in the definitions of “primary grid” and “dual grid,” which is reflected in the permutation matrix WW in Eq. 6. In aPNM, the domain Ω\Omega is decomposed into primary grids Ωip\Omega_i^p in a different way, still utilizing watershed segmentation. Unlike aPLMM, primary grids in aPNM correspond to local geometric constrictions of Ω\Omega, and contact interfaces to geometric enlargements. In pore-network modeling parlance, these are the throats and pores of the void space, respectively. Details of how this decomposition is performed can be found in [24], but briefly, it involves providing interface pixels identified by aPLMM as “seed points” to the watershed algorithm. The result is a decomposition like Figure 1d, where contact interfaces are shared by more than two primary grids and are located within geometric enlargements. For example, the contact interface in Figure 1g (yellow line denoted by Γ1234\Gamma_{1234}) is shared among four primary grids: Ω1p\Omega_1^p, Ω2p\Omega_2^p, Ω3p\Omega_3^p, and Ω4p\Omega_4^p. Dual grids are constructed in exactly the same way as before, namely, by morphologically dilating the pixels comprising each contact interface as illustrated by Figure 1e. Unlike aPLMM, each column of the matrix BB in Eq. 16a for aPNM can have more than two non-zero shape vectors pcjpip_{c_j}^{p_i}.

Geometric monolithic preconditioner

As noted in § 3.2.2, the closure BC ∂nu=0\mathrm{BC}\ \partial_n u=0 is not imposed exactly at contact interfaces during the reduction step of MGM_G, except for the Stokes equations. The deviation grows further with increasing Reynolds number, ReRe, resulting in large errors near interfaces [24] after each application of MGM_G. These errors then convect downstream due to the upwind scheme used for the inertia term in the Navier-Stokes equations. Since the inertia and viscous terms cannot be separated algebraically in the discretized system, exact closure cannot be imposed. In Stokes flow, inertia is absent, so no such separation is needed. In Navier-Stokes flow, exact closure demands geometric information, i.e., access to the code used to assemble the Jacobian matrix in Eq. (3). This would allow defining a modified residual r~wk\widetilde{r}_w^k (instead of rkr^k in Eq. (3)) whose Jacobian J~\widetilde{J} is used (in lieu of JkJ^k) to build MGM_G. The modified residual we propose is:

r~wk=[ρ(∂tuk+w⋅∇uk)−μΔuk+∇pk−ρb∇⋅uk](33)\widetilde{r}_w^k = \begin{bmatrix} \rho\left(\partial_t u_k + w \cdot\nabla u_k\right) - \mu\Delta u_k + \nabla p_k - \rho b \\ \nabla\cdot u_k \end{bmatrix} \tag*{(33)}

where the inertia term u⋅∇uu \cdot\nabla u is linearized around a given velocity ww, called “wind.” To compute uu (and pp) at some ReRe, we set ww to the velocity at a nearby Reynolds number. The closer the ReRe corresponding to ww is to the ReRe at which the solution is sought, the more accurate MGM_G will be. If no adjacent ww is available, the Stokes velocity serves as fallback.

Aside from the linearization in Eq. (33), we also remove the inertia term entirely from the modified residual of those fine-grid faces that lie within a few layers of each contact interface. Figure 3 illustrates such faces by tagging them with black dots. The layer-thickness of tagged faces depends on the size of the upwind stencil used for the inertia term (here, three-point). Removing the inertia term ensures that the reduction steps used to build MGM_G in § 3.2.2 impose ∂nu=0\partial_n u=0 exactly at interfaces. This is highlighted by the Navier-Stokes basis functions depicted in Figure 4, derived from the Jacobian of Eq. (33). Each basis is a column of the matrix BB in Eq. 16a, comprised of two (in PLMM) or four (in PNM) shape vectors associated with the yellow-highlighted interfaces. They belong to primary grids in Figure 1f-Figure 1g and correspond to a high ReRe. For comparison, Figure 4 also shows Stokes bases. Both satisfy ∂nu=0\partial_n u=0 at interfaces (yellow).

Cell and face partition

Figure 3. The inertia (u⋅∇u)(\boldsymbol{u}\cdot\nabla\boldsymbol{u}) term is removed from the modified residual in Eq. (33) of the fine-grid faces that lie within a few layers of each contact interface (Γ12)(\Gamma_{12}). These faces are tagged with black dots. The operation is required to impose the closure BC ∂nu=0\partial_n\boldsymbol{u}=0 exactly at contact interfaces.

Figure 4. Basis functions (pressure and velocity magnitude) corresponding to the MG of gPLMM and gPNM. Each basis is a column of the matrix BB in Eq. 16a, comprised of two (in gPLMM) or four (in gPNM) shape vectors associated with the yellow-highlighted interface. Navier-Stokes bases are built from the Jacobian of the modified residual in Eq. (33) at Re=1.6×104Re=1.6\times10^{4}. The bases belong to primary grids highlighted in Figs. 1f–g}, with BCs p=0p=0 and ∂u/∂n=0\partial\boldsymbol{u}/\partial n=0 on all red lines, and p=1p=1 and ∂u/∂n=0\partial\boldsymbol{u}/\partial n=0 on yellow lines. No-slip BCs hold on the void-solid interface (gray lines).

To summarize, the resulting geometric PLMM and PNM preconditioners, denoted hereafter by gPLMM and gPNM, are constructed from A^\hat{A} set equal to the modified Jacobian J~w\widetilde{J}_w of Eq. (33) (where inertia is disabled for near-interface faces). The RHS vector b^\hat{b} is computed as before from the original (not modified) residual in Eq. (3) (i.e., −rk-r^k). We show in § 8 that gPLMM and gPNM perform better than aPLMM and aPNM. Notice J~w\widetilde{J}_w does not depend on the Newton iteration index kk, meaning MGM_G is build once and reused thereafter. While JkJ^k, used to build aPLMM and aPNM, does depend on kk, we found empirically that building MGM_G once and reusing it for all kk is more efficient.

Coarse-scale Navier-Stokes solver

Here, we demonstrate that the global preconditioner MGM_G for gPLMM and gPNM can also be used as standalone coarse-scale solvers to compute approximate solutions to the steady-state Navier-Stokes equations (i.e., pre-turbulent regime). This approach results in significant computational speedup over exact solvers while maintaining acceptable accuracy in many applications, provided MGM_G corresponds to gPLMM (not gPNM). Extension to dynamic (i.e., turbulent) flow is beyond our scope and left as future work. For Stokes flow, governed by the linear system A^x^=b^\hat{A}\hat{x}=\hat{b}, we showed in [24] that an accurate approximate solution can be obtained from a single application of MG−1M_G^{-1} in Eq. (27):

x^aprx=MG−1b^(34)\hat{x}_{\mathrm{aprx}}=M_G^{-1}\hat{b} \tag*{(34)}

However, a single application is insufficient for the steady-state Navier-Stokes equations due to its nonlinearity, requiring an iterative approach. To achieve speedup, we devise a Newton method that performs iterations only on the coarse-scale (pressure) unknowns, without recourse to the fine grid or any fine-scale problems (local or global):

Jckδck=−rck(35)J_c^k\delta c^k=-r_c^k \tag*{(35)}

The coarse-scale residual and Jacobian are defined as follows:

rck=R^r~k(36)r_c^k=\hat{R}\tilde{r}^k \tag*{(36)}
Jck=R^J~kP^(37)J_c^k=\hat{R}\tilde{J}^k\hat{P} \tag*{(37)}

where r~k\tilde{r}^k and J~k\tilde{J}^k are the modified residual and Jacobian computed from Eq. (33), respectively (setting ∂tuk=0\partial_tu_k=0). However, the omission of subscript ww from both implies that we set w=ukw=u_k in Eq. (33). In other words, r~k\tilde{r}^k and J~k\tilde{J}^k are the same as rkr^k and JkJ^k in Eq. (3), except the inertia term is removed from fine-grid faces near contact interfaces (Figure 3). R^\hat{R} and P^\hat{P} are the effective restriction and effective prolongation matrices, respectively; defined in Eq.19. We build R^\hat{R} and P^\hat{P} by setting A^\hat{A} in Section 3.2.2 to J~w\tilde{J}_{w} for a given wind w\boldsymbol{w} (≠uk\ne\boldsymbol{u}_{k}) at a nearby ReRe. If no such w\boldsymbol{w} is available, the Stokes velocity serves as fallback. To map the course-scale update δck\delta_{c}^{k} onto the fine grid and obtain the approximate fine-scale solution at the next Newton iteration, we execute:

x^aprxk+1=x^aprxk+P^ δck(38)\hat{x}_{aprx}^{k+1}=\hat{x}_{aprx}^{k}+\hat{P}\,\delta_{c}^{k} \tag*{(38)}

Note that R^\hat{R} and P^\hat{P} do not depend on Newton iterations and are built only once. If they were built from JkJ^{k} in Eq. (3) instead of J~w\tilde{J}_{w}, coarse iterations would diverge or yield poor approximate solutions. This is because the closure ∂nu=0\partial_{n}u=0 is only strictly valid at interfaces when J~w\tilde{J}_{w} is used to construct MG\mathrm{MG}. Thus, only MG\mathrm{MG} from gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM} can serve as coarse solvers, not aPLMMa\mathrm{PLMM} or aPNMa\mathrm{PNM}. We show later that the MG\mathrm{MG} of gPLMMg\mathrm{PLMM} is far more accurate than gPNMg\mathrm{PNM}.

Algorithm 1 summarizes the above steps for the proposed coarse-scale solver of the steady-state Navier-Stokes equations. The algorithm consists of an outer loop that gradually increments ReRe from zero to a desired maximum, enveloping the coarse-scale Newton solver as an inner loop. Here, ReRe is incremented by increasing the inlet-boundary pressure while keeping the outlet pressure constant. The outer loop’s job is to provide a good initial guess for Newton to converge (iterations diverge if too far from x^aprx\hat{x}_{aprx}). In computing J~w\tilde{J}_{w}, we set w\boldsymbol{w} to the velocity from the previous ReRe.

Algorithm 1: Coarse-scale solver for steady-state Navier-Stokes equations

Initialize x^aprx=0\hat{x}_{aprx}=0 and w=0\boldsymbol{w}=0

Do Re=0Re=0 to RemaxRe_{max} with increment ΔRe\Delta Re ▷ Increment Reynolds number

Set wind w\boldsymbol{w} in Eq. (33) to velocity from previous ReRe increment

Build coarse preconditioner MG\mathrm{MG} from Jacobian J~w\tilde{J}_{w} of Eq. (33) ▷ This yields R^\hat{R} and P^\hat{P}

Compute coarse-scale residual rc0r_{c}^{0} and Jacobian Jc0J_{c}^{0} from Eq.25

Initialize Newton to x^aprx0=x^aprx\hat{x}_{aprx}^{0}=\hat{x}_{aprx} from previous ReRe increment

Do k=0k=0 to kmaxk_{max} ▷ Coarse-scale Newton iteration

Compute coarse-scale Newton update δck\delta_{c}^{k} by solving Eq. (35)

Update fine-scale approximate solution x^aprxk\hat{x}_{aprx}^{k} using Eq. (38)

Update coarse-scale residual rck+1r_{c}^{k+1} and Jacobian Jck+1J_{c}^{k+1} from Eq.25

If ∥rck+1∥/∥rc0∥<10−6\lVert r_{c}^{k+1}\rVert/\lVert r_{c}^{0}\rVert<10^{-6}, exit

End do

Set x^aprx\hat{x}_{aprx} to converged approximate solution

End do

Remark 2. For the linear Stokes equations, Algorithm 1 converges in only one Newton iteration and the solution equals Eq. (34) but with M−1=P^(R^A^P^)−1R^M^{-1}=\hat{P}(\hat{R}\hat{A}\hat{P})^{-1}\hat{R} (not Eq. (27)). Another way to formulate the coarse-scale Jacobian given by Eq.25b would have been Jck=WC(WTJ~kW)WTJ_{c}^{k}=WC(W^{\mathsf{T}}\tilde{J}^{k}W)W^{\mathsf{T}}, but the presence of the column-sum operator C(⋅)C(\cdot) prevents Newton from converging in only one step, which is why we opted for the form given by Eq.25b. The simple proof of this fact involves tracing one Newton step of Algorithm 1, revealing that (R^J^kP^)−1Jck=I(\hat{R}\hat{J}^{k}\hat{P})^{-1}J_{c}^{k}=I must hold for one-step convergence.

Problem set

In the following sections, we first test the coarse-scale solver in Algorithm 1 against the exact solution of the steady-state Navier-Stokes equations for the 2D and 3D porous geometries in Figure 5. Both gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM} are considered as the basis for building MG\mathrm{MG} for the solver. The domains include a monodisperse and spatially disordered disk pack [25] (GLD4), a polydisperse and spatially disordered disk pack [25] (PD4), a 2D representation of Berea sandstone [37] (Berea), and a 3D Gyroid whose void-solid interface Γw\Gamma_{w} is described by the following equation [38]:

Figure 5. Schematic of 2D and 3D porous geometries considered for testing the proposed preconditioners and the coarse-scale solver.

sin⁡(12x)cos⁡(12y)+sin⁡(12y)cos⁡(12z)+sin⁡(12z)cos⁡(12x)=0(39)\sin(12x)\cos(12y)+\sin(12y)\cos(12z)+\sin(12z)\cos(12x)=0 \tag*{(39)}

After gaining some intuition into the accuracy of gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM} as coarse-scale solvers, we test the algebraic (aPLMMa\mathrm{PLMM} and aPNMa\mathrm{PNM}) and geometric (gPLMMg\mathrm{PLMM} and gPNMg\mathrm{PNM}) monolithic preconditioners proposed for both steady-state and unsteady forms of the Navier-Stokes equations. The test domains include GLD4, PD4, Berea, and a 3D packing of non-spherical grains [24] (Granular). Disk positions in PD4 and GLD4 are identical, differing only in the disk sizes. We benchmark aaPLMM, aaPNM, ggPLMM and ggPNM against each other and block-triangular preconditioners bbAMG, bbPLMM, and bbPNM. The latter were described in § 1 and detailed in [24]. We utilize the scaled-BFBt approximation of the Schur-complement matrix in Eq. (5), which exhibits robust performance in complex geometries [24]. The difference between bbAMG, bbPLMM, and bbPNM lies in the choice of prolongation (transposition yields restriction) matrices used to precondition the elliptic sub-systems arising from the Schur-complement approximation. bbPLMM and bbPNM are built from the same shape and correction vectors used to formulate aaPLMM and aaPNM. To build bbAMG, we use the amg.m code from the iFEM GitHub repository [39], with settings identical to those in [24].

Each domain is decomposed into primary and dual grids corresponding to the randomly colored regions in Figure 6. These are used by aaPLMM, aaPNM, ggPLMM, ggPNM, bbPLMM, and bbPNM. Table 1 summarizes each domain’s dimensions and fine/coarse-grid information, including the number of cell-pressure unknowns (ncn_c), face-velocity unknowns (nfn_f), primary grids (NpN^p), and dual grids (Nd=NcN^d = N^c) for both PLMM and PNM. The NpN^p for PLMM roughly equals the NcN^c for PNM because primary grids in PLMM correspond to contact interfaces (or dual grids) in PNM and vice versa.

Domain size (cm)ncn_cnfn_fNpN^p, PLMMNcN^c, PLMMNpN^p, PNMNcN^c, PNM
PD42×12 \times1610,0401,230,924174294291172
GLD42×12 \times1717,0971,447,556186257260178
Berea1.45×1.151.45 \times1.15931,3961,877,760203255302192
Granular0.9×1×0.90.9 \times1 \times0.9375,9531,265,1999969064796
Gyroid1×1.5×11 \times1.5 \times1616,4001,947,4682110310916

Table 1. Geometric and fine/coarse-grid information of the domains in Figure 5. They include the domain size, number of cell-pressure unknowns (ncn_c), number of face-velocity unknowns (nfn_f), and number of primary (NpN^p) and dual (Nd=NcN^d = N^c) grids for PLMM- and PNM-based preconditioners.

Figure 6. Decomposition of the porous geometries shown in Figure 5 into primary and dual grids used by the coarse-scale solver and the monolithic and block preconditioners considered herein. Each primary grid and dual grid is illustrated by a randomly colored region.

To compute Reynolds number Re=ρUl/μRe = \rho Ul/\mu, we define the characteristic velocity as the interstitial velocity U=UD/ϕU = U_D/\phi, where UDU_D is the Darcy velocity (= flowrate divided by cross-sectional area) and ϕ\phi is porosity. The characteristic length is l=Vs/Awl=V_s/A_w, where VsV_s is the total solid volume and AwA_w is the void-solid interfacial area ∣Γw∣|\Gamma_w|. In all simulations, we set the fluid density to ρ=1\rho= 1 g/cc and the dynamic viscosity to μ=2×10−4\mu= 2 \times10^{-4} Poise for PD4, 1.2×10−41.2 \times10^{-4} Poise for GLD4, 1×10−41 \times10^{-4} Poise for Berea, and 1×10−31 \times10^{-3} Poise for Granular and Gyroid. The BCs imposed were described in § 2, which include setting the inlet pressure pinp_{in} at the left boundary and the outlet pressure poutp_{out} at the right.

To validate our fine-grid Navier-Stokes solver, we simulate the classic problem of flow around a circular or square obstacles at various Reynolds numbers in Appendix § 12. These simulations show that our solver produces accurate drag coefficients compared to literature values, with comparable pressure, velocity-magnitude, and vorticity fields.

Testing the coarse-scale solver

We test the accuracy of the coarse-scale solver outlined in Algorithm 1 for the steady-state Navier-Stokes equations by comparing the pressure and velocity magnitudes associated with the approximate solution x^aprx\hat{x}_{\mathrm{aprx}} produced to that of the exact solution. To increment ReRe in Algorithm 1, we progressively increase the inlet pressure pinp_{in} by 10% of its previous value while keeping the outlet pressure poutp_{out} fixed at zero. The initial value of pinp_{in} is set to 10−310^{-3} dynes/cm2^2. We increment ReRe in this way until the coarse-scale Newton loop ceases to converge within 50 iterations, which we interpret as the onset (or vicinity) of turbulent instabilities beyond which a steady-state solution is difficult to compute. Recall Algorithm 1 uses the converged solution from the previous ReRe increment as the initial guess for Newton in the current ReRe increment. In addition to pressure and velocity fields, which are fine-scale information, we compute the permeability KK of each domain versus ReRe, which is a bulk property:

K=μLUDΔp(40)K = \frac{\mu L U_D}{\Delta p} \tag*{(40)}

The UDU_D, Δp\Delta p, and LL denote Darcy velocity, pin−poutp_{\mathrm{in}}-p_{\mathrm{out}}, and inlet-to-outlet distance of the domain, respectively. Figs.7–8 compare approximate solutions from the coarse-scale solver to exact solutions at the highest ReRe reachable by the coarse-scale solver. Results are shown for the PD4, GLD4, Berea and Gyroid domains. Approximate solutions from both ggPLMM and ggPNM are included, where the corresponding MG\mathrm{M}_G (or equivalently R^\hat{\mathrm{R}} and R^\hat{\mathrm{R}}) is utilized in Algorithm 1. We observe very good agreement between approximate pressure and velocity-magnitudes from ggPLMM versus the exact solutions. Approximate solutions via ggPNM are significantly inferior in accurately capturing the flow field. These observations are confirmed further by Figure 9, where comparisons of KK versus ReRe are presented.

Figure 9. Errors in pressure (EP2E_P^2), velocity magnitude (Eu2E_u^2), and permeability (EKE_K) versus Reynolds number (ReRe) for approximate solutions from the coarse-scale solver in Algorithm 1 based on gPLMM and gPNM. Results correspond to the PD4, GLD4, Berea, and Gyroid domains. The approximate and exact permeabilities (KK) are plotted with dashed lines on the right. The former overestimates KK due to vortex suppression.

To quantify errors in the approximate solutions, we use the following metrics by [24, 25]:

E2ξ≡(1∣Ω∣∫Ω(Epξ)2 dΩ)1/2Epξ≡∣ξt−ξc∣sup⁡Ω∣ξt∣×100EK≡∣Kt−Kc∣∣Kt∣×100(41)E_2^\xi\equiv\left(\frac{1}{|\Omega|}\int_\Omega(E_p^\xi)^2\,\mathrm{d}\Omega\right)^{1/2} \qquad E_p^\xi\equiv\frac{|\xi_t-\xi_c|}{\sup_\Omega|\xi_t|}\times100 \qquad E_K \equiv\frac{|K_t-K_c|}{|K_t|}\times100 \tag*{(41)}

where ξ\xi is a placeholder for either pressure, pp, or velocity magnitude, ∣u∣|\mathbf{u}|. Subscripts cc and tt denote the approximate solution obtained from the coarse-scale solver and the “true” (or exact) solution, respectively. From left to right, the metrics in Eq. (41) yield the L2L_2, pointwise, and permeability errors; all expressed in percentages of the true value.

Figure 9 plots E2pE_2^p, E2∣u∣E_2^{|u|}, and EKE_K versus ReRe for all domains, where we see these errors increase with Reynolds number. Moreover, errors associated with ggPNM are much larger (up to 20 times) than those with ggPLMM. For the coarse-solver based on ggPLMM, errors are bounded as follows for all domains: E2p<3%E_2^p < 3\%, E2∣u∣<6%E_2^{|u|} < 6\% in 2D and <18%< 18\% in 3D, and EK<30%E_K < 30\%, which are acceptable in many engineering applications. We note the approximate velocity field of the coarse-scale solver is conservative in a “weak” sense, i.e., integrated flux along each interface is continuous. Figure 10 depicts pointwise errors of the pressure and velocity-magnitude in Figure 7–Figure 8 for the PD4 and Gyroid domains, which

Comparison of approximate pressure and velocity-magnitude fields for PD4 and GLD4

Figure 7. Comparison of approximate pressure and velocity-magnitude fields obtained from the coarse-scale solver in Algorithm 1 against exact solutions. Results correspond to the steady-state Navier-Stokes equations on PD4 at Re=3.1×103Re = 3.1 \times10^3 and GLD4 at Re=1.1×104Re = 1.1 \times10^4.

Comparison of approximate pressure and velocity-magnitude fields for Exact, gPLMM, and gPNM on Berea and Gyroid

Figure 8. Comparison of approximate pressure and velocity-magnitude fields obtained from the coarse-scale solver in Algorithm 1 against exact solutions. Results correspond to the steady-state Navier-Stokes equations on Berea at Re=1.6×104Re = 1.6 \times10^{4} and Gyroid at Re=4.7×103Re = 4.7 \times10^{3}.

Figure 10. Pointwise errors in pressure (EpE^p) and velocity magnitude (EulE^{u_l}) for approximate solutions from the coarse-scale solver in Algorithm 1 based on gPLMM and gPNM. Results correspond to PD4 at Re=3.1×103Re = 3.1 \times10^3 and Gyroid at Re=4.7×103Re = 4.7 \times10^3, whose field plots are shown in Figure 7–Figure 8.

confirm the observations just described. gPLMM errors are lower than gPNM, and under 1% for much of the domain. Other domains behave similarly and omitted for brevity. Unlike Stokes flow, where errors localize more strongly near contact interfaces [24] (high-frequency), Navier-Stokes exhibits errors that are comparatively global (low-frequency).

An interesting observation from Figure 9 is that the permeability predicted by the gPLMM coarse-scale solver is always larger than the true permeability computed from the exact solution. This is because the imposition of the closure BC ∂nu=0\partial_n u = 0 suppresses vortex formation, which is a key mechanism for dissipating energy, hence reducing flowrate. This is illustrated by Figure 11, where streamlines at low and high ReRe are drawn inside a portion of the domain shown in Figure 1a. The suppression of vortices is, incidentally, the reason why errors in Figure 9 grow with ReRe.

Figure 11. Schematic of flow streamlines (white lines) near a contact interface (yellow line). The velocity field is computed from the gPLMM coarse-scale solver and the exact solution. Results are shown for low and high ReRe corresponding to a portion of the domain in Figure 1.

Testing the preconditioners

We apply all preconditioners, including aaPLMM/aaPNM, ggPLMM/ggPNM, bbPLMM/bbPNM, and bbAMG, within right-preconditioned GMRES. We declare convergence when the normalized residual satisfies ∥A^x^−b^∥/∥b^0∥<10−9\lVert\hat{A}\hat{x}-\hat{b}\rVert/\lVert\hat{b}_0\rVert< 10^{-9}, where b^0\hat{b}_0 is the residual of the steady-state (or time-dependent if velocity at prior time step is set to zero) Navier-Stokes equations at the origin, i.e., r(u=0,p=0)r(u=0,p=0). This captures the magnitude of nonhomogeneous BCs. We use ∥b^0∥=∥r0∥\lVert\hat{b}_0\rVert=\lVert r^0\rVert for normalization instead of ∥b^∥=∥rk∥\lVert\hat{b}\rVert=\lVert r^k\rVert because the latter decreases with Newton iterations, leading to excess GMRES iterations at large kk. We run simulations in series on an Intel® Xeon® Gold 6248R CPU @ 3.00 GHz machine.

Steady-state Navier-Stokes equations

Similar to § 7, we increment ReRe by progressively increasing the inlet pressure pinp_{\mathrm{in}} from 1 dynes/cm2^2 using constant increments of Δpin=1\Delta p_{\mathrm{in}}=1 for PD4, 0.5 for GLD4 and Berea, and 2 for the Granular domain, while keeping the outlet pressure at pout=0p_{\mathrm{out}}=0. Unlike § 7, fine-scale (not coarse-scale) solutions are computed at each ReRe by performing Newton iterations on the fine grid, and GMRES iterations at each Newton iteration. The initial Newton guess at any given ReRe is the solution from the previous ReRe increment. To probe the necessity of rebuilding the aaPLMM/aaPNM, ggPLMM/ggPNM, and bbPLMM/bbPNM preconditioners as ReRe evolves, we test two variants of each: (1) Stokes-based, where the preconditioners are built from the Stokes equations once and reused across all subsequent ReRe; and (2) Navier-Stokes-based, where the preconditioners are rebuilt from scratch at the start of every ReRe increment; specifically, before the Newton loop is entered, but not during. Following the notation in § 1, we denote Stokes-based preconditioners with subscript “S” and Navier-Stokes-based preconditioners with “NS.” For example, bbPLMMS_{\mathrm{S}} is the block PLMM preconditioner based on the Stokes equations, and aaPNMNS_{\mathrm{NS}} is the algebraic monolithic PNM preconditioner that is continuously updated based on the Navier-Stokes equations. Since ggPLMMS=a_{\mathrm{S}}=aPLMMS_{\mathrm{S}} and ggPNMS=a_{\mathrm{S}}=aPNMS_{\mathrm{S}}, we use ggPLMM and ggPNM (no subscript) to denote Navier-Stokes-based preconditioners.

First, let us demonstrate that block preconditioners are disqualified from further consideration due to their severely poor performance. Figure 12 compares the GMRES convergence observed for the monolithic and block preconditioners in the first Newton iteration of the first ReRe increment. This is the simplest system to solve, as higher ReRe poses further challenges to GMRES (shown later). Compared to aaPLMM and aaPNM, the block preconditioners bbPLMM, bbPNM, and bbAMG are extremely slow to converge with long periods of initial stagnation. For bbAMG, stagnation is permanent. By contrast, monolithic preconditioners converge robustly and at least an order of magnitude faster. This observation is

Figure 12. Normalized linear-system residual versus GMRES iterations for the first Newton step of the first ReRe increment (Re1=9.0×103Re_1 = 9.0 \times10^3). Results correspond to different block and monolithic preconditioners applied to the steady-state Navier-Stokes equations on all domains.

insensitive to whether block preconditioners are Stokes-based or Navier-Stokes-based. In [24], the authors observed better performance by bbPLMM and bbPNM for the Stokes equations than what is observed here for the Navier-Stokes equations. However, even there, aaPLMM and aaPNM were superior, and bbAMG was prone to stagnation, consistent with Figure 12. Table 2 lists the total wall-clock times (WCTs) associated with the first three ReRe increments of the PD4 domain, using different preconditioners. The WCTs include contributions from the costs of building MGM_G, building MLM_L, and the self-time of GMRES. We see that block preconditioners take roughly 1-2 orders of magnitude longer than the monolithic preconditioners. Hence, we exclude bbPLMM, bbPNM, and bbAMG from all subsequent analysis.

bbPNMS_{\mathrm{S}}bbPNMNS_{\mathrm{NS}}bbPLMMS_{\mathrm{S}}bbPLMMNS_{\mathrm{NS}}aaPNMS_{\mathrm{S}}aaPNMNS_{\mathrm{NS}}aaPLMMS_{\mathrm{S}}aaPLMMNS_{\mathrm{NS}}
Re1=9.0×103Re_1 = 9.0 \times10^340,08887,34522,29544,4786581,158566758
Re2=1.2×104Re_2 = 1.2 \times10^448,796110,93431,01165,7896741,800563741
Re3=1.4×104Re_3 = 1.4 \times10^462,347137,52949,125102,8868242,405643769

Table 2. Total wall-clock times (seconds) associated with the first three ReRe increments in solving the steady-state Navier-Stokes equations on the PD4 domain. They include the costs of constructing MGM_G, constructing MLM_L, and the self-time of GMRES for different preconditioners in GMRES.

Figure 13 shows the number of Newton and GMRES iterations as a function of ReRe for the PD4, GLD4, Berea, and Granular domains. GMRES iterations correspond to the first Newton step of each ReRe, where GMRES struggles the most compared to subsequent Newton steps. Notice that the number of Newton iterations (between 2 to 6) is almost constant with respect to ReRe, which is a direct result of using the converged solution from the prior ReRe as the initial guess for the current ReRe. By contrast, GMRES iterations increase steadily with ReRe, indicative of A^x^=b^\hat{\mathbf{A}}\hat{\mathbf{x}}=\hat{\mathbf{b}} becoming more challenging to solve at higher Reynolds numbers. The best-performing preconditioner is consistently ggPLMM across all domains, outperforming aaPLMMS/NS_{\mathrm{S/NS}} by up to a factor of ∼2\sim2, and aaPNMS/NS_{\mathrm{S/NS}} by up to a factor of ∼4\sim4. The only exception is Granular, where ggPLMM and aaPLMMS/NS_{\mathrm{S/NS}} are comparable, and aaPNMS/NS_{\mathrm{S/NS}} slightly outperforms ggPLMM at high (but not low) ReRe. Interestingly, ggPNM performs as poorly as aaPNMS/NS_{\mathrm{S/NS}}, implying that the closure BC ∂nu=0\partial_n u=0 is only meaningful for ggPLMM, but not ggPNM. Moreover, comparing aaPLMMS_{\mathrm{S}} to aaPLMMNS_{\mathrm{NS}}, we see little difference in performance, implying the Stokes-based preconditioner is more attractive because it is built only once. As a general rule, preconditioners based on PLMM are seen to perform far better than those based on PNM.

Figure 13. (Top row) Number of Newton iterations versus ReRe. (Bottom row) Number of GMRES iterations of the first Newton step versus ReRe. Results belong to different preconditioners based on PLMM and PNM applied to the steady-state Navier-Stokes equations in all domains. Prefix aa means “algebraic,” and gg means “geometric.” Subscripts “S” and “NS” imply preconditioners are built from Stokes or Navier Stokes, respectively.

Figure 13 also includes the performance of GMRES preconditioned by only the smoothers of PLMM and PNM, i.e., MLM_L not paired with MGM_G. We see the PLMM smoother performs better than the PNM smoother, but neither beats their respective monolithic preconditioners, where MLM_L is paired with MGM_G. This confirms that such pairing is necessary.

Figure 14 depicts total wall-clock times (WCT), TtotT_{\mathrm{tot}}, associated with computations in Figure 13 versus ReRe. This includes costs corresponding to building MGM_G (TMGT_{M_G}), building MLM_L (TMLT_{M_L}); here LU-decomposition of local systems in the additive-

Figure 14. Total wall-clock times (WCT; in seconds) spent solving the steady-state Navier-Stokes equations (TtotT_{\mathrm{tot}}) versus ReRe, for different preconditioners based on PLMM and PNM (built from Stokes and Navier Stokes) in all domains. TtotT_{\mathrm{tot}} consists of the costs of building MGM_{\mathrm{G}} (TMGT_{\mathrm{MG}}; if monolithic), building MLM_{\mathrm{L}} (TMLT_{\mathrm{ML}}), and self-time of GMRES (TsolT_{\mathrm{sol}}). The breakdown of TtotT_{\mathrm{tot}} into TMGT_{\mathrm{MG}}, TMLT_{\mathrm{ML}}, and TsolT_{\mathrm{sol}} is illustrated in fractions of TtotT_{\mathrm{tot}}.

Schwarz smoothers), and self-time of GMRES (TsolT_{\mathrm{sol}}). Results belong to the aPLMM, aPNM, gPLMM, gPNM, and MLM_{\mathrm{L}} preconditioners. The breakdown of TtotT_{\mathrm{tot}} into TMGT_{\mathrm{MG}}, TMLT_{\mathrm{ML}}, and TsolT_{\mathrm{sol}} is shown as fractions of TtotT_{\mathrm{tot}} in Figure 14. We see in all cases, TsolT_{\mathrm{sol}} dominates TtotT_{\mathrm{tot}}, making the relative ranking among preconditioners in terms of TtotT_{\mathrm{tot}} similar to that already discussed in Figure 13 in terms of GMRES iterations. To quantify speedup, we normalize the TtotT_{\mathrm{tot}} of all preconditioners against that of gPLMM in Figure 15. Compared to gPLMM, aPLMMS/NSa\mathrm{PLMM}_{\mathrm{S/NS}} are 2-3 times slower, aPNMS/NSa\mathrm{PNM}_{\mathrm{S/NS}} are ∼10\sim10 times slower, the MLM_{\mathrm{L}} of PLMM is 3-5 times slower, and the MLM_{\mathrm{L}} of PNM is 10-20 times slower. The only exception is 3D Granular, whose TMGT_{\mathrm{MG}} constitutes a sizable fraction of TtotT_{\mathrm{tot}} due to the presence of a few large primary grids, making the continuous updating of MGM_{\mathrm{G}} versus ReRe in gPLMM more costly than the one-time cost of construction in aPLMMSa\mathrm{PLMM}_{\mathrm{S}}. Once again, aPLMMSa\mathrm{PLMM}_{\mathrm{S}} and aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} have comparable TtotT_{\mathrm{tot}} across all domains, except Granular for reasons just stated. This makes aPLMMSa\mathrm{PLMM}_{\mathrm{S}} more attractive than aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} as it is not rebuilt at every ReRe increment.

Figure 15. Relative performance of all monolithic and smoother-only preconditioners in Fig.14 measured against gPLMM for the steady-state Navier-Stokes equations. Relative performance is defined as the ratio of total WCT (TtotT_{\mathrm{tot}}) for the preconditioner in question over that of gPLMM.

To understand why gPLMM outperforms its algebraic counterparts aPLMMS/NSa\mathrm{PLMM}_{\mathrm{S/NS}}, and why PLMM-based preconditioners outperform PNM-based ones, we visualize the spectrum of the error-propagation matrix E:

EG=I−MG−1A^,EL=I−ML−1A^⇒E=ELEG(42)E_{\mathrm{G}} = I - M_{\mathrm{G}}^{-1}\hat{A}, \quad E_{\mathrm{L}} = I - M_{\mathrm{L}}^{-1}\hat{A} \quad\Rightarrow\quad E = E_{\mathrm{L}}E_{\mathrm{G}} \tag*{(42)}

for gPLMM, gPNM, aPLMMS/NSa\mathrm{PLMM}_{\mathrm{S/NS}}, and aPNMS/NSa\mathrm{PNM}_{\mathrm{S/NS}} in Figure 16. Each spectrum consists of the 500 largest eigenvalues of E for the PD4 domain at Re=3.9×104Re = 3.9 \times10^{4} (other domains yield similar results). We see that the spectrum of gPLMM is clustered closest to the origin of the complex plane and lies inside the unit circle, explaining its superior GMRES convergence. Next in ranking are aPLMMS/NSa\mathrm{PLMM}_{\mathrm{S/NS}}, which have similar performance. While aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} is more clustered near the origin than aPLMMSa\mathrm{PLMM}_{\mathrm{S}}, the former is plagued by rogue eigenvalues outside the unit circle slowing down convergence. Lastly, aPNMS/NSa\mathrm{PNM}_{\mathrm{S/NS}} and gPNM have the largest spectral radii, thus the slowest GMRES convergence.

Figure 16. Spectra (500 largest eigenvalues) of the error-propagation matrices EE (blue dots), EGE_G (green dots), and ELE_L (red dots) in Eq. (42). Results belong to preconditioners aPLMMS_S and aPNMS_S (left column), aPLMMNS_{NS} and aPNMNS_{NS} (middle column), and gPLMM and gPNM (right column) applied to the steady-state Navier-Stokes equations on the PD4 domain at Re=3.9×104Re=3.9 \times10^4.

In addition to E’s spectrum, Figure 16 shows the spectra of EGE_{\mathrm{G}} and ELE_{\mathrm{L}} defined by Eq. (42). These correspond to the error-propagation matrices of MGM_{\mathrm{G}} and MLM_{\mathrm{L}}, respectively. Eigenvalues of ELE_{\mathrm{L}} lie inside the unit circle for both the PLMM and PNM smoothers, with many very close to one, confirming the smoothers alone are inadequate as preconditioners. For aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}, Figure 16 shows the eigenvalues of EGE_{\mathrm{G}} consist of zero or one, because EGE_{\mathrm{G}} is a projection by Proposition 3.1 and our simplification for MGM_{\mathrm{G}} in Remark 1. For gPLMM, gPNM, aPLMMSa\mathrm{PLMM}_{\mathrm{S}}, and aPNMSa\mathrm{PNM}_{\mathrm{S}}, EGE_{\mathrm{G}}’s eigenvalues lie outside the unit circle, because the A^\hat{A} used in Eq. (42) is different from the Jacobian used to construct MGM_{\mathrm{G}}. What is interesting is that the spectral radius of E for gPLMM and aPLMMSa\mathrm{PLMM}_{\mathrm{S}} (but not gPNM and aPNMSa\mathrm{PNM}_{\mathrm{S}}) is smaller than one, despite the spectral radius of EGE_{\mathrm{G}} being larger than one. The opposite is true for aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} and aPNMNSa\mathrm{PNM}_{\mathrm{NS}}, where the spectral radius of E is larger than one despite both EGE_{\mathrm{G}} and ELE_{\mathrm{L}} having spectra contained within the unit disk. The latter is possible because both EGE_{\mathrm{G}} and ELE_{\mathrm{L}} are non-normal matrices, with non-orthogonal eigenvectors [40].

Unsteady-state Navier-Stokes equations

We focus next on the unsteady-state Navier-Stokes equations and the turbulent flow regimes that result from it. To ensure flow is turbulent at all tt, we set the IC equal to the steady-state solution from the previous section at the highest simulated ReRe. The BCs are identical to the steady-state simulations in Section 8.1, where the inlet pressure pinp_{\mathrm{in}} is incrementally increased while the outlet pressure is pout=0p_{\mathrm{out}} = 0. The only difference here is that a timescale is associated with the growth of pinp_{\mathrm{in}}. Specifically, we take one Δpin\Delta p_{\mathrm{in}} increment per Δt=0.2\Delta t = 0.2 sec, where Δpin=20\Delta p_{\mathrm{in}} = 20 dynes/cm2^{2} in all 2D domains and Δpin=30\Delta p_{\mathrm{in}} = 30 dynes/cm2^{2} in the 3D Granular domain. Within each 0.2 sec interval, during which pinp_{\mathrm{in}} is constant, smaller time steps dtdt are taken to capture the turbulent details of the flow. The dtdt are taken adaptively, based on how fast the residual norm evolves. We test the performance of the gPLMM, aPLMMS/NSa\mathrm{PLMM}_{\mathrm{S/NS}}, and aPNMS/NSa\mathrm{PNM}_{\mathrm{S/NS}} preconditioners on the PD4, GLD4, Berea, and Granular domains (see Figure 5). We exclude gPNM from consideration based on its poor performance in § 8.1. Navier-Stokes-based preconditioners (all except aPLMMS_S and aPNMS_S) are rebuilt at the beginning of every ReRe (or pinp_{\mathrm{in}}) increment, not in between dtdt steps or Newton iterations. Since dynamic simulations are computationally expensive, underperforming preconditioners are terminated prematurely whenever it is clear they are not competitive. Finally, GMRES iterations preconditioned by aPNMS/NS_{S/NS} diverge or stagnate in the Granular domain, even for very small dtdt. This is why aPNMS/NS_{S/NS} results for Granular appear absent from Figure 18–Figure 20.

Figure 18. (Top row) Number of time steps dtdt, taken within each ReRe increment, versus ReRe. (Middle row) Number of Newton iterations versus ReRe, averaged over each ReRe increment. (Bottom row) Number of GMRES iterations of the first Newton step versus ReRe, averaged over each ReRe increment. Results belong to different preconditioners based on PLMM and PNM applied to the unsteady-state Navier-Stokes equations in all domains. Prefix a means “algebraic,” and g means “geometric.” Subscripts “S” and “NS” imply preconditioners are built from Stokes or Navier Stokes, respectively.

Image not extracted

Figure 20. Relative performance of all monolithic and smoother-only preconditioners in Figure 19 measured against gPLMM for the unsteady-state Navier-Stokes equations. Relative performance is defined as the ratio of total WCT (TtotT_{\mathrm{tot}}) for the preconditioner in question over that of gPLMM.

To visualize the complex nature of turbulent flow, Figure 17 depicts snapshots of fluid pressure, velocity magnitude, and vorticity magnitude (∣∇×u∣|\nabla\times\mathbf{u}|) at the highest simulated ReRe in all domains. Compared to steady-state flow in Figure 7–Figure 8, we see many more circulation zones and chaotic patterns. Figure 18 shows that the number of dtdt time steps, taken within each ReRe increment, increases with ReRe, indicating progressively smaller dtdt is required to capture the growing intricacies of turbulent flow. The number of Newton and GMRES iterations per dtdt step (averaged over each ReRe increment) are also depicted as a function of ReRe. GMRES iterations correspond to the first Newton step of each ReRe, where GMRES struggles the most compared to later Newton steps. Similar to § 8.1, Newton iterations are constant (∼5\sim5) versus ReRe. However, unlike § 8.1 where GMRES iterations grow with ReRe, they remain nearly constant here. We attribute this to the small dtdt used to discretize ∂tu\partial_t\mathbf{u} in Eq. 1, rendering the (1,1)(1,1)-block of A^\hat{A} in Eq. (3) diagonally dominant. At the limit of large dtdt, the ∂tu\partial_t\mathbf{u} term becomes negligible and the steady-state results of Figure 13 are recovered.

Spatial distributions of fluid pressure, velocity magnitude, and vorticity magnitude for the unsteady-state Navier–Stokes equations

Figure 17. Spatial distributions of fluid pressure, velocity magnitude, and vorticity magnitude for the unsteady-state Navier–Stokes equations solved on the domains in Figure 5, namely, PD4 at Re=1.3×105Re = 1.3 \times10^{5}, GLD4 at Re=5.5×104Re = 5.5 \times10^{4}, Berea at Re=4.4×104Re = 4.4 \times10^{4}, and Granular at Re=1.8×104Re = 1.8 \times10^{4}.

Similar to § 8.1, Figure 18 suggests that the best-performing preconditioner is gPLMM across all domains. However, unlike § 8.1, aPLMMNS_{NS} is a very close second, slower by only <1.5 times in 2D and <2.8 times in the 3D Granular. By contrast, gPLMM is faster than aPNMNS_{NS} by <2 times in 2D domains (3D diverged), and than aPLMMS_S, aPNMS_S, and PLMM/PNM smoothers by >10 times in 2D and <2 times in 3D Granular. Clearly, preconditioners based on Navier Stokes (gPLMMNS_{NS}, aPLMMNS_{NS}, aPNMNS_{NS}) outperform those based on Stokes (aPLMMS_S, aPNMS_S) by about an order of magnitude. This implies that rebuilding the monolithic preconditioners at the start of every ReRe increment is necessary to efficiently model turbulent flow. Another clear observation is that preconditioners based on PLMM perform twice as fast as those based on PNM. Lastly, smoother-only preconditioners are extremely slow (except in Granular) indicating a pairing with a coarse preconditioner MGM_{\mathrm{G}} is necessary for rapid convergence.

Figure 19 plots the total wall-clock times (TtotT_{\mathrm{tot}}) spent on computations versus ReRe for all domains. The WCTs of all dtdt steps taken within each ReRe increment are summed for better representation of cost. The overall rise in TtotT_{\mathrm{tot}} with ReRe is due to the need for smaller dtdt in simulating turbulent flow at higher ReRe. By the same token, TsolT_{\mathrm{sol}} also increases with ReRe but the associated cost-per-dtdt is roughly constant, as evidenced by the constant number of GMRES iterations versus ReRe in Figure 18. Unlike § 8.1, TtotT_{\mathrm{tot}} here is dominated by the cost of building the smoother (TMLT_{\mathrm{ML}}; LU-decomposition of local systems in the additive-Schwarz smoothers), especially for ggPLMM. The cost of rebuilding MGM_{\mathrm{G}} is negligible in contrast. To better visualize speedup, Figure 20 normalizes the TtotT_{\mathrm{tot}} of all preconditioners against that of ggPLMM. Once again, we see that the performance of aaPLMMNS_{\mathrm{NS}} is on par with ggPLMM in 2D but slower by <3.4<3.4 times in 3D Granular. Moreover, ggPLMM is faster than aaPNMNS_{\mathrm{NS}} by <3<3 times, aaPLMMS_{\mathrm{S}} by <6<6 times, aaPNMS_{\mathrm{S}} by <9<9 times, PLMM smoother by <15<15 times, and the PNM smoother by <30<30 times. Other trends regarding the relative ranking of preconditioners are consistent with observations already discussed in relation to GMRES iterations in Figure 18.

Figure 19. Total wall-clock times (WCT; in seconds) spent solving the unsteady-state Navier-Stokes equations (TtotT_{\mathrm{tot}}) versus ReRe, for different preconditioners based on PLMM and PNM (built from Stokes and Navier Stokes) in all domains. TtotT_{\mathrm{tot}} consists of the costs of building MGM_{\mathrm{G}} (TMGT_{\mathrm{MG}}; if monolithic), building MLM_{\mathrm{L}} (TMLT_{\mathrm{ML}}), and self-time of GMRES (TsolT_{\mathrm{sol}}). The breakdown of TtotT_{\mathrm{tot}} into TMGT_{\mathrm{MG}}, TMLT_{\mathrm{ML}}, and TsolT_{\mathrm{sol}} is illustrated in fractions of TtotT_{\mathrm{tot}}.

Figure 21 visualizes the 500 largest eigenvalues of the error-propagation matrix EE in Eq. (42) for the PD4 domain at

Image not extracted

Figure 21. Spectra (500 largest eigenvalues) of the error-propagation matrices EE (blue dots) and ELE_{\mathrm{L}} (red dots) in Eq. (42). Results belong to preconditioners aPLMMS and aPNMS (left column), aPLMMNS and aPNMNS (middle column), and gPLMM and gPNM (right column) applied to the unsteady-state Navier-Stokes equations on the PD4 domain at Re=1.3×105Re = 1.3 \times10^{5}.

Re=1.3×105Re = 1.3 \times10^{5}. Included is also the spectrum of ELE_{\mathrm{L}}, but not EGE_{\mathrm{G}} because most of its eigenvalues for gPLMM, gPNM, aPLMMS_{\mathrm{S}} and aPNMS_{\mathrm{S}} lie far outside the unit circle. However, the EGE_{\mathrm{G}} of aPLMMNS_{\mathrm{NS}} and aPNMNS_{\mathrm{NS}} has eigenvalues that are either zero or one (see discussion in § 8.1). The spectral radius of EE for gPLMM and aPLMMNS_{\mathrm{NS}} are similar, which explains their comparable GMRES convergence in Figure 18. The same observation holds for gPNM versus aPNMNS_{\mathrm{NS}}. Notice also that the Navier-Stokes-based preconditioners (aPLMMNS_{\mathrm{NS}}/aPNMNS_{\mathrm{NS}}) have significantly reduced spectral radii than Stokes-based preconditioners (aPNMS_{\mathrm{S}}/aPLMMS_{\mathrm{S}}), resulting in faster GMRES convergence. Finally, the spectral radius of ELE_{\mathrm{L}} is almost one, confirming smoothers alone are inadequate for preconditioning GMRES.

Discussion

Coarse-scale solver

We presented a coarse-scale solver for computing approximate solutions to the steady-state Navier-Stokes equations in Algorithm 1, utilizing operators that comprise MGM_{\mathrm{G}}. We found that the MGM_{\mathrm{G}} of gPLMM yields far more accurate results than that of gPNM. Approximate solutions so obtained are sufficiently accurate (<30%< 30\% error in permeability) for use in a wide range of manufacturing (e.g., flow battery) and subsurface (e.g., CO2_2 storage) applications. But as

ReRe grows, accuracy degrades because the closure ∂nu=0\partial_n u = 0 becomes invalid at contact interfaces. Figure 11 demonstrates this, where unlike Stokes flow, streamlines no longer strike normal to the interface at high ReRe due to the formation of vortices. Recall a key step in imposing the velocity closure was to remove the inertia term from the residual of faces near each interface (Figure 3), so the column-sum operator C(⋅)C(\cdot) (in building P^\widehat{P}) imposes ∂nu=0\partial_n u = 0 exactly. Since all computations in Algorithm 1 involve only coarse-scale pressure unknowns defined on contact interfaces, with no recourse to the fine grid, the coarse-scale solver is much cheaper than computing solutions directly on the fine grid. Specifically, the TsolT_{\mathrm{sol}} and TMLT_{\mathrm{ML}} costs in Figure 14 are almost absent, rendering the coarse-scale solver faster by a factor of ∼10\sim10 in 2D and ∼2.5\sim2.5 in 3D Gyroid. However, Newton iterations of the coarse solver are larger by a factor of 2–5.

Two open questions remain: (1) Is there a more accurate closure at high ReRe and how does one impose it? (2) How can the coarse solver be generalized to time-dependent flows? The answer to (1) is unknown to to the authors, but we suspect there is an opportunity to use mortars (similar to [30]) to increase the flexibility of capturing arbitrary velocities along each interface. This would require building additional shape vectors (Eq.16a) and solving a larger coarse system (Eq. (35)), as was done in [30] for elliptic equations. Whether the associated costs would render such an approach prohibitive remains unknown. One answer to (2) involves discretizing ∂tu\partial_t u in the Navier-Stokes equations with a fixed time step dtdt, before building MG\mathrm{M}_{\mathrm{G}}. This embeds dtdt into the shape and correction vectors, which in turn can be used to march forward in time in increments of dtdt (similar to [25]). The drawback is committing to one dtdt for all tt.

Recommended preconditioners

The best-performing preconditioner for both steady-state and unsteady-state Navier-Stokes equations is gPLMM, consistently across all domains studied in § 8. This, incidentally, coincides with the more accurate coarse-scale solver based on gPLMM. The downside of gPLMM, however, is its need for geometric information, or more specifically, access to the code that can assemble the modified residual and Jacobian (r~\tilde{r} and J~\tilde{J} from Eq. (33)). Such access is needed to remove the inertia term from face-residuals near contact interfaces to impose ∂nu=0\partial_n u = 0. In the absence of such access, algebraic preconditioners are the only option, with aPLMMS_{\mathrm{S}} recommended for the steady-state and aPLMMNS_{\mathrm{NS}} for the unsteady-state Navier-Stokes equations. The former has the benefit of being built only once and reused for all ReRe. We remind that block preconditioners (bAMG, bPLMM, and bPNM) were extremely prohibitive and eliminated immediately from further consideration. PNM-based preconditioners (gPNM, aPNMS/NS_{\mathrm{S/NS}}) also exhibited very poor performance, indicating PLMM-based decomposition and closure are more accurate. Finally, smoothers alone are inadequate as preconditioners regardless of the steady-state or time-dependent form of the equations.

Computational complexity

While a serial machine was used here to perform all numerical tests, building and applying the coarse preconditioner MG\mathrm{M}_{\mathrm{G}} and the smoother ML\mathrm{M}_{\mathrm{L}} in all the proposed PLMM/PNM-based preconditioners are parallelizable. The cost of building MG\mathrm{M}_{\mathrm{G}} is dominated by computing shape vectors, pi\boldsymbol{p}^{i}, and correction vectors, ci\boldsymbol{c}^{i} in Eq. 16a, whose computations are fully decoupled across all primary grids. Similarly, applying the additive-Schwarz smoother ML\mathrm{M}_{\mathrm{L}} requires solving a set of decoupled local systems on primary and dual grids, both amenable to parallelism. In the following, we briefly analyze the computational complexity and parallel scalability of constructing and applying MG\mathrm{M}_{\mathrm{G}} and ML\mathrm{M}_{\mathrm{L}}.

Let Ω\Omega consist of NfN_f fine-scale unknowns, NpN^p primary grids, and NdN^d (=Nc=N^c) dual grids. Let all linear(ized) systems (global and local) be solved using a linear solver that scales as O(nβ)O(n^\beta), where nn is the size of the linear system and β∈(1,3)\beta\in(1,3). The wall-clock times (WCTs) associated with building and applying MG\mathrm{M}_{\mathrm{G}} and ML\mathrm{M}_{\mathrm{L}} are:

TbuildMG=O(Nf/Np)β×(2Nd+Np)/Nprc(43)\mathcal{T}^{\mathrm{M}_{\mathrm{G}}}_{\mathrm{build}} = O\left(N_f/N^p\right)^\beta\times\left(2N^d + N^p\right)/N_{\mathrm{prc}} \tag*{(43)}
TapplyMG=O(Nd+Np)β(44)\mathcal{T}^{\mathrm{M}_{\mathrm{G}}}_{\mathrm{apply}} = O\left(N^d + N^p\right)^\beta \tag*{(44)}
TapplyML=O[(Nf/Np)β×Np/Nprc+(Nfd/Nd)β×Nd/Nprc](45)\mathcal{T}^{\mathrm{M}_{\mathrm{L}}}_{\mathrm{apply}} = O\left[\left(N_f/N^p\right)^\beta\times N^p/N_{\mathrm{prc}} + \left(N_f d/N^d\right)^\beta\times N^d/N_{\mathrm{prc}}\right] \tag*{(45)}

where NprcN_{\mathrm{prc}} is the number of processors employed and fdf^d is the fraction of fine-scale unknowns associated with dual grids. Recall dual grids cover only a small portion of Ω\Omega (10–30%). Focusing on Eq. 31a, the average cost of solving one local system on a primary grid is O(Nf/Np)βO(N_f/N^p)^\beta, of which 2Nd2N^d must be solved for shape vectors and NpN^p for correction vectors to build MG\mathrm{M}_{\mathrm{G}}. These computations can all be performed in parallel, entailing NprcN_{\mathrm{prc}} can equal 2Nd+Np2N^d + N^p at maximum. Focusing next on Eq. 31b, one application of MG\mathrm{M}_{\mathrm{G}} requires solving a small coarse system of size Nd+NpN^d + N^p (Eq. (20)), whose cost is negligible compared to other overheads. As for Eq. 31c, the cost of applying ML\mathrm{M}_{\mathrm{L}} consists of solving NpN^p systems on primary grids and NdN^d systems on dual grids. If no pre-processing is done, the cost of building ML\mathrm{M}_{\mathrm{L}} is zero and all cost is due to application. But since applying ML\mathrm{M}_{\mathrm{L}} in iterative solvers requires repeated solves the same local systems, LU-decomposition during a pre-processing stage can significantly speed up ML\mathrm{M}_{\mathrm{L}}’s application. The construction cost of ML\mathrm{M}_{\mathrm{L}} then corresponds to these LU-decompositions, and the application cost in Eq. 31c is lowered (by reducing β\beta). Both the construction and application of ML\mathrm{M}_{\mathrm{L}} can be parallelized with NprcN_{\mathrm{prc}} up to max⁡{Np,Nd}\max\{N^p,N^d\}.

Challenges beyond linear preconditioning

Solving linear systems like Eq. (3) during Newton iterations is the slowest step in solving the Navier-Stokes equations, which we focused on herein. With our best preconditioner (gPLMM), the cost of steady-state simulations is dominated by GMRES’s self-time (TsolT_{\mathrm{sol}}), whereas that of dynamic simulations is dominated by ML\mathrm{M}_{\mathrm{L}}’s build-time (TMLT_{\mathrm{ML}}). Further speedup requires advances in both solvers and smoothers, not coarse preconditioners. Potential smoothers that remain untested include block ILU(kk), block Gauss-Seidel, and block additive-Schwarz based on PLMM or other.

Beyond linear preconditioning, the biggest challenge with solving the Navier-Stokes equations lies with Newton convergence. If the initial guess is far from the solution, Newton is very prone to divergence at high ReRe. What we have done here to reach high ReRe is essentially a method called homotopy continuation [41], where instead of solving the residual r(x^;Re)r(\hat{x};Re) in Eq. (3) directly at ReRe (the semicolon separates variable from parameter), an augmented residual H(x^,λ;Re):=r(x^;λRe)H(\hat{x},\lambda;Re) := r(\hat{x};\lambda Re) is solved for gradually increasing values of λ∈(0,1)\lambda\in(0,1). Notice H(x^,0;Re)H(\hat{x},0;Re) is an easy problem because it corresponds to Stokes flow, whereas H(x^,1;Re)=r(x^;Re)H(\hat{x},1;Re) = r(\hat{x};Re) is difficult as it corresponds to Navier-Stokes flow at the desired high ReRe. The approach we took to solve H(x^,λ;Re)H(\hat{x},\lambda;Re) and to increase λ\lambda was to increment the inlet pressure pinp_{\mathrm{in}} gradually from a low to a high value. This, in turn, implied an increment in ReRe, or equivalently λ\lambda. After solving H(x^,λ;Re)H(\hat{x},\lambda;Re) for a given λ\lambda, the solution was used as the initial guess for Newton in the next λ\lambda. While effective, our approach is computationally wasteful because H(x^,λ;Re)H(\hat{x},\lambda;Re) is solved to completion at each fixed λ\lambda. Better schemes, where λ\lambda is updated simultaneously as x^\hat{x} in a single Newton loop, exist and would likely be much more efficient [42, 43].

The above continuation approach was found essential for the steady-state flow equations. However, for unsteady-state flow, it is needed only if the time step dtdt used to discretize the ∂tu\partial_t u term in Eq. 1 is large. Note that at the limit dt→∞dt \to\infty, the discrete unsteady-state system reduces to state steady. But increasing dtdt too much introduces numerical diffusion into the solution, resulting in the inability to capture intricate details of the turbulent velocity field. In other words, the physics of the problem itself places an upper bound on dtdt, which is stricter at higher ReRe. If this bound is to be honored in favor of capturing the solution details accurately, then dtdt must necessarily be small and the system A^x^=b^\hat{A}\hat{x}=\hat{b} in Eq. (3) becomes diagonally dominant with respect to its (1,1)(1,1)-block. The latter helps Newton converge with almost any initial guess, but practically, it is natural to use the solution from the prior time step, as was done here.

Future extensions

While our preconditioners target the Navier-Stokes equations for Newtonian fluid flow in a fixed geometry, their applicability extends to more challenging problems. In immiscible two-phase flow, governing equations consist of a momentum balance and a phase-evolution equation, solved in staggered fashion to march forward in time. The former is essentially Navier Stokes plus a source term for interfacial tension, whose solution is the main computational bottleneck [8]. We expect our preconditioners to accelerate solving the momentum equation without any modification to MGM_G, as the source term will likely introduce high-frequency variations to the flow field. The phase-evolution equation is hyperbolic and discretized explicitly in time. It is, therefore, much cheaper to solve and errors are high-frequency in nature, which can be removed by a smoother alone (no MGM_G; similar to the phase-field equation in fracture mechanics [36]). Another class of candidate problems exhibit evolving geometry, due either to mineral dissolution/precipitation [44], biofilm growth [45], or phase change [46]. If the representation of Γw\Gamma_w is sharp (as is here), the decomposition of Ω\Omega into primary and dual grids must be updated periodically, which can be done locally and adaptively. But if Γw\Gamma_w is diffuse, as in the Brinkman–Stokes model [47], extra source terms in (1) capture geometric changes that get embedded into the shape/correction vectors of MGM_G. Finally, the flow of non-Newtonian fluids (e.g., blood, polymer) may benefit from our preconditioners if applied to linearized forms of the governing equations [48].

Conclusions

We present monolithic preconditioners to accelerate the convergence of linear solvers applied to the Navier-Stokes equations in arbitrarily complex porous microstructures. They are based on the pore-level multiscale method (PLMM) and the pore network model (PNM), and they generalize previously proposed preconditioners for the Stokes equations [24]. The preconditioners are two-level, consisting of a coarse preconditioner MGM_G and a smoother MLM_L, designed to attenuate low- and high-frequency errors, respectively. To build both, the computational domain is decomposed into subdomains (primary and dual grids), over which local problems are solved. We formulate algebraic (aaPLMM and aaPNM) and geometric (ggPLMM and ggPNM) versions of each preconditioner, with the key difference being that the closure BC ∂nu=0\partial_n u=0 is imposed exactly on subdomain interfaces in the geometric form but only approximately in the algebraic form. Hence, geometric preconditioners perform better but require access to code assembling the Jacobian to modify it slightly. Algebraic preconditioners need no such access and operate directly on the linear system.

We test our preconditioners against a wide range of 2D and 3D porous geometries, different ReRe, and steady-state and time-dependent forms of the Navier-Stokes equations.We also benchmark them against state-of-the-art block preconditioners bAMGbAMG, bPLMMbPLMM, and bPNMbPNM. The best-performing preconditioner across the board was ggPLMM. But since it requires intrusive access to code, comparable performance is possible with aPLMMSa\mathrm{PLMM}_{\mathrm{S}} for steady-state Navier Stokes and aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} for time-dependent Navier Stokes. Subscripts “S” and “NS” indicate the preconditioners are built from the Jacobians of the Stokes and Navier-Stokes equations. Given the Stokes equations are linear, aPLMMSa\mathrm{PLMM}_{\mathrm{S}} need only be built once for usage at other ReRe, whereas aPLMMNSa\mathrm{PLMM}_{\mathrm{NS}} (and gPLMMg\mathrm{PLMM}) must be built periodically at a nearby ReRe if ReRe changes, to retain optimal performance. Block and PNM-based preconditioners are far from competitive. Lastly, we formulate a coarse-scale solver based on gPLMMg\mathrm{PLMM} for the steady-state Navier-Stokes equations, which computes approximate solutions rapidly. Acceleration is achieved by conducting all computations on coarse-scale pressure unknowns defined at subdomain interfaces, without any recourse to the fine grid. The coarse solution can be mapped onto the fine grid using a prolongation operator inherent to gPLMMg\mathrm{PLMM}. Approximate solutions so obtained have acceptable accuracy for a range of applications (permeability error <30%< 30\%). Our coarse solver is more accurate than classical PNMs designed to capture inertial flow in pore-scale domains, simplified by a ball-and-stick representation.

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant No. CMMI-2145222. We acknowledge the Institute for Computational and Data Sciences (ICDS) at Penn State University for access to computational resources.

Validating the fine-grid solver

We validate the fine-grid solver used to assemble the residual and Jacobian of the Navier-Stokes equations, thus produce all results in this work. We consider fluid flow around circular and square obstacles at different ReRe. Fig. A.1 shows the 2D domains, which consist of rectangles of length L=3L=3 cm and height H=2H=2 cm. The centroids of the circle and square are positioned at half-height and a distance of 1 cm from the left boundary. The side length of the square and diameter of the circle are both D=0.2D=0.2 cm. The BCs consists of: (1) inflow on the left (u=(10,0)u=(10,0) and ∂np=0\partial_n p=0); (2) outflow on the right (∂nu=0\partial_n u=0 and p=0p=0); (3) slip on top and bottom (∂nu=0\partial_n u=0 and ∂np=0\partial_n p=0); and (4) no-slip on circle and square perimeters (u=0u=0 and ∂np=0\partial_n p=0). Fig. A.1 shows the pressure, velocity magnitude, and vorticity magnitude over the whole domain at a low and high ReRe. A von Karman vortex street is seen to form in the latter.

To validate the fine-scale solver, we compute drag coefficient:

CD=2Fdρuin2D(46)C_D = \frac{2F_d}{\rho u_{\mathrm{in}}^2D} \tag*{(46)}

on the obstacles at different Re=ρuinD/μRe=\rho u_{\mathrm{in}}D/\mu and compare them to literature values in Table A.1. In Eq. A.1, FdF_d is the drag force exerted on the obstacles, and uin=10u_{\mathrm{in}}=10 is the inlet velocity imposed in the horizontal direction. Table A.1 shows the CDC_D computed here agrees with many other reported values in the literature for ReRe between 20 and 300.

Reynolds numberThis work, CDC_DLiterature, CDC_D
CylinderRe=20Re=202.182.00 [49], 2.09 [50], 2.20 [51]
CylinderRe=40Re=401.631.62 [52], 1.53 [50], 1.60 [53]
CylinderRe=100Re=1001.371.35 [54], 1.39 [55], 1.35 [56]
CylinderRe=300Re=3001.321.38 [56], 1.28 [51], 1.37 [57]
SquareRe=100Re=1001.571.59 [58], 1.51 [59]
SquareRe=250Re=2501.711.66 [56], 1.69–1.72 [60]

Table A.1. Comparison of drag coefficient (CDC_D) computed here against literature for flow around a circle and square at different ReRe.

Image not extracted

Figure A.1. Pressure, velocity magnitude, and vorticity magnitude for flow around circular and square obstacles at different ReRe.

References

  1. [1]Jacob Bear. Dynamics of fluids in porous media. Courier Corporation, 2013.
  2. [2]Peisheng Liu and Guo-Feng Chen. Porous materials: processing and applications. Elsevier, 2014.

Paper details

vlnc:W_g7bdgrzc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents