Grobner Bases and Generation of Difference Schemes

arXiv:math/0605334v1[math.RA]12May2006Symmetry,IntegrabilityandGeometry:MethodsandApplicationsVol.2(2006),Paper051,26pagesGr¨obnerBasesandGenerationofDifferenceSchemesforPartialDifferentialEquationsVladimirP.GERDT†,YuriA.BLINKOV‡andVladimirV.MOZZHILKIN‡†LaboratoryofInformationTechnologies,JointInstituteforNuclearResearch,141980Dubna,RussiaE-mail:[e-mail]:‡DepartmentofMathematicsandMechanics,SaratovUniversity,410071Saratov,RussiaE-mail:[e-mail]:://¨obnerbasisofthelineardifferenceidealgeneratedbythepolynomialsinthediscretesystem.ForthesepurposesweusethedifferenceformofJanet-likeGr¨obnerbasesandtheirimplementationinMaple.Asillustrationofthedescribedmethodsandal-gorithms,weconstructanumberofdifferenceschemesforBurgersandFalkowich–Karmanequationsanddiscusstheirnumericalproperties.Keywords:partialdifferentialequations;conservativedifferenceschemes;differenceal-gebra;lineardifferenceideal;Gr¨obnerbasis;Janet-likebasis;computeralgebra;Burgersequation;Falkowich–Karmanequation2000MathematicsSubjectClassification:68W30;65M06;13P10;39A05;65Q051IntroductionItiswell-knownthatfinitedifferencesalongwithfiniteelementsandfinitevolumesaremostimportantdiscretizationschemesfornumericalsolvingofpartialdifferentialequations(PDEs)(see,forexample,[1,2,3,4,5,6,7,8]).MathematicaloperationsusedintheconstructionofdifferenceschemesforPDEsaresub-stantiallysymbolic.Thereby,itisachallengeforcomputeralgebratoprovideanalgorithmictoolforautomatizationofthedifferenceschemesconstructingaswellasfortheinvestigationofpropertiesofthedifferenceschemes.Oneofthemostfundamentalrequirementsforadifferenceschemeisitsstabilitywhichcanbeanalyzedwiththeuseofcomputeralgebramethodsandsoftware[9].Furthermore,ifPDEsadmitaconservationlawformor/andhavesomesymmetries,itisworthwhiletopreservethesefeaturesatthelevelofdifferenceschemestoo.Inparticular,atoolforautomaticconstructionofdifferenceschemesshouldproduceconservativeschemes2V.P.Gerdt,Yu.A.BlinkovandV.V.MozzhilkinwhenevertheoriginalPDEscanbewrittenintheintegralconservationlawform.OneofsuchtoolsGRIDOPwritteninReduce[10,11]isbasedonsymbolicoperatormethodsandgeneratesconservativefinite-differenceschemesonrectangulardomainsinanarbitrarynumberofindependentvariables.However,thegenerationisnotentirelyautomatic.AuserofGRIDOPhastospecifyfunctionspacestogetherwithassociatedscalarproductsanddefinegridoperatorsasfinite-differenceschemes.Thentheusermayprovidepartialdifferentialequationsintermsofthedefinedgridoperatorsortheadjointsofthoseoperators.Undertheseconditionsthepackagereturnsthefinite-differenceequationsforthedependentvariables.Besides,afewotherapplicationsofcomputeralgebraareknowntoconstructfinite-differenceschemes[12,13]which,beingalsonotcompletelyautomatic,areapplicabletoPDEsofacertainform.InthispaperwedescribeauniversalalgorithmicapproachtotheautomaticgenerationofconservativedifferenceschemesforlinearPDEswithtwoindependentvariablesadmittingtheconservationlawform.Thisapproachgeneralizesandextendstheobservationsofpaper[14]whereitwasnoticedthataconservativedifferenceschemecanbederivedasacompatibilityconditionforasystemofdifferenceequations.ThesystemiscomposedofadiscreteformoftheoriginalPDEstakenintheintegralconservationlawformandofanumberofnaturalintegralrelationsbetweenfunctionsandtheirpartialderivatives.Thefinite-differenceschemeisobtainedbyeliminationofallthepartialderivativesfromthesystem.Wealsoshow,bytheexampleofBurgersequation,thatonecanalsoapplythedifferenceeliminationapproachtogenerateofdifferenceschemeswithoutuseofconservationlawform.ToperformthedifferenceeliminationweapplytheGr¨obnerbasesmethodinvented40yearsagobyBuchberger[15]forpolynomialideals.Thismethodhasbecomethemostuniversalalgorithmictoolincommutativealgebraandalgebraicgeometryandfoundalsonumerousfruitfulapplicationsforcomputationsincertainnoncommutativepolynomialringsaswellasinringsoflineardifferentialoperatorsanddifferentialpolynomials[16].Nowadays,allmoderngeneral-purposecomputeralgebrasystems,forexample,Maple[17]andMathematica[18],havespecialbuilt-inmodulesimplementingalgorit