A fast and accurate semi-Lagrangian particle level

AFastandAccurateSemi-LagrangianParticleLevelSetMethod¤DouglasEnrightyFrankLosassozRonaldFedkiwzOctober8,2003AbstractInthispaper,wepresentafastsemi-Lagrangianbasedparticlelevelsetmethodfortheaccuratecapturingofinterfaces.Thismethodre-tainstherobusttopologicalpropertiesofthelevelsetmethodwithouttheadverseeffectsofnumericaldissipation.Boththelevelsetmethodandtheparticlelevelsetmethodtypicallyusehighorderaccuratenumericaldiscretizationsintimeandspace,e.g.TVDRunge-KuttaandHJ-WENOschemes.Wedemonstratethatthesecomputationallyexpensiveschemesarenotrequired,ratherfast,loworderaccuratenu-mericalschemessuffice.Thatis,theadditionofparticlestothelevelsetmethodnotonlyremovesthedifficultiesassociatedwithnumericaldissipation,butalsoalleviatestheneedforcomputationallyexpensivehighorderaccurateschemes.Weuseafast,firstorderaccuratesemi-Lagrangianadvectionschemecoupledwithafirstorderaccuratefastmarchingmethodtoevolvethelevelsetfunction.Toaccuratelytracktheunderlyingflowcharacteristics,theparticlesareevolvedwithasecondorderaccuratemethod.Sinceweavoidcomplexhighorderac-curatenumericalmethods,extendingthealgorthimtoarbitrarydatastruturesbecomesmorefeasible,andweshowpreliminaryresultsob-tainedwithanoctree-basedadaptivemeshthatcapturesthesmallscalefeaturesoftheinterface.¤ResearchsupportedinpartbyanONRYIPandPECASEaward(N00014-01-1-0620),aPackardFoundationFellowship,aSloanResearchFellowship,ONRN00014-03-1-0071,ONRN00014-02-1-0720,NSFDMS-0106694,andDOEundertheASCIAcademicStrate-gicAlliancesProgram(LLNLcontractB341491).Inaddition,thefirstauthorwassup-portedinpartbyanNSFpostdoctoralfellowship(DMS-0202459).yMathematicsDepartment,UCLA,LosAngeles,CA90095.zComputerScienceDepartment,StanfordUniversity,Stanford,CA94305.11IntroductionStandardEulerianadvectionalgorithms,e.g.HJ-(W)ENOmethods[17,8]combinedwithTVD-basedhighorderaccurateRunge-Kuttaschemes[17],requireastrictboundonthemaximumpossibletimestepduetoastability-basedCFLcriterion.Ontheotherhand,particlesarenotrestrictedbythisstabilitycriterion,ratherthesizeofthetimestepusedcanbebasedsolelyonthedegreeofnumericalaccuracydesired.Gridbasedsemi-Lagrangianadvectionmethodsarelikewisenotlimitedbyastability-basedCFLcondi-tion,sinceeachgridpointistreatedina“particle-like”manner.However,semi-Lagrangianschemescansufferfromlargeamountsofnumericaldis-sipation,makingtheiruseproblematic.HJ-(W)ENOmethodsexperiencefarlessnumericaldissipationduetotheirhighorderaccurateadaptivena-ture.Inordertotakeadvantageofthestabilityaffordedbyparticlebasedmethods,thespatialandtemporalcoherencyofEulerianmethods,andtheopportunityforselectiveadaptivemeshrefinementneartheinterfaceinor-dertoresolvesmallscalefeaturesasdiscussedbelow,weproposetocoupletogetherasemi-Lagrangianadvectionschemewithacharacteristic-basedparticlemethodtotrackapassivelyadvectedinterface.Aflexibleandeasy-to-implementinterfacetrackingtechniqueisthelevelsetmethodofOsherandSethian[11].Bystoringthedistancetotheinter-faceateachpointonafixedcomputationalgrid,handlinggrosschangestointerfacetopology,e.g.pinchingandmerging,becomestrivialascomparedtostandardLagrangiantechniques[24]whichforcetheusertoexplicitlyevolveandfixamovinginterfacemesheachtimestep.Byavoidingthesedifficultiesandutilizingwellestablishednumericalalgorithmsforthesolu-tionofnonlinearhyperbolicconservationlaws,levelsetmethodshavebeenappliedtoawidevarietyofproblemsincludingfluidmechanics,computervision,materialscience,andcomputergraphics.Onedifficultywiththeuseofthelevelsetmethodistheneedtocontroltheamountofnumericaldiffusion(ormassloss)presentinthemethod,especiallyinareasofhighcurvatureandlong,thinfilamentaryregions.Variousauthors[23,21,22]haveattemptedtocorrectthisproblembyreinitializingthelevelsetfunc-tion,Á,tobesigneddistancetotheinterfaceaftereachtimestep.HighorderaccurateTVDRunge-KuttaandHJ-(W)ENOtechniquescanbeusedtoperformthisreinitialization.Whileproducingreasonableresults,thesemethodssufferfromthesameEulerian-basedadvectionissuesmentionedabovesuchassmalltimesteprestrictions.Analternativecharacteristic-baseddiffusioncorrectiontechnique,theparticlelevelsetmethod[5],hasbeenrecentlyproposed.Inthismethod,2twosetsofmarkerparticlesareplacedneartheinterface,onesetassociatedwiththeinterior(Á·0)region,andtheotherwiththeexterior(Á0)region.Errorsduetonumericaldissipationcanthenbeidentifiedwheninteriorparticlesappearintheexteriorregionorexteriorparticlesappearintheinteriorregion.Sincetheparticlesareabletomoreaccuratelytracktheunderlyingflowcharacteristics,these“escaped”particlescanbeusedtocorrectthelevelsetrepresentationoftheinterface.Theparticlelevelsetmethodhasbeenshowntopossessexcellentvolumeconservationpropertiesandahighdegreeofgeometricalaccuracyintrackingcontactdiscontinuities,comparabletootherinterfacemethodsincludingVolume-Of-Fluid(VOF)andexplicitfronttracking.Atthesametimethemethodmaintainsthehighlydesirabletopologicalpropertiesandease-of-implementationoftheoriginallevelsetmethod.Asanexampleoftheflexibilityoftheparticlelevelsetmethod,itsuseinmodelingcomplexthreedimensionalwatersurfacescanbeseenin[6,7].In[5],HJ-WENOnume