CRM-McGill Applied Math Seminar Tuesday Jan 29, 2008, 3:35pm Burnside Room 1205 Felix Kwok Geneva University Title: Efficient linear and nonlinear solvers for multiphase flow in porous media Abstract: The efficient simulation of immiscible fluid displacements in underground porous media remains an important and challenging problem in reservoir engineering. First, the governing PDEs exhibit a mixed hyperbolic-parabolic character due to the coupling between the global flow and the local transport of the different phases. The transport problem is highly nonlinear, leading to the formation of shock fronts and steep gradients in the saturation profile. In addition, rock properties such as porosity and permeability are highly heterogeneous, leading to poor numerical conditioning of the resulting linear systems. Finally, fluid velocities vary greatly across the domain, with near-well regions experiencing fast flows and some far away regions experiencing almost no flow at all. Consequently, the use of explicit integrators would entail a time-step restriction that is much more severe than the global reservoir time scales. For this reason, implicit time-stepping is the preferred temporal discretization in the reservoir simulation community, but this requires the solution of a very large system of nonlinear algebraic equations (often on the order of millions of unknowns) at each time step. Our main algorithmic contribution is the ordering of equations and unknowns in such a way that flow directions are exploited. This leads to improvements in both the linear and nonlinear solvers. In the nonlinear setting, the ordering leads to a reduced-order Newton method, which numerical experiments have shown to have a much more robust convergence behavior than the usual Newton's method. We also prove, for 1D incompressible two-phase flow, that the reduced Newton method converges for any time-step size. In the linear solver, ordering improves the convergence of the Constrained Pressure Residual (CPR) preconditioner and reduces its sensitivity to flow configurations. We also present a rigorous analysis of phase-based upstream discretization, which is different from the classical Godunov and Engquist-Osher schemes for nonlinear conservation laws. We show, based on a fully nonlinear analysis, that the fully implicit scheme is well-defined, stable, monotonic and converges to the entropy solution for arbitrary CFL numbers. Thus, unlike the existing linear stability analysis, our results provide a rigorous justification for the empirical observation that fully-implicit solutions are always stable and yield monotonic profiles.