Emil Constantinescu's research: time-stepping

Picture of Emil Constantinescu

Emil Constantinescu
emconsta[at]mcs.anl.gov
• Asst Computational Mathematician
• Mathematics and Computer Science
• Argonne National Laboratory

• Fellow of the Computation Institute
• University of Chicago

Homepage

Research

-	Time stepping
-	Uncertainty
-	AMR

Publications

ANL Stuff

Time Integration

Time-stepping methods are algorithms used to compute the numerical solution of ordinary differential equations as well as to evolve the solution of partial differential equations in time. This page describes three advanced techniques: general linear methods, implicit-explicit schemes, and multirate time-stepping algorithms.

General linear methods (GLMs)

General linear (GL) methods, under various names (e.g., hybrid methods, pseudo Runge-Kutta) represent a natural generalization of both Runge-Kutta and linear multistep methods that are aimed at improving their stability and accuracy properties while taking advantage of past precomputed information. They use both internal stages like RK methods and information from previous solution steps like LM methods.

IMplicit-EXplicit (IMEX) time stepping methods

The dynamics of a process determines the best numerical solution strategy. Explicit time discretizations are effective for slow processes as their computational cost per step is relatively low. On the other hand implicit methods are more efficient for fast processes as their step sizes are not limited by stability considerations. Time integration of multiscale processes is challenging as neither purely explicit nor purely implicit methods are adequate. Explicit methods require prohibitively small time steps (limited by the fastest time scale in the system). Implicit methods require the solution of (non)linear systems of equations that involve all the processes in the model; this is both computationally expensive and difficult to implement. The implicit-explicit (IMEX) approach has been developed to alleviate these difficulties. The IMEX idea is to combine an implicit scheme for the stiff components with an explicit scheme for the non-stiff components such that the overall discretization method has the desired stability and accuracy properties.

Below is a performance analysis of several extrapolation IMEX methods introduced in [Constantinescu and Sandu, 2008] applied to a advection-reaction problem with stiff boundary conditions. The comparison is carried among different IMEX-BDF and ARK methods of various orders. As discussed in the reference mentioned above, the extrapolation IMEX methods are easily parallelizable; therefore, a naive parallelization with OpenMP (left figure) shows that these methods can outperform the state-of-the-art BDF or Runge-Kutta IMEX schemes on a 8-core machine. [mode details are forthcoming]

Multirate time stepping methods

Hyperbolic conservation laws are of great practical importance as they model diverse physical phenomena that appear in mechanical and chemical engineering, aeronautics, astrophysics, meteorology and oceanography, financial modeling, environmental sciences, etc. Representative examples are gas dynamics, shallow water flow, groundwater flow, non-Newtonian flows, traffic flows, advection and dispersion of contaminants, etc. Conservative high resolution methods with explicit time discretization have gained widespread popularity to numerically solve these problems.

Stability requirements limit the temporal step size, with the upper bound being determined by the ratio of the temporal and spatial meshes and the magnitude of the wave speed. Local spatial mesh refinement reduces the allowable time step for the explicit time discretizations. The time step for the entire domain is restricted by the finest mesh patch or by the highest wave velocity, and is typically (much) smaller than necessary for other variables in the computational domain.

Multirate time integration schemes allow the time step to vary across the spatial domain while satisfying the CFL condition only locally, resulting in substantially more efficient overall computations.

Multirate Example (1)

An example is given below that illustrates the main idea of multirate and AMR. The 2D simulation models the transport of a (power plant) plume in the atmosphere (1 km mixing layer) with an Eastern wind (5 m/s) and a turbulent diffusivity of 100 m²/s. The simulation is run for 6 hours. The power plant is turned off and the plume dynamics is simulated for another six hours. Note how the fine grid resolution follows the features of the solution. Such an algorithm that dynamically adapts the grid for large scale models is presented in [Constantinescu et al. 2007; Comp. Geosci.]. The fine resolution accurately resolves the fine features of the solution. In order to efficiently implement this AMR approach, different time steps should be used for different resolutions: large time steps for coarse resolutions and small time steps for fine resolutions resulting in multirate algorithms. Examples of such algorithms are found in [Constantinescu et al. 2007; Sci. Comp.] or [Sandu et al. 2007; Sci. Comp.]

Selected journal publications, proceedings, presentations

Journal publications:

Emil M. Constantinescu and Adrian Sandu, "Extrapolated multirate methods for differential equations with multiple time scales." Journal of Scientific Computing, submitted; Preprint # ANL/MCS-P1796-1010, 2010.
Emil M. Constantinescu and Adrian Sandu, "Optimal strong-stability-preserving general linear methods." SIAM Journal of Scientific Computing, Vol. 32(5), Pages 3130-3150, 2010. -> Technical report with complete results.
Emil M. Constantinescu and Adrian Sandu, "Extrapolated implicit-explicit time stepping." Vol. 31(6), Pages 4452-4477, SIAM Journal of Scientific Computing, 2010. -> Technical report version.
Emil M. Constantinescu, "On the order of general linear methods." Vol. 22(9), Pages 1425-1428, Applied Mathematics Letters, 2009. -> Technical report version [ANL/MCS-P1555-1008, Oct 2008].
Adrian Sandu and Emil M. Constantinescu, "Multirate explicit Adams methods for time integration of conservation laws." Vol. 38(2), Pages 229-249, Journal of Scientific Computing, 2009. -> Technical report version.
Emil M. Constantinescu, Adrian Sandu, and Gregory R. Carmichael, "Modeling atmospheric chemistry and transport with dynamic adaptive resolution." Vol. 12(2), Pages 133-151, Computational Geosciences, 2008.
Emil M. Constantinescu and Adrian Sandu, "Multirate timestepping methods for hyperbolic conservation laws." Vol. 33(3), Pages 239-278, Journal of Scientific Computing, 2007. -> Technical report version.

Proceedings/Presentations/Posters:

Emil M. Constantinescu and Adrian Sandu, "Multirate explicit SSP methods for hyperbolic PDEs" in Time Discretizations for the Evolution of Time-dependent PDEs mini-symposium; SIAM Annual Meeting (AN10), Pittsburgh, PA, July 13, 2010.
Adrian Sandu and Emil M. Constantinescu, "Multirate time discretizations for hyperbolic partial differential equations." International Conference of Numerical Analysis and Applied Mathematics (ICNAAM 2009), Crete, Greece, 18-22 September; Vol. 1168(1), pp. 1411-1414, 2009.
Emil M. Constantinescu and Adrian Sandu, "Explicit time stepping methods with high stage order and monotonicity properties." International Conference on Computational Science (ICCS) 2009, Baton Rouge, Louisiana, May 25-27, 2009 [ Preprint ANL/MCS-P1576-0109, January 2009].
"On General Linear Time Stepping Methods." Presented by Emil M. Constantinescu at SIAM CS&E 2009 meeting, Miami, FL, March 2-6, 2009.
Emil M. Constantinescu and Adrian Sandu, "On Extrapolated multirate numerical integration methods." ECMI 2008 (Springer Mathematics in Industry), 2008 -> Technical report version.
Emil M. Constantinescu and Adrian Sandu, "Strong stability preserving multirate schemes for hyperbolic conservation laws." SIAM Conference on Computational Science and Engineering (CSE 2007), Costa Mesa, CA, February 18-23, 2007.
Emil M. Constantinescu and Adrian Sandu, "On adaptive mesh refinement for atmospheric pollution models." International Conference on Computational Science (ICCS) 2005, pages 798-806 Atlanta, GA, May 22-25, 2005.
Emil M. Constantinescu, Wenyuan Liao, and Adrian Sandu, "Mesh refinement strategies in air quality modeling." High Performance Computing Symposium (HPC) 2005, pages 158-163 - San Diego, CA, April 2-8, 2005.

Technical Reports:

Emil M. Constantinescu and Adrian Sandu, "Optimal Explicit Strong-Stability-Preserving General Linear Methods: Complete Results." Mathematics and Computer Science Division Technical Memorandum ANL/MCS-TM-304, Argonne National Laboratory, January 2009.
Emil M. Constantinescu and Adrian Sandu, "On the order of general linear methods." Technical Report ANL/MCS/JA-62914, Mathematics and Computer Science, Argonne National Laboratory, Oct 2008.
Emil M. Constantinescu and Adrian Sandu, "On Extrapolated Multirate Methods." Technical Report TR-08-12, Computer Science, Virginia Tech, 2008.
Emil M. Constantinescu and Adrian Sandu, "Achieving Very High Order for Implicit Explicit Time Stepping: Extrapolation Methods."Mathematics and Computer Science Division Technical Memorandum ANL/MCS-TM-306, Argonne National Laboratory, April 2009.
Adrian Sandu and Emil M. Constantinescu, "Multirate explicit Adams methods for time integration of conservation laws." Technical Report TR-07-30(989), Computer Science, Virginia Tech, 2007.
Emil M. Constantinescu and Adrian Sandu, "Update on multirate timestepping methods for hyperbolic conservation laws." Technical Report TR-07-12(955), Computer Science, Virginia Tech, 2007.
Emil M. Constantinescu and Adrian Sandu, "Multirate timestepping methods for hyperbolic conservation laws." Technical Report TR-06-15, Computer Science, Virginia Tech, 2006.