Symmetry, Integrability and Geometry: Methods and Applications (SIGMA)

SIGMA 2 (2006), 051, 26 pages      math.RA/0605334      https://doi.org/10.3842/SIGMA.2006.051

Gröbner Bases and Generation of Difference Schemes for Partial Differential Equations

Vladimir P. Gerdt a, Yuri A. Blinkov b and Vladimir V. Mozzhilkin b
a) Laboratory of Information Technologies, Joint Institute for Nuclear Research, 141980 Dubna, Russia
b) Department of Mathematics and Mechanics, Saratov University, 410071 Saratov, Russia

Received December 07, 2005, in final form April 24, 2006; Published online May 12, 2006

Abstract
In this paper we present an algorithmic approach to the generation of fully conservative difference schemes for linear partial differential equations. The approach is based on enlargement of the equations in their integral conservation law form by extra integral relations between unknown functions and their derivatives, and on discretization of the obtained system. The structure of the discrete system depends on numerical approximation methods for the integrals occurring in the enlarged system. As a result of the discretization, a system of linear polynomial difference equations is derived for the unknown functions and their partial derivatives. A difference scheme is constructed by elimination of all the partial derivatives. The elimination can be achieved by selecting a proper elimination ranking and by computing a Gröbner basis of the linear difference ideal generated by the polynomials in the discrete system. For these purposes we use the difference form of Janet-like Gröbner bases and their implementation in Maple. As illustration of the described methods and algorithms, we construct a number of difference schemes for Burgers and Falkowich-Karman equations and discuss their numerical properties.

Key words: partial differential equations; conservative difference schemes; difference algebra; linear difference ideal; Gröbner basis; Janet-like basis; computer algebra; Burgers equation; Falkowich-Karman equation.

pdf (425 kb)   ps (249 kb)   tex (114 kb)

References

  1. Godunov S.K., Ryaben'kii V.S., Difference schemes. An introduction to the underlying theory, New York, Elsevier, 1987.
  2. Strikwerda J.C., Finite difference schemes and partial differential equations, 2nd ed., Philadelphia, SIAM, 2004.
  3. Ganzha V.G., Vorozhtsov E.V., Numerical solutions for partial differential equations: problem solving using Mathematica, Boca Raton, CRC Press, 1996.
  4. Quarteroni A.,Valli A., Numerical approximation of partial differential equations, 2nd ed., Berlin, Springer-Verlag, 1997.
  5. Thomas J.W., Numerical partial differential equations: finite difference methods, 2nd ed., New York, Springer-Verlag, 1998.
  6. Thomas J.W., Numerical partial differential equations: conservation laws and elliptic equations, New York, Springer-Verlag, 1999.
  7. Samarskii A.A., The theory of difference schemes, New York, Marcel Dekker, 2001.
  8. Morton K.W., Mayers D.F., Numerical solution of partial differential equations, 2nd ed., Cambridge, Cambridge University Press, 2005.
  9. Ganzha V.G., Vorozhtsov E.V., Computer-aided analysis of difference schemes for partial differential equations, New York, Wiley-Interscience, 1996.
  10. Liska R., Shashkov M.Yu., Algorithms for difference schemes construction on non-orthogonal logically rectangular meshes, in Proceedings of ISSAC'91, New York, ACM Press, Addison Wesley, 1991, 419-426.
  11. Liska R., Shashkov M.Y., Solovjov A.V., Support-operators method for PDE discretization: symbolic algorithms and realization, Mathematics and Computers in Simulation, 1994, V.35, 173-183.
  12. Fournié M., Symbolic derivation of different class of high-order schemes for partial differential equations, in Computer Algebra in Scientific Computing / CASC'99, Springer-Verlag, 1999, 93-100.
  13. Köller R., Mohl K.D., Schramm H., Zeitz M., Kienle A., Mangold M., Stein E., Gilles E., Method of lines within the simulation environment DIVA for chemical processes, in Adaptive Method of Lines, Chapmann and Hall, 2001, 371-406.
  14. Mozzhilkin V.V., Blinkov Yu.A., Methods of constructing difference schemes in gas dynamics, Transactions of Saratov University, 2001, V.1, N 2, 145-156 (in Russian).
  15. Buchberger B., An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal, PhD Thesis, University of Innsbruck, Institute for Mathematics, 1965 (in German).
  16. Buchberger B.,Winkler F. (Editors), Gröbner bases and applications, Cambridge University Press, 1998.
  17. http://www.maplesoft.com/
  18. http://www.wolfram.com/
  19. Greuel G.-M., Pfister G., Schönemann H., Singular 3.0. A computer algebra system for polynomial computations, Centre for Computer Algebra, University of Kaiserslautern, 2005, http://www.singular.uni-kl.de/
  20. http://magma.maths.usyd.edu.au/magma/
  21. Cohn R.M., Difference algebra, Tracts in Mathematics, Vol. 17, Interscience Publishers, 1965.
  22. Kondratieva M.V., Levin A.B., Mikhalev A.V., Pankratiev E.V., Differential and difference dimension polynomials. Mathematics and its applications, Dordrecht, Kluwer, 1999.
  23. Buchberger B., Gröbner bases: an algorithmic method in polynomial ideal theory, in Recent Trends in Multidimensional System Theory, Dordrecht, Reidel, 1985, 184-232.
  24. Chyzak F., Salvy B., Non-commutative elimination in Ore algebras proves multivariate identities, J. Symbolic Computation, 1998, V.26, 187-227.
  25. Chyzak F., Quadrat A., Robertz D., OreModules: a symbolic package for the study of multidimensional linear systems, in Applications of Time-Delay Systems, Editors J. Chiasson and J.-J. Loiseau, Springer, to appear (see http://wwwb.math.rwth-aachen.de/OreModules).
  26. Greuel G.-M., Levandovskyy V., Schönemann H., Plural. A subsystem of the computer algebra system Singular 3.0 for computations with non-commutative polynomial algebras, Centre for Computer Algebra, University of Kaiserslautern, 2005, http://www.singular.uni-kl.de
  27. Gerdt V.P., Involutive algorithms for computing Gröbner bases, in Computational Commutative and Non-Commutative Algebraic Geometry, Amsterdam, IOS Press, 2005, 199-225, math.AC/0501111.
  28. http://invo.jinr.ru
  29. Gerdt V.P., Robertz D., A Maple package for computing Gröbner bases for linear recurrence relations, cs.SC/0509070.
  30. Janet M., Leçons sur les Systèmes d'Equations aux Dérivées Partielles, Cahiers Scientifiques, IV, Paris, Gauthier-Villars, 1929.
  31. Thomas J., Differential systems, New York, American Mathematical Society, 1937.
  32. Gerdt V.P., Completion of linear differential systems to involution, in Computer Algebra in Scientific Computing CASC'99, Editors V.G. Ganzha, E.W. Mayr and E.V. Vorozhtsov, Berlin, Springer, 1999, 115-137, math.AP/9909114.
  33. Gerdt V.P., Blinkov Yu.A., Janet-like monomial division. Janet-like Gröbner bases, in Computer Algebra in Scientific Computing / CASC 2005, LNCS, Springer, 2005, 174-195.
  34. Gerdt V.P., On computation of Gröbner bases for linear difference systems, math-ph/0509050.
  35. von zur Gathen J., Gerhard J., Modern computer algebra, 2nd ed., Cambridge University Press, 2003.
  36. Gerdt V.P., Blinkov Yu.A., Involutive bases of polynomial ideals. Minimal involutive bases, Mathematics and Computers in Simulation, 1998, V.45, 519-560, math.AC/9912027, math.AC/9912029.
  37. Apel J., Hemmecke R., Detecting unnecessary reductions in an involutive basis computation, RISC Linz Report Series 02-22, 2002.
  38. http://www-sop.inria.fr/saga/POL
  39. http://www.math.uic.edu/~jan/demo.html
  40. Shokin Yu.I., Yanenko N.N., Method of differential approximation. Application to gas dynamics, Nauka, Siberian Division, 1985 (in Russian).
  41. Richtmyer R.D., Morton K.W., Difference methods for initial-value problems, 2nd ed., New York, John Wiley & Sons, 1967 (reprinted Krieger Publishing Company, New York, 1994).
  42. Godunov S.K., A finite difference method for numerical computation and discontinuous solutions of the equations of fluid dynamics, Math. Sb., 1959, V.47, 271-306 (in Russian).
  43. Toro E.F., Riemann solvers and numerical methods for fluid dynamics, 2nd ed., Berlin, Springer-Verlag, 1997.
  44. Czapor S.R., Solving algebraic equations: combining Buchberger's algorithm with multivariate factorization, J. Symbolic Computation, 1989, V.7, 49-53.
  45. von Karman T., Collected works, von Karman Institute for Fluid Dynamics, 1975 (see also Butterworth Scientific Publ., London, 1956).
  46. Bykov V., Kutmanov A., Lazman M., Elimination methods in polynomial computer algebra, Kluwer Academic Publishers, 1997.
  47. Jameson A., Transonic flow calculations, von Karman Institute for Fluid Dynamics Lecture Series, Vol. 87, 1976;
    Jameson A., Numerical methods in fluid dynamics, Hemisphere, 1978, 1-87.
  48. Spanier J.,Oldham K.B., The unit-step u(x-a) and related functions, Ch. 8, in An Atlas of Functions, Washington, DC, Hemisphere, 1987.
  49. Yee H.C., A class of high-resolution explicit and implicit shock-capturing methods, Technical Report Lecture Series 1989-04, von Karman Institute for Fluid Dynamics, 1989.
  50. Manizini M., Numerical methods for 1D compressible flows, an interactive book, see here.

Previous article   Next article   Contents of Volume 2 (2006)