Parallel algorithm with spectral convergence for n

arXiv:physics/0202062v1[physics.comp-ph]26Feb2002Parallelalgorithmwithspectralconvergencefornonlinearintegro-differentialequationsBogdanMihaila††PhysicsDivision,ArgonneNationalLaboratory,Argonne,IL60439E-mail:[e-mail]‡‡DepartmentofAppliedStatisticsandComputerScience,UniversityofNewBrunswick,SaintJohn,NBCanadaE2L4L5E-mail:[e-mail]ithmforsolvingnonlinearintegro-differentialequations,andillustrateourfindingsfortheparticularcaseofVolterratypeequations.ThealgorithmcombinesaperturbationapproachmeanttorenderalinearizedversionoftheproblemandaspectralmethodwhereunknownfunctionsareexpandedintermsofChebyshevpolynomials(El-gendi’smethod).Thisapproachisshowntobesuitableforthecalculationoftwo-pointGreenfunctionsrequiredinnexttoleadingorderstudiesoftime-dependentquantumfieldtheory.PACSnumbers:02.70.-c,02.30.Mv,02.60.Jh,02.70.Bf,02.60.Nm,02.60.LjSubmittedto:J.Phys.A:Math.Gen.Parallelalgorithmwithspectralconvergence21.IntroductionAstrophysicalapplicationsrelatedtothephysicsoftheearlyuniverse,aswellaschallengesposedbythephysicsprogramsatnewheavyionaccelerators,havetriggeredarenewedinterestintheunderstandingofrealtimeprocessesinthecontextofquantumfieldtheory.Withtheadventofnewcomputertechnologyandtherecentsuccessofnewcomputationalschemes,non-equilibriumphenomenawhichhavebeenpreviouslystudiedonlyintheframeworkmean-fieldtheory[1,2,3],arenowbeingrevisited,andmorecomplexnexttoleadingorderapproaches[4,5,6,7]arebeingusedinanattempttoclarifytheroleplayedbytherescatteringmechanism,whichisresponsiblefordrivinganoutofequilibriumsystembacktoequilibrium.Ofparticularinterestisthestudyofthedynamicsofphasetransitionsandparticleproductionfollowingarelativisticheavy-ioncollision.OnewayofapproachingthisstudyisbasedonsolvingSchwingerDysonequationswithintheclosedtimepath(CTP)formulation[8].Thisformalismhasbeenrecentlyshowntoprovidegoodapproximationsoftherealtimeevolutionofthesystembothinquantummechanicsand1+1dimensionalclassicalfieldtheory[9],wheredirectcomparisonswithexactcalculationscanbeperformed.Thekeyelementincarryingoutsuchstudiesisrelatedtothecalculationofthetwo-pointGreenfunction,whichissolvedforself-consistentlywiththeequationsofmotionforthefields.Thetwo-pointGreenfunctiongivesrisetoVolterra-typeintegralorintegro-differentialequations.Intheprocessofextendingourstudytoencompassahighernumberofspatialdimensions,i.e.2+1and3+1fieldtheory,wearefacedwiththechallengeofcopingwithconstraintsdictatedbothbystorageandtime-relatedcomputationallimits.Thusourinterestindesigningalgorithmswhichfeaturespectralconvergenceinordertoachieveconvergencewithminimumstoragerequirements.Inaddition,wealsodesirethesealgorithmstoscalewhenportedtomassivelymultiprocessor(MPP)machines,sothatsolutionscanbeobtainedinareasonableamountoftime.AlgorithmsforVolterraintegralandintegro-differentialequationsusuallystartoutatthelowerendofthedomain,a,andmarchoutfromx=a,buildingupthesolutionastheygo[10].Suchmethodsareserialbynature,andare,ingeneral,notsuitableforparallelimplementationonaMPPmachine.Evenso,cleverapproachestoalreadyexistingmethodscanprovidealgorithmsthattakeadvantageofaparallelprocessingcomputer:Shaw[11]hasshownrecentlythatoncethestartingvaluesoftheapproximationareobtained,onecandesignaglobalapproachwheresuccessiveapproximationsofthesolutionovertheentiredomainx∈[a,b]canbeevaluatedsimultaneously.Inarecentpaper[12]oneofushasdiscussedaspectralmethod[13]ofsolvingsometypesofequationsofinterestforthestudyoftime-dependentnonequilibriumproblemsinquantumfieldtheory.ThegistofthemethodconsistsinexpandingouttheunknownfunctionintermsofChebyshevpolynomialsonasuitablegrid,thusreducingtheproblemtofindingthenumericalsolutionofasystemoflinearequations.ThemainParallelalgorithmwithspectralconvergence3advantageofthismethodoverstandardfinite-differencetypemethodsresidesinthespectralcharacterofitsconvergence.ThisisrelatedinparttothefactthatChebyshevtypemethodsuseanon-uniformgrid,whilefinite-differencemethodsrequireauniformgrid.Usuallythereisatrade-offbetweencomputationaltimeandstoragerequirements,andabalancedsolutionmustbereachedonacase-by-casebasis.Spectralmethodsaremoreexpensiveperpointasthematricesmaybeconsiderablydenserthaninthefinite-differencecase,butwerequireconsiderablyfewergridpointsinordertoachievethesamedegreeofaccuracy.ByexpandingtheunknownfunctiononacompactsupportinChebyshevpolynomialsandusingapartitionofthedomainbasedeitheronthesetof(N+1)extremaorthesetofNzerosofTN(x)–theChebyshevpolynomialoffirstkindofdegreeN–weinfactreplaceacontinuousproblembyadiscreteone.Fornon-singularfunctionsthediscreteorthogonalityandcompletenessrelationsforChebyshevpolynomialsattheabovegridpointsassureadefactoexactexpansionforanarbitraryfinitevalueN.Inpracticehowever,onehastocomputederivativesandintegralsoftheunknownfunctionatthecollocationpoints,andtheChebyshevexpansionprovidesonlyanapproximationforthesesubsequentcomputations.Theseerrors,togetherwiththefiniteaccuracyofnumericalmethodsneededinconjunctionwiththeChebyshevexpansion,conspireinordertodeterioratethea