×

zbMATH — the first resource for mathematics

Semi-implicit Krylov deferred correction methods for differential algebraic equations. (English) Zbl 1270.65044
Summary: In the recently developed Krylov deferred correction (KDC) methods for differential algebraic equation initial value problems (cf. [J. Huang et al., J. Comput. Phys. 221, No. 2, 739–760 (2007; Zbl 1110.65076)]), 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.

MSC:
65L80 Numerical methods for differential-algebraic equations
34A09 Implicit ordinary differential equations, differential-algebraic equations
65Y20 Complexity and performance of numerical algorithms
65L05 Numerical methods for initial value problems
65F08 Preconditioners for iterative methods
65L20 Stability and convergence of numerical methods for ordinary differential equations
Software:
DASSL; PSAT; RODAS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] http://pitagora.dm.uniba.it/ testset/
[2] V. Ajjarapu, Computational Techniques for Voltage Stability Assessment and Control, Springer, 2007.
[3] Georgios Akrivis, Michel Crouzeix, and Charalambos Makridakis, Implicit-explicit multistep methods for quasilinear parabolic equations, Numer. Math. 82 (1999), no. 4, 521 – 541. · Zbl 0936.65118 · doi:10.1007/s002110050429 · doi.org
[4] 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. · Zbl 0726.65018 · doi:10.1137/0912009 · doi.org
[5] P. M. Anderson, Analysis of Faulted Power Systems, Wiley-IEEE Press, 1995.
[6] 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. · Zbl 0908.65055
[7] 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. · Zbl 0841.65081 · doi:10.1137/0732037 · doi.org
[8] 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). · Zbl 0896.65061 · doi:10.1016/S0168-9274(97)00056-1 · doi.org
[9] Kendall E. Atkinson, An introduction to numerical analysis, 2nd ed., John Wiley & Sons, Inc., New York, 1989. · Zbl 0718.65001
[10] 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. · Zbl 1058.65068 · doi:10.1023/B:NUMA.0000033129.73715.7f · doi.org
[11] 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. · Zbl 0814.65030
[12] Sebastiano Boscarino, Error analysis of IMEX Runge-Kutta methods derived from differential-algebraic systems, SIAM J. Numer. Anal. 45 (2007), no. 4, 1600 – 1621. · Zbl 1152.65088 · doi:10.1137/060656929 · doi.org
[13] Sebastiano Boscarino, On an accurate third order implicit-explicit Runge-Kutta method for stiff problems, Appl. Numer. Math. 59 (2009), no. 7, 1515 – 1528. · Zbl 1162.65367 · doi:10.1016/j.apnum.2008.10.003 · doi.org
[14] 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. · Zbl 1061.76053 · doi:10.1016/S0021-9991(03)00251-1 · doi.org
[15] Elizabeth L. Bouzarth and Michael L. Minion, A multirate time integrator for regularized Stokeslets, J. Comput. Phys. 229 (2010), no. 11, 4208 – 4224. · Zbl 1334.76097 · doi:10.1016/j.jcp.2010.02.006 · doi.org
[16] 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. · Zbl 0844.65058
[17] 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.
[18] 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. · Zbl 1005.65100
[19] 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. · Zbl 0983.65106 · doi:10.1016/S0168-9274(00)00061-1 · doi.org
[20] 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. · Zbl 0658.76001
[21] Ke Chen, Matrix preconditioning techniques and applications, Cambridge Monographs on Applied and Computational Mathematics, vol. 19, Cambridge University Press, Cambridge, 2005. · Zbl 1079.65057
[22] 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. · Zbl 0571.65057
[23] Alok Dutt, Leslie Greengard, and Vladimir Rokhlin, Spectral deferred correction methods for ordinary differential equations, BIT 40 (2000), no. 2, 241 – 266. · Zbl 0959.65084 · doi:10.1023/A:1022338906936 · doi.org
[24] 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. · Zbl 0862.65005 · doi:10.1137/0733082 · doi.org
[25] 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). · Zbl 0887.65094 · doi:10.1016/S0168-9274(97)00059-7 · doi.org
[26] D. Gottlieb, and S. S. Orszag, Numerical Analysis of Spectral Methods, SIAM, Philadelphia, 1977. · Zbl 0412.65058
[27] L. Greengard, Spectral integration and two-point boundary value problems, SIAM J. Numer. Anal. 28 (1991), no. 4, 1071 – 1080. · Zbl 0731.65064 · doi:10.1137/0728057 · doi.org
[28] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325 – 348. · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 · doi.org
[29] 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. · Zbl 0994.65135
[30] 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. · Zbl 0683.65050
[31] 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. · Zbl 0859.65067
[32] Jingfang Huang, Jun Jia, and Michael Minion, Accelerating the convergence of spectral deferred correction methods, J. Comput. Phys. 214 (2006), no. 2, 633 – 656. · Zbl 1094.65066 · doi:10.1016/j.jcp.2005.10.004 · doi.org
[33] 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. · Zbl 1110.65076 · doi:10.1016/j.jcp.2006.06.040 · doi.org
[34] 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. · Zbl 1134.65064 · doi:10.1016/j.jcp.2007.09.018 · doi.org
[35] 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. · Zbl 0832.65046
[36] 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. · Zbl 1031.65069
[37] 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. · Zbl 1013.65103 · doi:10.1016/S0168-9274(02)00138-1 · doi.org
[38] 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. · Zbl 1036.65045 · doi:10.1016/j.jcp.2003.08.010 · doi.org
[39] 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. · Zbl 1139.35397 · doi:10.1016/S1063-5203(03)00004-6 · doi.org
[40] 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.
[41] 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. · Zbl 1100.76048 · doi:10.1016/j.jcp.2003.09.010 · doi.org
[42] 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. · Zbl 1078.65552 · doi:10.1007/s10543-005-0016-1 · doi.org
[43] 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. · Zbl 1131.65059 · doi:10.2140/camcos.2007.2.1 · doi.org
[44] F. Milano, An open source power system analysis toolbox, Power Systems, IEEE Transactions on, Vol. 20, No. 3, 2005.
[45] 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.
[46] Michael L. Minion, Semi-implicit spectral deferred correction methods for ordinary differential equations, Commun. Math. Sci. 1 (2003), no. 3, 471 – 500. · Zbl 1088.65556
[47] 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. · Zbl 1035.76040 · doi:10.1016/j.apnum.2003.11.005 · doi.org
[48] N. Mohan, First Course on Power Systems, MNPERE, 2006.
[49] 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. · Zbl 1018.65093
[50] J. O. Pessanha and A. A. Paz, Testing a Differential-algebraic Equation Solver in Long-term Voltage Stability Simulation, Mathematical Problems in Engineering, 2006. · Zbl 1196.78031
[51] Victor Pereyra, Iterated deferred corrections for nonlinear boundary value problems, Numer. Math. 11 (1968), 111 – 125. · Zbl 0176.15003 · doi:10.1007/BF02165307 · doi.org
[52] 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.
[53] 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.
[54] A. Rangan, Deferred Correction Methods for Low Index Differential Algebraic Equations, BIT, Vol. 43, No. 1, 1-18, 2003.
[55] 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. · Zbl 0599.65018 · doi:10.1137/0907058 · doi.org
[56] 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. · Zbl 0589.65069 · doi:10.1007/BF01396661 · doi.org
[57] 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.
[58] Lloyd N. Trefethen and Manfred R. Trummer, An instability phenomenon in spectral methods, SIAM J. Numer. Anal. 24 (1987), no. 5, 1008 – 1023. · Zbl 0636.65124 · doi:10.1137/0724066 · doi.org
[59] 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. · Zbl 1063.65074 · doi:10.1016/j.jcp.2004.08.015 · doi.org
[60] 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
[61] 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.
[62] 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. · Zbl 0324.65035 · doi:10.1007/BF01399082 · doi.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.