Semi-implicit Krylov deferred correction methods for differential algebraic equations

Bu, Sunyoung; Huang, Jingfang; Minion, Michael

doi:10.1090/S0025-5718-2012-02564-6

Semi-implicit Krylov deferred correction methods for differential algebraic equations
HTML articles powered by AMS MathViewer

by Sunyoung Bu, Jingfang Huang and Michael L. Minion PDF

Math. Comp. 81 (2012), 2127-2157 Request permission

Abstract:

In the recently developed Krylov deferred correction (KDC) methods for differential algebraic equation initial value problems (Huang, Jia, Minion, 2007), 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 efficiently using Newton-Krylov methods. KDC methods have the advantage that methods with arbitrarily high order of accuracy can be easily constructed which have similar computational complexity as lower order methods. In this paper, we investigate semi-implicit KDC (SI-KDC) methods in which the stiff component of the preconditioner is treated implicitly and the non-stiff parts explicitly. For certain types of problems, such a semi-implicit treatment can significantly reduce the computational cost of the preconditioner compared to fully implicit KDC (FI-KDC) methods. Preliminary analysis and numerical experiments show that the convergence of Newton-Krylov iterations in the SI-KDC methods is similar to that in FI-KDC, and hence the SI-KDC methods offer a reduction in overall computational cost for such problems.

References

http://pitagora.dm.uniba.it/~testset/
V. Ajjarapu, Computational Techniques for Voltage Stability Assessment and Control, Springer, 2007.
Georgios Akrivis, Michel Crouzeix, and Charalambos Makridakis, Implicit-explicit multistep methods for quasilinear parabolic equations, Numer. Math. 82 (1999), no. 4, 521–541. MR 1701828, DOI 10.1007/s002110050429
Bradley K. Alpert and Vladimir Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM J. Sci. Statist. Comput. 12 (1991), no. 1, 158–179. MR 1078802, DOI 10.1137/0912009
P. M. Anderson, Analysis of Faulted Power Systems, Wiley-IEEE Press, 1995.
Uri M. Ascher and Linda R. Petzold, Computer methods for ordinary differential equations and differential-algebraic equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. MR 1638643, DOI 10.1137/1.9781611971392
Uri M. Ascher, Steven J. Ruuth, and Brian T. R. Wetton, Implicit-explicit methods for time-dependent partial differential equations, SIAM J. Numer. Anal. 32 (1995), no. 3, 797–823. MR 1335656, DOI 10.1137/0732037
Uri M. Ascher, Steven J. Ruuth, and Raymond J. Spiteri, Implicit-explicit Runge-Kutta methods for time-dependent partial differential equations, Appl. Numer. Math. 25 (1997), no. 2-3, 151–167. Special issue on time integration (Amsterdam, 1996). MR 1485812, DOI 10.1016/S0168-9274(97)00056-1
Kendall E. Atkinson, An introduction to numerical analysis, 2nd ed., John Wiley & Sons, Inc., New York, 1989. MR 1007135
W. Auzinger, H. Hofstätter, W. Kreuzer, and E. Weinmüller, Modified defect correction algorithms for ODEs. I. General theory, Numer. Algorithms 36 (2004), no. 2, 135–155. MR 2062870, DOI 10.1023/B:NUMA.0000033129.73715.7f
Richard Barrett, Michael Berry, Tony F. Chan et al., Templates for the solution of linear systems: building blocks for iterative methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1247007, DOI 10.1137/1.9781611971538
Sebastiano Boscarino, Error analysis of IMEX Runge-Kutta methods derived from differential-algebraic systems, SIAM J. Numer. Anal. 45 (2007), no. 4, 1600–1621. MR 2338401, DOI 10.1137/060656929
Sebastiano Boscarino, On an accurate third order implicit-explicit Runge-Kutta method for stiff problems, Appl. Numer. Math. 59 (2009), no. 7, 1515–1528. MR 2512274, DOI 10.1016/j.apnum.2008.10.003
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 (2003), no. 2, 651–675. MR 1996061, DOI 10.1016/S0021-9991(03)00251-1
Elizabeth L. Bouzarth and Michael L. Minion, A multirate time integrator for regularized Stokeslets, J. Comput. Phys. 229 (2010), no. 11, 4208–4224. MR 2609773, DOI 10.1016/j.jcp.2010.02.006
K. E. Brenan, S. L. Campbell, and L. R. Petzold, Numerical solution of initial-value problems in differential-algebraic equations, Classics in Applied Mathematics, vol. 14, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. Revised and corrected reprint of the 1989 original. MR 1363258
S. Bu, J. Huang, and M.M. Minion, Semi-implicit Krylov Deferred Correction Methods for Ordinary Differential Equations, Proceedings of the American Conference on Applied Mathematics, Houston, May, 2009.
M. P. Calvo and C. Palencia, Avoiding the order reduction of Runge-Kutta methods for linear initial boundary value problems, Math. Comp. 71 (2002), no. 240, 1529–1543. MR 1933043, DOI 10.1090/S0025-5718-01-01362-X
M. P. Calvo, J. de Frutos, and J. Novo, Linearly implicit Runge-Kutta methods for advection-reaction-diffusion equations, Appl. Numer. Math. 37 (2001), no. 4, 535–549. MR 1831798, DOI 10.1016/S0168-9274(00)00061-1
Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, and Thomas A. Zang, Spectral methods in fluid dynamics, Springer Series in Computational Physics, Springer-Verlag, New York, 1988. MR 917480, DOI 10.1007/978-3-642-84108-8
Ke Chen, Matrix preconditioning techniques and applications, Cambridge Monographs on Applied and Computational Mathematics, vol. 19, Cambridge University Press, Cambridge, 2005. MR 2169217, DOI 10.1017/CBO9780511543258
K. Dekker and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations, CWI Monographs, vol. 2, North-Holland Publishing Co., Amsterdam, 1984. MR 774402
Alok Dutt, Leslie Greengard, and Vladimir Rokhlin, Spectral deferred correction methods for ordinary differential equations, BIT 40 (2000), no. 2, 241–266. MR 1765736, DOI 10.1023/A:1022338906936
A. Dutt, M. Gu, and V. Rokhlin, Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. Numer. Anal. 33 (1996), no. 5, 1689–1711. MR 1411845, DOI 10.1137/0733082
J. Frank, W. Hundsdorfer, and J. G. Verwer, On the stability of implicit-explicit linear multistep methods, Appl. Numer. Math. 25 (1997), no. 2-3, 193–205. Special issue on time integration (Amsterdam, 1996). MR 1485815, DOI 10.1016/S0168-9274(97)00059-7
D. Gottlieb, and S. S. Orszag, Numerical Analysis of Spectral Methods, SIAM, Philadelphia, 1977.
L. Greengard, Spectral integration and two-point boundary value problems, SIAM J. Numer. Anal. 28 (1991), no. 4, 1071–1080. MR 1111454, DOI 10.1137/0728057
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, DOI 10.1016/0021-9991(87)90140-9
Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2002. Structure-preserving algorithms for ordinary differential equations. MR 1904823, DOI 10.1007/978-3-662-05018-7
Ernst Hairer, Christian Lubich, and Michel Roche, The numerical solution of differential-algebraic systems by Runge-Kutta methods, Lecture Notes in Mathematics, vol. 1409, Springer-Verlag, Berlin, 1989. MR 1027594, DOI 10.1007/BFb0093947
E. Hairer and G. Wanner, Solving ordinary differential equations. II, 2nd ed., Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1996. Stiff and differential-algebraic problems. MR 1439506, DOI 10.1007/978-3-642-05221-7
Jingfang Huang, Jun Jia, and Michael Minion, Accelerating the convergence of spectral deferred correction methods, J. Comput. Phys. 214 (2006), no. 2, 633–656. MR 2216607, DOI 10.1016/j.jcp.2005.10.004
Jingfang Huang, Jun Jia, and Michael Minion, Arbitrary order Krylov deferred correction methods for differential algebraic equations, J. Comput. Phys. 221 (2007), no. 2, 739–760. MR 2293148, DOI 10.1016/j.jcp.2006.06.040
Jun Jia and Jingfang Huang, Krylov deferred correction accelerated method of lines transpose for parabolic problems, J. Comput. Phys. 227 (2008), no. 3, 1739–1753. MR 2450970, DOI 10.1016/j.jcp.2007.09.018
C. T. Kelley, Iterative methods for linear and nonlinear equations, Frontiers in Applied Mathematics, vol. 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. With separately available software. MR 1344684, DOI 10.1137/1.9781611970944
C. T. Kelley, Solving nonlinear equations with Newton’s method, Fundamentals of Algorithms, vol. 1, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. MR 1998383, DOI 10.1137/1.9780898718898
Christopher A. Kennedy and Mark H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations, Appl. Numer. Math. 44 (2003), no. 1-2, 139–181. MR 1951292, DOI 10.1016/S0168-9274(02)00138-1
D. A. Knoll and D. E. Keyes, Jacobian-free Newton-Krylov methods: a survey of approaches and applications, J. Comput. Phys. 193 (2004), no. 2, 357–397. MR 2030471, DOI 10.1016/j.jcp.2003.08.010
Petter Kolm, Shidong Jiang, and Vladimir Rokhlin, Quadruple and octuple layer potentials in two dimensions. I. Analytical apparatus, Appl. Comput. Harmon. Anal. 14 (2003), no. 1, 47–74. MR 1971301, DOI 10.1016/S1063-5203(03)00004-6
A. Kurita, H. Okubo, K. Oki, S. Agematsu, D. B. Klapper, N. W. Miller, W. W. Price, J. J. Jr.Sanchez-Gasca, K. A. Wirgau, T. D. Younkins, Multiple time-scale power system dynamic simulation, Power Systems, IEEE Transactions pp. 216-223, Vol. 8, Issue: 1, Feb. 1993.
Anita T. Layton and Michael L. Minion, Conservative multi-implicit spectral deferred correction methods for reacting gas dynamics, J. Comput. Phys. 194 (2004), no. 2, 697–715. MR 2034861, DOI 10.1016/j.jcp.2003.09.010
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 (2005), no. 2, 341–373. MR 2176198, DOI 10.1007/s10543-005-0016-1
Anita T. Layton and Michael L. Minion, Implications of the choice of predictors for semi-implicit Picard integral deferred correction methods, Commun. Appl. Math. Comput. Sci. 2 (2007), 1–34. MR 2327081, DOI 10.2140/camcos.2007.2.1
F. Milano, An open source power system analysis toolbox, Power Systems, IEEE Transactions on, Vol. 20, No. 3, 2005.
M. 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.
Michael L. Minion, Semi-implicit spectral deferred correction methods for ordinary differential equations, Commun. Math. Sci. 1 (2003), no. 3, 471–500. MR 2069941, DOI 10.4310/CMS.2003.v1.n3.a6
Michael L. Minion, Semi-implicit projection methods for incompressible flow based on spectral deferred corrections, Appl. Numer. Math. 48 (2004), no. 3-4, 369–387. Workshop on Innovative Time Integrators for PDEs. MR 2056924, DOI 10.1016/j.apnum.2003.11.005
N. Mohan, First Course on Power Systems, MNPERE, 2006.
Lorenzo Pareschi and Giovanni Russo, Implicit-explicit Runge-Kutta schemes for stiff systems of differential equations, Recent trends in numerical analysis, Adv. Theory Comput. Math., vol. 3, Nova Sci. Publ., Huntington, NY, 2001, pp. 269–288. MR 2029975
J. O. Pessanha and A. A. Paz, Testing a Differential-algebraic Equation Solver in Long-term Voltage Stability Simulation, Mathematical Problems in Engineering, 2006.
Victor Pereyra, Iterated deferred corrections for nonlinear boundary value problems, Numer. Math. 11 (1968), 111–125. MR 225498, DOI 10.1007/BF02165307
Linda R. Petzold, A description of DASSL: a differential/algebraic system solver, Scientific computing (Montreal, Que., 1982) IMACS Trans. Sci. Comput., I, IMACS, New Brunswick, NJ, 1983, pp. 65–68. MR 751605
Aaditya Viswanath Rangan, Adaptive solvers for partial differential and differential-algebraic equations, ProQuest LLC, Ann Arbor, MI, 2003. Thesis (Ph.D.)–University of California, Berkeley. MR 2705653
A. Rangan, Deferred Correction Methods for Low Index Differential Algebraic Equations, BIT, Vol. 43, No. 1, 1-18, 2003.
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
J. M. Sanz-Serna, J. G. Verwer, and W. H. Hundsdorfer, Convergence and order reduction of Runge-Kutta schemes applied to evolutionary problems in partial differential equations, Numer. Math. 50 (1987), no. 4, 405–418. MR 875165, DOI 10.1007/BF01396661
J. W. Shen and X. Zhong, Semi-implicit Runge-Kutta schemes for the non-autonomous differential equations in reactive flow computations, Proceedings of the 27th AIAA Fluid Dynamics Conference, AIAA, June 1996.
Lloyd N. Trefethen and Manfred R. Trummer, An instability phenomenon in spectral methods, SIAM J. Numer. Anal. 24 (1987), no. 5, 1008–1023. MR 909061, DOI 10.1137/0724066
Prashanth K. Vijalapura, John Strain, and Sanjay Govindjee, Fractional step methods for index-1 differential-algebraic equations, J. Comput. Phys. 203 (2005), no. 1, 305–320. MR 2104398, DOI 10.1016/j.jcp.2004.08.015
D. Yong, V. Ajjarapu, A Decoupled Time-Domain Simulation Method via Invariant Subspace Partition for Power System Analysis, Power Systems, IEEE Transactions pp. 11-18, Volume: 21, Issue: 1, Feb. 2006
P. E. Zadunaisky, A method for the estimation of errors propagated in the numerical solution of a system of ordinary differential equations, The Theory of Orbits in the Solar System and in Stellar Systems. Proceedings of International Astronomical Union, Symposium 25, 1964.
Pedro E. Zadunaisky, On the estimation of errors propagated in the numerical integration of ordinary differential equations, Numer. Math. 27 (1976/77), no. 1, 21–39. MR 431696, DOI 10.1007/BF01399082