On the consistency analysis of finite difference approximations

D. L. Michels   ; V. P. Gerdt   ; Yu. A. Blinkov   ; D. A. Lyakhov

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXIX, Tome 468 (2018), pp. 249-266

Résumé

Finite difference schemes are widely used in applied mathematics to numerically solve partial differential equations. However, for a given solution scheme, it is usually difficult to generally evaluate the quality of their underlying finite difference approximation with respect to the inheritance of algebraic properties of the differential problem under consideration. In this contribution, we present an appropriate quality criterion of strong consistency for finite difference approximations to systems of nonlinear partial differential equations. This property strengthens the standard requirement of consistency of difference equations with the differential ones. On this foundation, we use a verification algorithm for strong consistency, which is based on the computation of difference Gröbner bases. This allows for the evaluation and construction of solution schemes, which preserve some fundamental algebraic properties of the system at the discrete level. We demonstrate our presented concept by simulating a Kármán vortex street for two-dimensional incompressible viscous flow described by the Navier–Stokes equations.

Bibliographie

[1] P. Amodio, Yu. A. Blinkov, V. P. Gerdt, R. La Scala, “On Consistency of Finite Difference Approximations to the Navier–Stokes Equations”, Computer Algebra in Scientific Computing, CASC 2013, LNCS, 8136, eds. V. P. Gerdt, W. Koepff, E. W. Mayr, E. V. Vorozhtsov, Springer, Cham, 2013, 46–60 | MR | Zbl

[2] P. Amodio, Yu. A. Blinkov, V. P. Gerdt, R. La Scala, “Algebraic construction and numerical behavior of a new $s$-consistent difference scheme for the 2D Navier–Stokes equations”, Applied Mathematics and Computation, 314 (2017), 408–421 | DOI | MR

[3] T. Bächler, V. P. Gerdt, M. Lange-Hegermann, D. Robertz, “Algorithmic Thomas decomposition of algebraic and differential systems”, J. Symbolic Computation, 47:10 (2012), 1233–1266 | DOI | MR | Zbl

[4] T. Becker, V. Weispfenning, A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics, 141, Springer, New York, 1993 | DOI | MR | Zbl

[5] Yu. A. Blinkov, C. F. Cid, V. P. Gerdt, W. Plesken, D. Robertz, “The MAPLE Package Janet: II. Linear Partial Differential Equations”, Proceedings of the 6th International Workshop on Computer Algebra in Scientific Computing, CASC 2003, eds. V. G. Ganzha, E. W. Mayr, E. V. Vorozhtsov, Technische Universität München, 2003, 41–54; Package Janet is freely available on the web page: http://wwwb.math.rwth-aachen.de/Janet/

[6] D. Cox, J. Little, D. O'Shie, Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd Edition, Springer, New York, 2007 | MR | Zbl

[7] V. P. Gerdt, “On Decomposition of Algebraic PDE Systems into Simple Subsystems”, Acta Applicandae Mathematicae, 101 (2008), 39–51 | DOI | MR | Zbl

[8] V. P. Gerdt, “Consistency Analysis of Finite Difference Approximations to PDE Systems”, Mathematical Modeling in Computational Physics, MMCP 2011, LNCS, 7125, eds. G. Adam, J. Buša, M. Hnatič, Springer, Berlin, 2012, 28–42

[9] V. P. Gerdt, Yu. A. Blinkov, V. V. Mozzhilkin, “Gröbner Bases and Generation of Difference Schemes for Partial Differential Equations”, SIGMA, 2 (2006), 051 | DOI | MR | Zbl

[10] V. P. Gerdt, Yu. A. Blinkov, “Involution and Difference Schemes for the Navier–Stokes Equations”, Computer Algebra in Scientific Computing, CASC 2009, LNCS, 5743, eds. V. P. Gerdt, E. W. Mayr, E. V. Vorozhtsov, Springer, Berlin, 2009, 94–105 | MR | Zbl

[11] V. P. Gerdt, R. La Scala, “Noetherian Quotient of the Algebra of Partial Difference Polynomials and Gröbner Bases of Symmetric Ideals”, J. Algebra, 423 (2015), 1233–1261 | DOI | MR | Zbl

[12] V. P. Gerdt, D. Robertz, “Consistency of Finite Difference Approximations for Linear PDE Systems and its Algorithmic Verification”, Proceedings of ISSAC 2010, ed. Watt S. M., Association for Computing Machinery, 2010, 53–59 | MR | Zbl

[13] V. P. Gerdt, D. Robertz, “Computation of Difference Gröbner Bases”, Computer Science Journal of Moldova, 20:2(59) (2012), 203–226 | MR | Zbl

[14] S. K. Godunov, V. S. Ryaben'kii, Difference schemes. An introduction to the underlying theory, Elsevier, New York, 1987 | MR

[15] P. M. Gresho, R. L. Sani, “On Pressure boundary conditions for the incompressible Navier–Stokes equations”, Int. J. Numer. Methods Fluids, 7 (1987), 1111–1145 | DOI | Zbl

[16] E. Hubert, “Notes on Triangular Sets and Triangulation-Decomposition Algorithms. II. Differential Systems”, SNSC 2001, LNCS, 2630, eds. F. Winkler, U. Langer, Springer, Berlin, 2001, 40–87 | MR

[17] T. Kármán, Aerodynamics, McGraw-Hill, New York, 1963

[18] J. Kim, P. Moin, “Application of a fractional-step method to incompressible Navier–Stokes equations”, J. Comput. Phys., 59 (1985), 308–323 | DOI | MR | Zbl

[19] E. R. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, New York–London, 1973 | MR | Zbl

[20] M. Lange-Hegermann, DifferentialThomas, freely available on the web page https://wwwb.math.rwth-aachen.de/thomasdecomposition/

[21] A. Levin, Difference Algebra, Algebra and Applications, 8, Springer, 2008 | MR | Zbl

[22] K. W. Morton, D. F. Mayers, Numerical Solution of Partial Differential Equations. An Introduction, Cambridge University Press, 2005 | MR | Zbl

[23] F. Ollivier, “Standard Bases of Differential Ideals”, Applied Algebra. Algebraic Algorithms and Error-Correcting Codes, AAECC'90, LNCS, 508, ed. Sakata S., Springer, London, 1990, 304–321 | MR

[24] D. Robertz, Formal Algorithmic Elimination for PDEs, Lecture Notes in Mathematics, 2121, Springer, Berlin, 2014 | DOI | MR | Zbl

[25] D. Robertz, LDA (Linear Difference Algebra), freely available on the web page, Aachen, 2015

[26] A. A. Samarskii, Theory of Difference Schemes, Marcel Dekker, New York, 2001 | MR | Zbl

[27] W. M. Seiler, Involution: The Formal Theory of Differential Equations and its Applications in Computer Algebra, Algorithms and Computation in Mathematics, 24, Springer, Heidelberg, 2010 | DOI | MR | Zbl

[28] Yu. I. Shokin, “On conservatism of difference schemes of gas dynamics”, Tenth International Conference on Numerical Methods in Fluid Dynamics, Lecture Notes in Physics, 264, eds. F. G. Zhuang, Y. L. Zhu, Springer, Berlin, 1986, 578–583 | DOI

[29] A. F. Sidorov, V. P. Shapeev, N. N. Yanenko, Method of Differential Constraints and its Applications to Gas Dynamics, Nauka, Novosibitsk, 1984 (in Russian) | MR

[30] J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Edition, SIAM, Philadelphia, 2004 | MR | Zbl

[31] J. M. Thomas, Differential Systems, AMS Colloquium Publications, 21, 1937 ; Systems and Roots, The Wylliam Byrd Press, Rychmond, Virginia, 1962 | DOI | Zbl | Zbl

[32] J. W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Edition, Springer, New York, 1998 | MR

[33] D. V. Trushin, Difference Nullstellensatz

[34] A. Zobnin, “Admissible Orderings and Finiteness Criteria for Differential Standard Bases”, Proceedings of ISSAC 2005, ed. M. Kauers, Association for Computing Machinery, 2010, 365–372 | MR