Fast Sweeping Algorithms for a Class of Hamilton-J

FastSweepingAlgorithmsforaClassofHamilton-JacobiEquationsYen-HsiRichardTsai∗†,Li-TienCheng‡§,StanleyOsher¶†,andHong-KaiZhaokAbstractWederiveaGodunov-typenumericalfluxfortheclassofstrictlyconvex,homogeneousHamiltoniansthatincludesH(p,q)=pap2+bq2−2cpq,c2ab.WecombineourGodunovnumericalfluxeswithsimpleGauss-SeideltypeiterationsforsolvingthecorrespondingHamilton-JacobiEqua-tions.Theresultingalgorithmisfastsinceitdoesnotrequireasortingstrat-egyasfound,e.g.,inthefastmarchingmethod.Inaddition,itprovidesawaytocomputesolutionstoaclassofHJequationsforwhichtheconventionalfastmarchingmethodisnotapplicable.Ourexperimentsindicateconver-genceafterafewiterations,eveninratherdifficultcases.1IntroductionHamilton-Jacobiequationshavearichpoolofapplications,rangingfromthoseofoptimalcontroltheory,geometricaloptics,toessentiallyanyproblemthatneedsthe(weighted)distancefunction[13].Examplesincludecrystalgrowth,raytracing,etching,roboticmotionplanning,andcomputervision.Solutionsofthesetypesofequationsusuallydevelopsingularitiesintheirderivatives,andthus,theuniqueviscositysolution[5]issought.∗DepartmentofMathematicsandPACM,PrincetonUniversity,Princeton,NewJersey08644.Email:[e-mail]†ResearchsupportedbyONRN00014-97-1-0027,DARPA/NSFVIPgrantNSFDMS9615854andARODAAG55-98-1-0323‡DepartmentofMathematics,UCSD,LaJolla,CA92093-0112.Email:[e-mail]§ResearchsupportedbyNSFGrant#0112413and#0208449¶DepartmentofMathematics,UCLA,LosAngeles,California90095.Email:[e-mail]ics,UCI,Irvine,CA92697-3875.Email:[e-mail]1Inthisarticle,wefocusontheclassoftimeindependentHamilton-JacobiEqua-tionswithDirichletboundarycondition:H(x,∇u)=r(x),u|Γ=0;H(x,p)arestrictlyconvex,non-negative,andlimλ→0H(x,λp)=0.Weexplainourmethodusingthisfollowingimportantmodelequation:H(φx,φy)=qaφ2x+bφ2y−2cφxφy=r,(1)whereφ:R27→Rcontinuousanda,b,candrcaneitherbeconstantsorscalarfunctions,inwhichcaseHdependsalsoonx,definedonR2,satisfyingabc2,a,b,r0.Witha=b=1,andc=0,wehavethestandardeikonalequationforwhichmanynumericalmethodshavebeendeveloped.ThisequationhastheessentialfeaturesofHJequationswithconvexHamiltonianssothatwecaneasilyexplainouralgorithm,andisgeneralenoughthatfastmarchingisnotapplicable.Inthefollowingsubsections,wewillreviewsomeofthesolutionmethodsfortheeikonalequationsinceitformsthemotivationofourwork.WethenpresentafastGauss-Seideltypeiterationmethodforequation(1)whichutilizesamonotoneup-windGodunovfluxfortheHamiltonian.Weshownumericallythatthisalgorithmcanbeapplieddirectlytoequationsoftheabovetypewithvariablecoefficients.1.1SolvingEikonalEquationsIngeometricaloptics[9],theeikonalequationqφ2x+φ2y=r(x,y)(2)isderivedfromtheleadingterminanasymptoticexpansioneiω(φ(x,y)−t)∞Xj=0Aj(x,y,t)(iω)−jofthewaveequation:wtt−c2(x,y)(wxx+wyy)=0,wherer(x,y)=1/|c(x,y)|,isthefunctionofslowness.ThelevelsetsofthesolutionφcanthusbeinterpretedasthefirstarrivaltimeofthewavefrontthatisinitiallyΓ.Itcanalsobeinterpretedasthe“distance”functiontoΓ.2Wefirstrestrictourattentionfornowtothecaseinwhichr=1.LetΓbeaclosedsubsetofR2.Itcanbeshowneasilythatthedistancefunctiondefinedbyd(x)=dist(x,Γ):=minp∈Γ||x−p||,x=(x,y)∈R2,istheviscositysolutiontoequation(2)withtheboundaryconditionφ(x,y)=0for(x,y)∈Γ.RouyandTourin[19]provedtheconvergencetotheviscositysolutionofaniter-ativemethodsolvingequation(2)withtheGodunovHamiltonianapproximating||∇φ||.TheGodunovHamiltonianfunctioncanbewritteninthefollowingform:HG(p−,p+,q−,q+)=qmax{p+−,p−+}2+max{q+−,q−+}2(3)wherep±=Dx±φi,j,q±=Dy±φi,j,Dx±φi,j=±(φi±1,j−φi,j)/handaccordinglyforDy±φi,j,andx+=max(x,0),x−=−min(x,0).Osher[12]providedalinktotimedependenteikonalequationsbyprovingthatthet-levelsetofφ(x,y)isthezerolevelsetoftheviscositysolutionoftheevolutionequationattimetψt=||∇ψ||withappropriateinitialconditions.Infact,thesameistrueforaverygeneralclassofHamilton-Jacobiequations(see[12]).Asaconsequence,onecantrytosolvethetime-dependentequationbythelevelsetformulation[16]withhighorderapproximationsonthepartialderivatives[8][17].CrandallandLionsprovedthatthediscretesolutionobtainedwithaconsistent,monotoneHamiltonianconvergestothedesiredviscositysolution[4].Tsitsiklis[24]combinedheapsortwithavariantoftheclassicalDijkstraalgorithmtosolvethesteadystateequationofthemoregeneralproblem||∇φ||=r(x).Thiswaslaterrederivedin[22]andalsoreportedin[7].IthasbecomeknownasthefastmarchingmethodwhosecomplexityisO(Nlog(N)),whereNisthenumberofgridpoints.OsherandHelmsen[14]haveextendedthefastmarchingtypemethodtosomewhatmoregeneralHamilton-Jacobiequations.Wewillcommentonthisinafollowingsection.31.2AnisotropicEikonalEquationWereturntotheHamiltonianinquestion:H(p,q)=pap2+bq2−2cpq.Writingthequadraticformasap2+bq2−2cpq=pq
a−c−cbpq,itiseasytoseethatwecandiagonalizethesymmetricmatrixinthemiddleoftheequationforourpreviouslynotedchoicesofa,b,candfindacoordinatesystemξ-ηsuchthatafterrescaling,theHamiltonianbecomesH(˜p,˜q)=p˜p2+˜q2.Theeigensystemoftheabovematrixdefinestheanisotropy.Indeed,theauthorsin[14]proposedtosolvetheconstantcoefficientequation(1)byfirsttransformingit