- Sunyoung Bu, Jingfang Huang, and Michael L. Minion, Semi-implicit Krylov Deferred Correction Methods for Ordinary Differential Equations. In Proceedings of the 15th American Conference on Applied Mathematics (Houston, USA, April 30 - May 02, 2009), 95-100, 2009.
Abstract: In the recently developed Krylov deferred correction (KDC) methods for differential algebraic equation initial value problems, a Picard-type collocation formulation is preconditioned using low-order time integration schemes based on spectral deferred correction (SDC), and the resulting system is solved e±ciently using Newton-Krylov methods. In this paper, we further improve the effciency of these KDC methods by introducing the semi-implicit KDC (SI-KDC) methods, in which the stiff component of the preconditioner is solved by implicit schemes and the non-stiff parts by explicit methods. Compared with fully implicit KDC (FI-KDC) methods, preliminary analyses show that the convergence of Newton-Krylov iterations in the SI-KDC methods is similar to that in FI-KDC, while for systems with a nonlinear non-stiff component and a linear stiff part, the SI-KDC can greatly reduce the computational cost in each spectral deferred correction iteration for the same accuracy requirement, as only linear solves are required in each SI-KDC iteration. The analyses are validated by preliminary numerical results.
- Michael L. Minion and Sarah A. Williams, Parareal and Spectral Deferred Corrections, AIP Conference Proceedings, 1048, 388--391, 2008.
Abstract: A new class of iterative time parallel methods for initial value ordinary differential equations are developed. Methods based on a parallel variation of spectral deferred corrections (SDC) are compared and contrasted with the parareal method. It is shown that there is a strong similarity between the serial step in the parareal algorithm and the correction step in the SDC method. This observation is used to construct a hybrid strategy combining features of both the parareal and SDC methods which can significantly reduce the computational cost of each iteration compared to parareal. A numerical example is presented to compare the effectiveness of the hybrid strategies.
- Samet Kadioglu, Rupert Klein, and Michael L. Minion, A Fourth-Order Auxiliary Variable Projection Method for Zero-Mach Number Gas Dynamics, J. Comput. Phys.,227,(3), 2012--2043, 2008.
Abstract: A fourth-order numerical method for the zero-Mach-number limit of the equations for compressible flow is presented. The method is formed by discretizing a new auxiliary variable formulation of the conservation equations, which is a variable density analog to the impulse or gauge formulation of the incompressible Euler equations. An auxiliary variable projection method is applied to this formulation, and accuracy is achieved by combining a fourth-order finite-volume spatial discretization with a fourth-order temporal scheme based on spectral deferred corrections. Numerical results are included which demonstrate fourth-order spatial and temporal accuracy for non-trivial flows in simple geometries.
- Jingfang Huang, Jun Jia, and Michael L. Minion, Arbitrary Order Krylov Deferred Correction Methods for Differential Algebraic Equations, J. Comput. Phys., 221,(2), 739--760, 2007.
Abstract: In this paper, a new framework for the construction of accurate and efficient numerical methods for differential algebraic equation (DAE) initial value problems is presented. The methods are based on applying spectral deferred correction techniques as preconditioners to a Picard integral collocation formulation for the solution. The resulting preconditioned nonlinear system is solved using Newton-Krylov schemes such as the Newton-GMRES method. Least squares based orthogonal polynomial approximations are computed using Gaussian type quadratures, and spectral integration is used to avoid the numerically unstable differentiation operator. The resulting Krylov deferred correction (KDC) methods are of arbitrary order of accuracy and very stable. Preliminary results show that these new methods are very competitive with existing DAE solvers, particularly when high precision is desired.
- Anita T. Layton and Michael L. Minion, Implications of the Choice of Predictors for Semi-Implicit Picard Integral Deferred Correction Methods, Comm. App. Math. and Comp. Sci., 2(1),1--34, 2007.
Abstract: Previously, high-order semi-implicit Picard integral deferred correction (SIPIDC) methods have been proposed for the time-integration of partial differential equations with two or more disparate time scales. The SIPIDC methods studied to date compute a high-order approximation by first computing a provisional solution with a first-order semi-implicit method and then using a similar semi-implicit method to solve a series of correction equations, each of which raises the order of accuracy of the solution by one. This study assesses the efficiency of SIPIDC methods that instead use standard semi-implicit methods with orders two through four to compute the provisional solution. Numerical results indicate that using a method with more than first-order accuracy in the computation of the provisional solution increases the efficiency of SIPIDC methods in some cases. first-order PIDC corrections can improve the efficiency of semi-implicit integration methods based on backward difference formula (BDF) or Runge-Kutta methods while maintaining desirable stability properties. Finally, the phenomenon of order reduction, which may be encountered in the integration of stiff problems, can be partially alleviated by the use of BDF methods in the computation of the provisional solution.
- Jingfang Huang, Jun Jia, and Michael L. Minion, Accelerating the Convergence of Spectral Deferred Correction Methods, J. Comput. Phys., 214 (2), 633-656, 2006.
Abstract: In the recent paper by Dutt, Greengard and Rokhlin, a variant of deferred or defect correction methods is presented which couples Gaussian quadrature with the Picard integral equation formulation of the initial value ordinary differential equation. The resulting {\it spectral deferred correction} methods (SDC) have been shown to possess favorable accuracy and stability properties even for versions with very high order of accuracy. In this paper, we show that for linear problems, the iterations in the SDC algorithm are equivalent to constructing a preconditioned Neumann series expansion for the solution of the standard collocation discretization of the ODE. This observation is used to accelerate the convergence of SDC using the GMRES Krylov subspace method. For nonlinear problems, the GMRES acceleration is coupled with a linear implicit approach. Stability and accuracy analyses show the accelerated scheme provides an improvement in the accuracy, efficiency, and stability of the original SDC approach. Furthermore, preliminary numerical experiments show that accelerating the convergence of SDC methods can effectively eliminate the order reduction previously observed for stiff ODE systems.
- Anita T. Layton and Michael L. Minion, Implications of the Choice of Quadrature Nodes for Picard Integral Deferred Corrections Methods for Ordinary Differential Equations, BIT, 45 (2), 341-373, 2005.
Abstract: This paper concerns a class of deferred correction methods recently developed for initial value ordinary differential equations; such methods are based on a Picard integral form of the correction equation. These methods divide a given timestep $ [t_n,t_{n+1}] $ into substeps, and use function values computed at these substeps to approximate the Picard integral by means of a numerical quadrature. The main purpose of this paper is to present a detailed analysis of the implications of the location of quadrature nodes on the accuracy and stability of the overall method. Comparisons between Gauss-Legendre, Gauss-Lobatto, Gauss-Radau, and uniformly spaced points are presented. Also, for a given set of quadrature nodes, quadrature rules may be formulated that include or exclude function values computed at the left-hand endpoint $t_n$. Quadrature rules that do not depend on the left-hand endpoint (which are referred to as right-hand quadrature rules) are shown to lead to $L(\alpha)$-stable implicit methods with $\alpha\approx\pi/2$. The semi-implicit analog of this property is also discussed. Numerical results suggest that the use of uniform quadrature nodes, as opposed to nodes based on Gaussian quadratures, does not significantly affect the stability or accuracy of these methods for orders less than ten. In contrast, a study of the reduction of order for stiff equations shows that when uniform quadrature nodes are used in conjunction with a right-hand quadrature rule, the form and extent of order-reduction changes considerably. Specifically, a reduction of order to ${\mathcal O}(\epsilon^2)$ is observed for uniform nodes as opposed to ${\mathcal O}(\epsilon\Delta t)$ for non-uniform nodes, where $\Delta t$ denotes the time step and $\epsilon$ denotes a stiffness parameter such that $\epsilon\rightarrow 0$ corresponds to the problem becoming increasingly stiff.
- Anita T. Layton and Michael L. Minion, Conservative Multi-Implicit Spectral Deferred Correction Methods for Reacting Gas Dynamics, J. Comput. Phys, 194 (2), 697-714, 2004.
Abstract: In most models of reacting gas dynamics, the characteristic time scales of chemical reactions are much shorter than the hydrodynamic and diffusive time scales, rendering the reaction part of the model equations stiff. Moreover, nonlinear forcings may introduce into the solutions sharp gradients or shocks, the robust behavior and correct propagation of which require the use of specialized spatial discretization procedures. This study presents high-order conservative methods for the temporal integration of model equations of reacting flows. By means of a method of lines discretization on the flux difference form of the equations, these methods compute approximations to the cell-averaged or finite-volume solution. The temporal discretization is based on a multi-implicit generalization of spectral deferred correction methods. The advection term is integrated explicitly, and the diffusion and reaction terms are treated implicitly but independently, with the splitting errors reduced via the spectral deferred correction procedure. To reduce computational cost, different time steps may be used to integrate processes with widely-differing time scales. Numerical results show that the conservative nature of the methods allows a robust representation of discontinuities and sharp gradients; the results also demonstrate the expected convergence rates for the methods of orders three, four, and five for smooth problems.
- Michael L. Minion, Semi-Implicit Projection Methods for Incompressible Flow based on Spectral Deferred Corrections, Appl. Numer. Math., 48 (3-4), 369-387, 2004.
Abstract: A semi-implicit form of spectral deferred corrections is used in a method of lines approach to create a projection method that is sixth-order accurate in both time and space for simple domains. The derivation of spectral deferred corrections is presented and compared to traditional deferred correction methods. An auxiliary variable form of the equations for Boussinesq flow is presented which facilitates a method of lines approach. A discussion of how these methods can be extended to complex spatial domains through the use of integral equation methods is also presented.
- Anne Bourlioux , Anita T. Layton, and Michael L. Minion High-Order Multi-implicit Spectral Deferred Correction Methods for Problems of Reactive Flow, J. Comput. Phys., 189, 351--376, 2003.
Abstract: Models for reacting flow are typically based on advection-diffusion-reaction (A-D-R) partial differential equations. Many practical cases correspond to situations where the relevant time-scales associated with each of the three sub-processes can be widely different, leading to disparate time-step requirements for robust and accurate time-integration. In particular, interesting regimes in combustion correspond to systems in which diffusion and reaction are much faster processes than advection. The numerical strategy introduced in this paper is a general procedure to account for this time-scale disparity. The proposed methods are high-order multi-implicit generalizations of spectral deferred correction methods (MISDC methods), constructed for the temporal integration of A-D-R equations. Spectral deferred correction methods compute a high-order approximation to the solution of a differential equation by using a simple, low-order numerical method to solve a series of correction equations, each of which increases the order of accuracy of the approximation. The key feature of MISDC methods is their flexibility in handling several sub-processes implicitly but independently, while avoiding the splitting errors present in traditional operator-splitting methods and also allowing for different time-steps for each process. The stability, accuracy, and efficiency of MISDC methods are first analyzed using a linear model problem and the results are compared to semi-implicit spectral deferred correction methods. Furthermore, numerical tests on simplified reacting flows demonstrate the expected convergence rates for MISDC methods of orders three, four, and five. The gain in efficiency by independently controlling the sub-process time-steps is illustrated for nonlinear problems, where reaction and diffusion are much stiffer than advection. Although the paper focuses on this specific time-scales ordering, the generalization to any ordering combination is straightforward.
- Michael L. Minion, Semi-implicit Spectral Deferred Correction Methods for Ordinary Differential Equations, Comm. Math. Sci., 1(3), 471--500, 2003.
Abstract: A semi-implicit formulation of the method of spectral deferred corrections (SISDC) for ordinary differential equations with both stiff and non-stiff terms is presented. Several modifications and variations to the original spectral deferred corrections method by Dutt, Greengard, and Rokhlin concerning the choice of integration points and the form of the correction iteration are presented. The stability and accuracy of the resulting ODE methods for both stiff and non-stiff problems are explored analytically and numerically. The SISDC methods are intended to be combined with the method of lines approach to yield a flexible framework for creating higher-order semi-implicit methods for partial differential equations. A discussion and numerical examples of the SISDC method applied to advection-diffusion type equations are included. The results suggest that higher-order SISDC methods are a competitive alternative to existing Runge-Kutta and linear multistep methods based on the accuracy per function evaluation.
- Michael L. Minion, Higher-order Semi-implicit Projection Methods, in Numerical Simulations of Incompressible Flows. Papers from the workshop held in Half Moon Bay, CA, June 19-21, 2001. also LLNL Technical Report UCRL-JC-145295.
Abstract: A semi-implicit form of the method of spectral deferred corrections is applied to the solution of the incompressible Navier-Stokes equations. A methodology for constructing semi-implicit projection methods with arbitrarily high order of temporal accuracy in both the velocity and pressure is presented. Three variations of projection methods are discussed which differ in the manner in which the auxiliary velocity and the pressure are calculated. The presentation will make clear that projection methods in general need not be viewed as fractional step methods as is often the practice. Two simple numerical examples are used to demonstrate fourth-order accuracy in time for an implementation of each variation of projection method.
- David L. Brown, Ricardo Cortez, and Michael L. Minion Accurate Projection Methods for the Incompressible Navier-Stokes Equations, J. Comput. Phys., 168, 464 -- 499, 2001.
Abstract: This paper considers the accuracy of projection method approximations to the initial-boundary-value problem for the incompressible Navier-Stokes equations. The issue of how to correctly specify numerical boundary conditions for these methods has been outstanding since the birth of the second-order methodology a decade and a half ago. It has been observed that while the velocity can be reliably computed to second-order accuracy in time and space, the pressure is typically only first-order accurate in the $L_\infty$-norm. This paper identifies the source of this problem in the interplay of the global pressure-update formula with the numerical boundary conditions, and presents an improved projection algorithm which is fully second-order accurate, as demonstrated by a normal mode analysis and numerical experiments. In addition, a numerical method based on an impulse formulation of the incompressible Navier-Stokes equations is discussed, which provides another option for obtaining fully second-order convergence in both velocity and pressure. The connection between the boundary conditions for projection methods and impulse methods is explained in detail.
- Leslie Greengard, Zydrunas Gimbutas and Michael L. Minion Coulumb Interactions on Planar Structures: Inverting the Square Root of the Laplacian", SIAM J. Sci. Computing 22 (6), 2093--2108, 2001.
Abstract: We present an adaptive fast multipole method for inverting the square root of the Laplacian in two dimensions. Solving this problem is the dominant computational cost in many applications arising in electrical engineering, geophysical fluid dynamics, and the study of thin films. It corresponds to the evaluation of the field induced by a planar distribution of charge or vorticity. Our algorithm is direct and assumes only that the source distribution is discretized using an adaptive quad-tree. The amount of work grows linearly with the number of mesh points.
- Ricardo Cortez and Michael L. Minion, The Blob Projection Method for Immersed Boundary Problems, J. Comput. Phys., 161, 428--453, 2000.
Abstract: A new finite difference numerical method for modeling the interaction between flexible elastic membranes and an incompressible fluid in a two-dimensional domain is presented. The method differs from existing methods in the way the forces exerted by the membranes on the fluid are modeled. These are described by a collection of regularized point forces, and the velocity field they induce is computed directly on a regular Cartesian grid via a smoothed dipole potential. Comparisons between this method and the immersed boundary method of Peskin and McQueen are presented. The results show that the method proposed here preserves volumes better and has a higher order of convergence.
- Michael L. Minion and David L. Brown, Performance of Under-resolved Two-dimensional Incompressible Flow Simulations II, J. Comput. Phys., 138, 734 -- 765, 1997.
Abstract: This paper presents a study of the behavior of several difference approximations for the incompressible Navier-Stokes equations as a function of the computational mesh resolution. In particular, the under-resolved case is considered. The methods considered include a Godunov projection method, a primitive variable ENO method, an upwind vorticity stream-function method, centered difference methods of both a pressure-Poisson and vorticity stream-function formulation, and a pseudospectral method. It is demonstrated that all these methods produce spurious, non-physical vortices of the type described by Brown and Minion for a Godunov projection method \cite{brownMinion:1995} when the flow is sufficiently under-resolved. The occurrence of these artifacts appears to be due to a nonlinear effect in which the truncation error of the difference method initiates a vortex instability in the computed flow. The implications of this study for adaptive mesh refinement strategies are also discussed.
- Michael L. Minion, A Projection Method for Locally Refined Grids, J. Comput. Phys., 127, 158 -- 177, 1996.
Abstract: A numerical method for the solution of the two-dimensional Euler equations for incompressible flow on locally refined grids is presented. The method is a second order Godunov-projection method adapted from Bell, Colella, and Glaz. Second order accuracy of the numerical method in time and space is established through numerical experiments. The main contributions of this work concern the formulation and implementation of a projection for refined grids. A discussion of the adjointness relation between gradient and divergence operators for a refined grid MAC projection is presented, and a uniformly accurate, refined grid approximate projection is developed. An efficient multigrid method which exactly solves the projection is developed, and a method for casting certain approximate projections as MAC projections on refined grids is presented.
- Michael L. Minion, On The Stability of Godunov-projection Methods for Incompressible Flow, J. Comput. Phys., 123, 435 -- 449, 1996.
Abstract: An analysis of the stability of certain numerical methods for the linear advection-diffusion equation in two dimensions is performed. The advection-diffusion equation is studied because it is a linearized version of the Navier-Stokes equations, the evolution equation for density in Boussinesq flows, and a simplified form of the equations for bulk thermodynamic temperature and mass fraction in reacting flows. It is found that various methods currently in use which are based on a Crank-Nicholson type temporal discretization utilizing second-order Godunov methods for explicitly calculating advective terms suffer from a time-step restriction which depends on the coefficients of diffusive terms. A simple modification in the computation of the advective derivatives results in a method with a stability condition that is independent of the magnitude of the coefficients of the diffusive terms.
- David L. Brown and Michael L. Minion, Performance of Under-resolved Two-dimensional Incompressible Flow Simulations J. Comput. Phys., 122, 165 -- 183,1995.
Abstract: A careful study of the behavior of a Godunov-projection method for the incompressible Navier-Stokes equations as a function of the resolution of the computational mesh is presented. By considering a representative example problem, it is demonstrated that a Godunov-projection method performs as well as an accurate centered finite difference method in cases where the smallest flow scales are well-resolved. In under-resolved cases, however, where centered methods compute solutions badly polluted with mesh-scale oscillations, the Godunov-projection method sometimes computes smooth, apparently physical solutions. Closer examination indicates that these under-resolved Godunov solutions, although convergent when the grid is refined, contain spurious non-physical vortices that are artifacts of the under-resolution. These artifacts are not unique to Godunov methods, however, and are observed with other difference approximations as well. The implication of these results on the applicability of difference approximations to engineering flow problems in the under-resolved case is discussed.