Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Semi-implicit Krylov deferred correction methods for differential algebraic equations

Authors: Sunyoung Bu, Jingfang Huang and Michael L. Minion
Journal: Math. Comp. 81 (2012), 2127-2157
MSC (2010): Primary 65B10, 65F10, 65L20, 65L80, 65N35
Published electronically: April 26, 2012
MathSciNet review: 2945149
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1.
  • 2. V. Ajjarapu, Computational Techniques for Voltage Stability Assessment and Control, Springer, 2007.
  • 3. G. Akrivis, M. Crouzeix, and C. Makridakis, Implicit-explicit multistep methods for quasilinear parabolic equations, Numer. Math., 82:521-541, 1999. MR 1701828 (2000e:65075)
  • 4. B. K. Alpert, and V. Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM J. on Sci. and Stat. Computing, 12,158-179, 1991. MR 1078802 (91i:65042)
  • 5. P. M. Anderson, Analysis of Faulted Power Systems, Wiley-IEEE Press, 1995.
  • 6. U. M. Ascher, and L. R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, Philadelphia, 1998. MR 1638643 (99k:65052)
  • 7. U. M. Ascher, S. J. Ruuth, and B. Wetton, Implicit-explicit methods for time-dependent PDEs, SIAM J. Numer. Anal, 32, 797-823, 1997. MR 1335656 (96j:65076)
  • 8. U. M. Ascher, S. J. Ruuth, and R. J. Spiteri, Implicit-explicit Runge-Kutta methods for time-dependent partial differential equations, Appl. Numer. Math, 25, 151-167, 1997. MR 1485812 (98i:65054)
  • 9. K. Atkinson, An Introduction to Advanced Numerical Analysis, 2nd edition, John Wiley, 1989. MR 1007135 (90m:65001)
  • 10. W. Auzinger, H. Hofstätter, W. Kreuzer, and E. Weinmüller, Modified defect correction algorithms for ODEs. Part I: General theory, Numer. Algorithms, 36:135-156, 2004. MR 2062870 (2005h:65096)
  • 11. R. Barrett, et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, SIAM, Philadelphia, 1994. MR 1247007 (94m:65002)
  • 12. S. Boscarino, Erroro analysis of IMEX Runge-Kutta methods derived from differential-algebraic systems, SIAM J. Numer. Anal., Vol. 45, No. 4, pp. 1600-1621, 2007. MR 2338401 (2008g:65086)
  • 13. S. Boscarino, On an accurate third order implicit-explicit Runge-Kutta method for stiff problems, Appl. Numer. Math, Vol. 59, pp. 1515-1528, 2009. MR 2512274 (2010d:65142)
  • 14. A. Bourlioux, A.T. Layton, and M.L. Minion, High-order multi-implicit spectral deferred correction methods for problems of reactive flow, J.Comput. Phys., 189, 351-376, 2003. MR 1996061 (2004f:76084)
  • 15. E. Bouzarth, M. Minion, A multirate integrator for regularized stokeslets, J. Comp. Phys. 229 (2010) 4208-4224. MR 2609773 (2011b:65099)
  • 16. K. E. Brenan, S. L. Campbell, and L. R. Petzold, Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations, SIAM, Philadelphia, 1995. MR 1363258 (96h:65083)
  • 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 eduction of Runge-Kutta methods for linear initial boundary value problems, Math. Comput., 71, 1529-1543, 2002. MR 1933043 (2003h:65091)
  • 19. M. P. Calvo, J. de Frutos, and J. Novo, Linearly implicit Runge-Kutta methods for advection-reaction-diffusion equations, Appl. Numer. Math., 37:535-549, 2001. MR 1831798 (2002e:65114)
  • 20. C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral Methods in Fluid Dynamics, Springer-Verlag, 1988. MR 917480 (89m:76004)
  • 21. K. Chen, A. Iserles, and P. G. Ciarlet (Editors), Matrix Preconditioning Techniques and Applications, Cambridge University Press, 2005. MR 2169217 (2006e:65001)
  • 22. K. Dekker, and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations. CWI Monographs. North-Holland, 1984. MR 774402 (86g:65003)
  • 23. A. Dutt, L. Greengard, and V. Rokhlin, Spectral deferred correction methods for ordinary differential equations, BIT, 40(2) 241-266, 2000. MR 1765736 (2001e:65104)
  • 24. A. Dutt, M. Gu, and V. Rokhlin, Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. on Num. Anal., 33(5), 1689-1711, 1996. MR 1411845 (97h:65015)
  • 25. J. Frank, W. Hundsdorfer and J. G. Verwer, Stability of implicit-explicit linear multistep methods, Applied Numerical Mathematics: Transactions of IMACS, Vol.25, 2-3, 1997 MR 1485815 (98m:65126)
  • 26. D. Gottlieb, and S. S. Orszag, Numerical Analysis of Spectral Methods, SIAM, Philadelphia, 1977.
  • 27. L. Greengard, Spectral integration and two-point boundary value problems, SIAM J. Num. Anal. 28, 1071-1080 1991. MR 1111454 (92h:65033)
  • 28. L. Greengard, and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73, 325-348, 1987. MR 918448 (88k:82007)
  • 29. E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Springer-Verlag, 2002. MR 1904823 (2003f:65203)
  • 30. E. Hairer, C. Lubich, and M. Roche, The Numerical Solution of Differential-Algebraic Systems by Runge-Kutta Methods, Springer-Verlag, 1989. MR 1027594 (91a:65178)
  • 31. E. Hairer, and G. Wanner, Solving Ordinary Differential Equations II, Springer, 1996. MR 1439506 (97m:65007)
  • 32. J. Huang, J. Jia, and M. Minion, Accelerating the convergence of spectral deferred correction methods, J. of Comp. Physics, 214(2), 633-656 , 2006. MR 2216607 (2006k:65173)
  • 33. J. Huang, J. Jia, M. Minion, Arbitrary order Krylov deferred correction methods for differential algebraic equations, Comput. Phys., 221,(2), 739-760, 2007. MR 2293148 (2008a:65134)
  • 34. J. Jia, J. Hunag, Krylov deferred correction accelerated method of lines transpose for parabolic problems, J. Comput. Phys., 227(3),1739-1753, 2008. MR 2450970 (2009k:65175)
  • 35. C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995. MR 1344684 (96d:65002)
  • 36. C. T. Kelley, Solving Nonlinear Equations with Newton's Method, SIAM, 2003. MR 1998383 (2004i:65003)
  • 37. C. A. Kennedy and M. H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations., Appl. Numer. Math., 44:139-181, 2003. MR 1951292 (2003m:65111)
  • 38. D.A. Knoll, D.E. Keyes, Jacobian-free Newton Krylov methods: A survey of approaches and applications, J. Comput. Phys. 193 (2004) 357-397. MR 2030471 (2004j:65066)
  • 39. P. Kolm, S. Jiang, and V. Rokhlin, Quadruple and octuple layer potentials in two dimensions. I. Analytical apparatus, Appl. Comput. Harmon. Anal. 14, no. 1, 2003. MR 1971301 (2004c:35436)
  • 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. A. T. Layton, and M. L. Minion, Conservative multi-implicit spectral deferred correction methods for reacting gas dynamics, J. Comput. Phys, 194(2), 697-714, 2004. MR 2034861 (2004k:76089)
  • 42. A. T. Layton, and M. 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. MR 2176198 (2006h:65087)
  • 43. A. T. Layton and M. 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. MR 2327081 (2008e:65252)
  • 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. M. L. Minion, Semi-implicit spectral deferred correction methods for ordinary differential equations, Comm. Math. Sci., 1:471-500, 2003. MR 2069941 (2005f:65085)
  • 47. M. L. Minion, Semi-implicit projection methods for incompressible flow based on spectral deferred corrections, Appl. Numer. Math., 48 (3-4), 369-387, 2004. MR 2056924
  • 48. N. Mohan, First Course on Power Systems, MNPERE, 2006.
  • 49. L. Pareschi and G. Russo, Implicit-explicit Runge-Kutta schemes for stiff systems of differential equations, volume 3, pages 269-287. Nova Science, 2000. MR 2029975 (2005a:65065)
  • 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.
  • 51. V. Pereyra, Iterated deferred correction for nonlinear boundary value problems, Numer. Math. 11, 111-125 1968. MR 0225498 (37:1091)
  • 52. L. R. Petzold, A Description of DASSL: A Differential-Algebraic System Solver, SAND82-8637, Sandia National Lab, 1982. MR 751605
  • 53. A. Rangan, Adaptive Solvers for Partial Differential and Differential-Algebraic Equations, Ph.D. Thesis, University of California at Berkeley , 2003. MR 2705653
  • 54. A. Rangan, Deferred Correction Methods for Low Index Differential Algebraic Equations, BIT, Vol. 43, No. 1, 1-18, 2003.
  • 55. Y. Saad and M. H. Schultz. GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM J. Sci. Stat. Comp., 7:856-869, 1986. MR 848568 (87g:65064)
  • 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, 405-418, 1986. MR 875165 (88f:65146)
  • 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. L. N. Trefethen, and M. R. Trummer, An instability phenomenon in spectral methods, SIAM J. Numer. Anal, 24, 1008-1023, 1987 MR 909061 (89a:65139)
  • 59. P. K. Vijalapura, J. Strain, and S. Govindjee, Fractional step methods for index-1 differential-algebraic equations, J. of Comp. Phys., 203(1), 305-320, 2005. MR 2104398 (2005k:65160)
  • 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. P. E. Zadunaisky, On the estimation of errors propagated in the numerical integration of ordinary differential equations, Numer. Math. 27, 21-40 1976. MR 0431696 (55:4691)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65B10, 65F10, 65L20, 65L80, 65N35

Retrieve articles in all journals with MSC (2010): 65B10, 65F10, 65L20, 65L80, 65N35

Additional Information

Sunyoung Bu
Affiliation: Department of Mathematics, University of North Carolina, CB #3250, Phillips Hall, Chapel Hill North Carolina 27599-3250
Address at time of publication: Institute of Mathematical Sciences, Ewha Womans University, Seoul 120-750, Korea

Jingfang Huang
Affiliation: Department of Mathematics, University of North Carolina, CB #3250, Phillips Hall, Chapel Hill North Carolina 27599-3250

Michael L. Minion
Affiliation: Department of Mathematics, University of North Carolina, CB #3250, Phillips Hall, Chapel Hill North Carolina 27599-3250

Keywords: Differential algebraic equations, Krylov deferred correction, semi-implicit schemes, preconditioner
Received by editor(s): July 21, 2010
Received by editor(s) in revised form: March 18, 2011
Published electronically: April 26, 2012
Additional Notes: The work of Bu was partially supported by the Priority Research Centers Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2010-0028298). Part of the work was done while Bu was a visiting member of the Institute for Mathematics and Its Applications at the University of Minnesota.
The work of Huang and Bu was supported by NSF grants 0811130 and 0941235
The work of Minion was supported by NSF grant 0854961
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society