
SIGMA 2 (2006), 051, 26 pages math.RA/0605334
http://dx.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
Janetlike 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 FalkowichKarman
equations and discuss their numerical properties.
Key words:
partial differential equations; conservative difference schemes; difference algebra; linear difference ideal; Gröbner basis; Janetlike basis; computer algebra; Burgers equation; FalkowichKarman equation.
pdf (425 kb)
ps (249 kb)
tex (114 kb)
References
 Godunov S.K., Ryaben'kii V.S., Difference schemes. An introduction to
the underlying theory, New York, Elsevier, 1987.
 Strikwerda J.C., Finite difference schemes and partial differential equations, 2nd
ed., Philadelphia, SIAM, 2004.
 Ganzha V.G., Vorozhtsov E.V., Numerical solutions for partial differential equations:
problem solving using Mathematica, Boca Raton, CRC Press, 1996.
 Quarteroni A.,Valli A., Numerical approximation of partial
differential equations, 2nd ed., Berlin, SpringerVerlag, 1997.
 Thomas J.W.,
Numerical partial differential equations: finite difference
methods, 2nd ed., New York, SpringerVerlag,
1998.
 Thomas J.W.,
Numerical partial differential equations: conservation laws and
elliptic equations, New York, SpringerVerlag,
1999.
 Samarskii A.A., The theory of difference schemes, New York, Marcel Dekker, 2001.
 Morton K.W., Mayers D.F., Numerical solution of partial differential equations,
2nd ed., Cambridge, Cambridge University Press, 2005.
 Ganzha V.G., Vorozhtsov E.V.,
Computeraided analysis of difference schemes for partial
differential equations,
New York, WileyInterscience, 1996.
 Liska R., Shashkov M.Yu., Algorithms for difference schemes
construction on nonorthogonal logically rectangular meshes, in
Proceedings of ISSAC'91, New York, ACM Press, Addison Wesley,
1991, 419426.
 Liska R., Shashkov M.Y., Solovjov A.V., Supportoperators method for
PDE discretization: symbolic algorithms and realization,
Mathematics and Computers in Simulation, 1994, V.35, 173183.
 Fournié M.,
Symbolic derivation of different class of highorder schemes for
partial differential equations, in Computer Algebra in
Scientific Computing / CASC'99, SpringerVerlag, 1999, 93100.
 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, 371406.
 Mozzhilkin V.V., Blinkov Yu.A.,
Methods of constructing difference schemes in gas dynamics,
Transactions of Saratov University, 2001, V.1, N 2, 145156 (in Russian).
 Buchberger B., An algorithm for finding a basis
for the residue class ring of a zerodimensional polynomial ideal,
PhD Thesis, University of Innsbruck, Institute for Mathematics,
1965 (in German).
 Buchberger B.,Winkler F. (Editors),
Gröbner bases and applications, Cambridge University Press,
1998.
 http://www.maplesoft.com/
 http://www.wolfram.com/
 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.unikl.de/
 http://magma.maths.usyd.edu.au/magma/
 Cohn R.M., Difference algebra, Tracts in Mathematics, Vol. 17, Interscience Publishers, 1965.
 Kondratieva M.V., Levin A.B., Mikhalev A.V., Pankratiev E.V.,
Differential and difference dimension polynomials. Mathematics
and its applications,
Dordrecht, Kluwer, 1999.
 Buchberger B., Gröbner bases: an algorithmic
method in polynomial ideal theory, in Recent Trends in
Multidimensional System Theory, Dordrecht, Reidel, 1985, 184232.
 Chyzak F., Salvy B., Noncommutative elimination in Ore algebras proves multivariate identities,
J. Symbolic Computation, 1998, V.26, 187227.
 Chyzak F., Quadrat A., Robertz D., OreModules: a symbolic package for the study of
multidimensional linear systems, in Applications of TimeDelay
Systems, Editors J. Chiasson and J.J. Loiseau, Springer, to
appear (see http://wwwb.math.rwthaachen.de/OreModules).
 Greuel G.M., Levandovskyy V., Schönemann H.,
Plural. A subsystem of the computer algebra
system Singular 3.0 for computations with noncommutative
polynomial algebras, Centre for Computer
Algebra, University of
Kaiserslautern, 2005, http://www.singular.unikl.de
 Gerdt V.P., Involutive algorithms for computing Gröbner bases,
in Computational Commutative and NonCommutative Algebraic
Geometry,
Amsterdam, IOS Press, 2005, 199225, math.AC/0501111.
 http://invo.jinr.ru
 Gerdt V.P., Robertz D.,
A Maple package for computing Gröbner bases for linear
recurrence relations, cs.SC/0509070.
 Janet M., Leçons sur les Systèmes
d'Equations aux Dérivées Partielles, Cahiers Scientifiques, IV,
Paris, GauthierVillars, 1929.
 Thomas J., Differential systems, New York, American
Mathematical Society, 1937.
 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, 115137, math.AP/9909114.
 Gerdt V.P., Blinkov Yu.A.,
Janetlike monomial division. Janetlike Gröbner bases,
in Computer Algebra in Scientific Computing / CASC 2005, LNCS, Springer, 2005, 174195.
 Gerdt V.P.,
On computation of Gröbner bases for linear difference systems,
mathph/0509050.
 von zur Gathen J., Gerhard J., Modern computer algebra, 2nd ed.,
Cambridge University Press, 2003.
 Gerdt V.P., Blinkov Yu.A.,
Involutive bases of polynomial ideals. Minimal involutive bases,
Mathematics and Computers in Simulation, 1998, V.45,
519560, math.AC/9912027, math.AC/9912029.
 Apel J., Hemmecke R., Detecting unnecessary reductions in an involutive basis
computation, RISC Linz Report Series 0222, 2002.
 http://wwwsop.inria.fr/saga/POL
 http://www.math.uic.edu/~jan/demo.html
 Shokin Yu.I., Yanenko N.N.,
Method of differential approximation. Application to gas
dynamics,
Nauka, Siberian Division, 1985 (in Russian).
 Richtmyer R.D., Morton K.W., Difference methods for initialvalue
problems, 2nd ed., New York, John Wiley & Sons, 1967 (reprinted
Krieger Publishing Company, New York, 1994).
 Godunov S.K., A finite difference method for numerical
computation and discontinuous solutions of the equations of
fluid dynamics, Math. Sb., 1959, V.47, 271306 (in
Russian).
 Toro E.F., Riemann solvers and numerical methods for fluid dynamics, 2nd ed.,
Berlin, SpringerVerlag, 1997.
 Czapor S.R., Solving algebraic equations: combining Buchberger's algorithm with multivariate
factorization, J. Symbolic Computation, 1989, V.7, 4953.
 von Karman T., Collected works, von Karman Institute for Fluid Dynamics, 1975 (see
also Butterworth Scientific Publ., London, 1956).
 Bykov V., Kutmanov A., Lazman M., Elimination methods in polynomial computer algebra,
Kluwer Academic Publishers, 1997.
 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, 187.
 Spanier J.,Oldham K.B., The unitstep u(xa) and
related functions, Ch. 8, in An Atlas of Functions, Washington,
DC, Hemisphere, 1987.
 Yee H.C.,
A class of highresolution explicit and implicit shockcapturing
methods, Technical Report Lecture Series 198904, von Karman
Institute for Fluid Dynamics, 1989.
 Manizini M., Numerical methods for 1D compressible flows, an interactive book,
see here.

