DISCONTINUOUSGALERKINMETHODSFORHAMILTON-JACOBIEQUATIONS ANDHIGH-DIMENSIONALELLIPTICEQUATIONS By ZixuanWang ADISSERTATION Submittedto MichiganStateUniversity inpartialentoftherequirements forthedegreeof AppliedMathematics{DoctorofPhilosophy 2015 ABSTRACT DISCONTINUOUSGALERKINMETHODSFORHAMILTON-JACOBI EQUATIONSANDHIGH-DIMENSIONALELLIPTICEQUATIONS By ZixuanWang Thisthesisfocusesontworelatedtopics,whicharetodesigntdiscontinuous Galerkin(DG)schemesforHamilton-Jacobi(HJ)equationsandhigh-dimensionalelliptic equations. Inthepart,weproposeanewDGmethodthatsolvesfortheviscositysolution ofthegeneralHJequations.Thenewmethodiscompactandeasytoimplement.We avoidthereconstructionofthesolutionacrosselementsbyutilizingtheinterfacialterms involvingtheRoespeed.Apenaltytermproportionaltothejumpofthenormalderivative ofthenumericalsolutionisaddedtotheentropyviolation,whichwasinspiredbythe HartenandHymansentropy[53]forRoeschemefortheconservationlaws.Numerical experimentsdemonstrategoodperformanceforgeneralHamiltonians,includingnonconvex Hamiltonians. Inthesecondpart,wedevelopaninteriorpenaltyDGmethodonsparsegridsfort computationsofhigh-dimensionalsecond-orderellipticproblems.Usingahierarchicalbasis representation,weconstructasparseelementapproximationspace,reducingthedegree offreedomfromthestandard O ( h d )to O ( h 1 j log 2 h j d 1 )for d -dimensionalproblems, where h istheuniformmeshsizeineachdimension.Comparedtothetraditionalfullgrid approaches,theaccuracyofthenumericalapproximationofthismethodisonlyslightly deterioratedbyafactorof j log 2 h j d 1 intheenergynorm.Errorestimatesareprovidedand bynumericaltestsinmulti-dimensions. ACKNOWLEDGMENTS Firstandforemost,Iwanttoexpressmydeepestappreciationtomyadvisor,Professor YingdaCheng,forherinvaluableencouragement,guidanceandsupportduringmygraduate study.ItistrulyagreathonorformetobeherPh.D.student.Shehasbeena tremendousmentorandhasalwaysbeenthereformewheneverIneedherhelp.This dissertationwouldnothavebeenpossiblewithoutherexpertiseinnumericalanalysisand inspirationalsuggestionsontheprojects. MysincerethanksalsogotoProfessorAndrewChristlieb,forleadingmeintotheof sciencomputingandinsightfuladvicesthroughouttheseyears.Iwouldalsolike tothanktherestofmycommitteemembers,ProfessorJianliangQianforteachingmelots ofknowledge,andProfessorChichiaChiuandProfessorZhengfangZhoufortheircritical commentsandvaluablefeedbacks.AndIamindebtedtomyundergraduateadvisorProfessor KangshengLiuforhisacademicsupportandforgivingmesomanywonderfulopportunities. IalsowanttoacknowledgemydearfriendsYuanLiu,WeiGuo,XinghuiZhong,Xianfeng Hu,LipingChen,LiangminZhou,XinYangandQinfengGaofortheirfriendshipsandhelps. Lastbutnottheleast,Iameternallygratefultomyparents,JianchengWangandJunyan Li,andmylittlesisterZirunWang,whosepersistentsupportandunconditionallovemade mewhoIamtoday.Mydeepestgratitudegoestomyhusband,QiTang,forlovingmeand alwaysbeingthereformethroughthisentirejourney.Yourlovemakesmefeelathome whereverwego. iii TABLEOFCONTENTS LISTOFTABLES .................................... v LISTOFFIGURES ................................... viii Chapter1Introduction ............................... 1 1.1Overview......................................1 1.2NumericalMethodsforHJEquations......................2 1.3ReviewofDGSchemesforEllipticEquations.................4 1.4SparseGridMethodsforHigh-dimensionalPDEs...............5 Chapter2DGMethodforDirectlySolvingtheHamilton-JacobiEquations8 2.1SchemeinOneDimension............................9 2.1.1One-dimensionalFormulation......................9 2.1.2InterpretationoftheScheme.......................11 2.2SchemeonTwo-dimensionalCartesianMeshes.................16 2.3SchemeonGeneralUnstructuredMeshes....................20 2.4NumericalResults.................................21 2.4.1One-dimensionalResults.........................22 2.4.2Two-dimensionalResults.........................34 Chapter3SparseGridDGMethodsforHigh-DimensionalEllipticEqua- tions .................................... 46 3.1DGFiniteElementSpacesonSparseGrids...................48 3.1.1HierarchicalDecompositionofPiecewisePolynomialSpacesinOne Dimension.................................48 3.1.2SparseDiscontinuousFiniteElementSpacesinMulti-dimensions...54 3.1.3ApproximationResults..........................61 3.1.4ApproximationsfromVariousSparseDiscontinuousFiniteElement Spaces:ANumericalInvestigation...................63 3.2IPMethodonSparseGridsforEllipticEquations...............74 3.2.1FormulationoftheScheme........................74 3.2.2ErrorAnalysis...............................77 3.3NumericalResults.................................81 3.3.1Two-dimensionalResults.........................81 3.3.2Three-dimensionalResults........................84 3.3.3Four-dimensionalResults.........................88 Chapter4Conclusion ................................ 92 BIBLIOGRAPHY .................................... 94 iv LISTOFTABLES Table2.1:ErrorsandnumericalordersofaccuracyforExample2.4.1whenus- ing P k , k =1 ; 2 ; 3,polynomialsandthirdorderRunge-Kuttatime discretizationonauniformmeshof M cells.Finaltime t =1.....23 Table2.2:ErrorsandnumericalordersofaccuracyforExample2.4.2whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M cells.Finaltime t =1. CFL =0 : 1.......26 Table2.3:ErrorsandnumericalordersofaccuracyforExample2.4.3whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M cells.Penaltyconstant C =0 : 25.Finaltime t =0 : 5. CFL =0 : 1............................27 Table2.4:ErrorsandnumericalordersofaccuracyforExample2.4.3whenusing P 1 and P 2 polynomialsandthirdorderRunge-Kuttatimediscretiza- tiononarandommeshwith40%perturbationof M cells.Penalty constant C =0 : 25.Finaltime t =0 : 5. CFL =0 : 1...........27 Table2.5:ErrorsandnumericalordersofaccuracyforExample2.4.5whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M cells.Penaltyconstant C =0 : 25.Finaltime t =1. CFL =0 : 1.............................30 Table2.6:ErrorsandnumericalordersofaccuracyforExample2.4.6whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M cells.Penaltyconstants C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1..........................31 Table2.7:ErrorsandnumericalordersofaccuracyforExample2.4.7whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M cells. CFL =0 : 05.Penaltyconstant C =0 : 25. Finaltime t =1.Aminmodlimiterisused..............32 Table2.8:ErrorsandnumericalordersofaccuracyforExample2.4.8whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M M cells.Finaltime t =1. CFL =0 : 1....35 Table2.9:ErrorsandnumericalordersofaccuracyforExample3.9whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationon auniformmeshof M M cells.Finaltime t =1. CFL =0 : 1....36 v Table2.10:ErrorsandnumericalordersofaccuracyforExample2.4.10whenus- ing P 2 polynomialsandthirdorderRunge-Kuttatimediscretization ontriangularmesheswithcharacteristiclength h .Penaltyconstant C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1.............37 Table2.11:ErrorsandnumericalordersofaccuracyforExample2.4.11whenus- ing P 2 polynomialsandthirdorderRunge-Kuttatimediscretization onauniformmeshof M M cells.Penaltyconstant C =0 : 25.Final time t =0 : 8. CFL =0 : 1........................38 Table2.12:ErrorsandnumericalordersofaccuracyforExample2.4.13whenus- ing P 2 polynomialsandthirdorderRunge-Kuttatimediscretization ontriangularmesheswithcharacteristiclength h .Penaltyconstant C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1.............40 Table3.1:Orthonormal,vanishing-momentfunctions f 1 ; ;f k +1 ,for k =0 ; ; 4, for x 2 (0 ; 1).Thefunctions f i isextendedtotheinterval( 1 ; 1)as anoddorevenfunctionbasedontherule f i ( x )=( 1) i + k f i ( x )for x 2 ( 1 ; 0),andiszeroelsewhere....................51 Table3.2: L 2 projectionerrorsandordersofaccuracy.FGDOFdenotesthe degreesoffreedomofthefullgridapproximationspace. d =2. k =1.68 Table3.3:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegrees offreedomofthefullgridapproximationspace. d =2. k =2.....69 Table3.4:Projectionerrorsandordersofaccuracy.FGDOFdenotesthede- greesoffreedomofthefullgridapproximationspace. d =2. k =3.70 Table3.5:Projectionerrorsandordersofaccuracy.FGDOFdenotesthede- greesoffreedomofthefullgridapproximationspace. d =3. k =1.71 Table3.6:Projectionerrorsandordersofaccuracy.FGDOFdenotesthede- greesoffreedomofthefullgridapproximationspace. d =3. k =2.72 Table3.7:Projectionerrorsandordersofaccuracy.FGDOFdenotesthede- greesoffreedomofthefullgridapproximationspace. d =3. k =3.73 Table3.8:NumericalerrorsandordersofaccuracyforExample3.3.1computed byspace ^ V k N with k =1 ; 2andindicated N ..............82 Table3.9:Sparsityandconditionnumberofthematrix.Example3.3.1 computedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeof freedomusedforthesparsegridDGscheme.NNZisthenumberof nonzeroelementsinthematrix.Order=log(NNZ) = log(SGDOF) : 83 vi Table3.10:NumericalerrorsandordersofaccuracyforExample3.3.2computed bythespace ^ V k N with k =1 ; 2andindicated N ............84 Table3.11:NumericalerrorsandordersofaccuracyforExample3.3.3computed bythespace ^ V k N with k =1 ; 2andindicated N ............85 Table3.12:NumericalerrorsandordersofaccuracyforExample3.3.4computed bythespace ^ V k N with k =1 ; 2andindicated N ............86 Table3.13:Sparsityandconditionnumberofthematrix.Example3.3.4 computedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeof freedomusedforthesparsegridDGscheme.NNZisthenumberof nonzeroelementsinthematrix.Order=log(NNZ) = log(SGDOF) : 86 Table3.14:NumericalerrorsandordersofaccuracyforExample3.3.5computed bythespace ^ V k N with k =1 ; 2andindicated N ............88 Table3.15:NumericalerrorsandordersofaccuracyforExample3.3.6computed bythespace ^ V k N with k =1 ; 2andindicated N ............89 Table3.16:Sparsityandconditionnumberofthematrix.Example3.3.6 computedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeof freedomusedforthesparsegridDGscheme.NNZisthenumberof nonzeroelementsinthematrix.Order=log(NNZ) = log(SGDOF) : 90 Table3.17:NumericalerrorsandordersofaccuracyforExample3.3.7computed bythespace ^ V k N with k =1 ; 2andindicated N ............91 vii LISTOFFIGURES Figure2.1:Example2.4.2.Thenumericalsolutionwithvariousvaluesofpenalty constant C :(a) C =0,(b) C =0 : 001,(c) C =0 : 25,and(d) C =1. Here t =1, CFL =0 : 1, P 2 polynomials, M =80.Solidline:the exactsolution;circles:thenumericalsolution. Forinterpretation ofthereferencestocolorinthisandallotheres,thereaderis referredtotheelectronicversionofthisthesis. ............25 Figure2.2:Example2.4.3.Here t =1 : 5, CFL =0 : 1, P 2 polynomials, M =40. Penaltyconstant C =0 : 25.Solidline:theexactsolution;circles:the numericalsolution............................28 Figure2.3:Example2.4.4.Thenumericalsolutionwithvariousvaluesofpenalty constant C :(a) C =0,(b) C =0 : 001,(c) C =0 : 25,and(d) C =1 : 0. Here t =1, CFL =0 : 1, P 2 polynomials, M =80.Solidline:the exactsolution;circles:thenumericalsolution.............29 Figure2.4:Example2.4.6.Here t =1 : 5 =ˇ 2 , CFL =0 : 1, P 2 polynomials, M = 80.Penaltyconstant C =0 : 25.Solidline:theexactsolution;circles: thenumericalsolution..........................31 Figure2.5:Example2.4.7.Comparisonofthenumericalsolutionwithandwith- outthelimiter:(a) M =80,withoutlimiter;(b) M =80,with limiter;(c) M =81,withoutlimiter;and(d) M =81,withlimiter. Here t =1, P 2 polynomials, CFL =0 : 05.Penaltyconstant C =0 : 25. Solidline:theexactsolution;circles:thenumericalsolution.....33 Figure2.6:Example2.4.8.Here t =2 ˇ , CFL =0 : 1,80 80uniformmesh. (a) P 1 polynomials;(b) P 2 polynomials.Onedimensionalcutof45 withthe x axis.Solidline:theexactsolution;circles:thenumerical solution..................................35 Figure2.7:Examples2.4.10and2.4.13.Theunstructuredmeshusedwithchar- acteristiclength h =1 = 4........................37 Figure2.8:Example2.4.10.Here CFL =0 : 1, P 2 polynomials.Triangularmesh withcharacteristiclength1 = 8.2816elements.Penaltyconstant C = 0 : 25.(a) t =0 : 5 =ˇ 2 ;(b) t =1 : 5 =ˇ 2 ..................38 Figure2.9:Example2.4.11.Here CFL =0 : 1, P 2 polynomialsona80 80 uniformmesh.Penaltyconstant: C =0 : 25.(a) t =0 : 8;(b) t =1 : 5.39 viii Figure2.10:Example2.4.12.Here t =1, CFL =0 : 1, P 2 polynomialsona 40 40uniformmesh.Penaltyconstant: C =0 : 25.(a)thenumerical solution;(b)sign( ' y )..........................40 Figure2.11:Example2.4.13.Here CFL =0 : 1, P 2 polynomials.Triangularmesh withcharacteristiclength1 = 8.2816elements.Penaltyconstant: C =0 : 25.(a) t =0 : 5 =ˇ 2 .(b) t =1 : 5 =ˇ 2 ................41 Figure2.12:Example2.4.14.Here t =1, CFL =0 : 1, P 2 polynomialsona41 41 uniformmesh.Penaltyconstant: C =0 : 25..............41 Figure2.13:Example2.4.15.Theunstructuredmeshusedinthecomputation. Numberofelements:3480........................42 Figure2.14:Example2.4.15. CFL =0 : 1. P 2 polynomials.Penaltyconstant: C =0 : 25.Thenumericalsolutionattheindicatedtimes.......43 Figure2.15:Example2.4.16.Theunstructuredmeshusedinthecomputation. Numberofelements:5890........................44 Figure2.16:Example2.4.16.Here CFL =0 : 1, P 2 polynomials.Penaltyconstant: C =0 : 25.Thenumericalsolutionattheindicatedtimes.......45 Figure3.1:Example3.3.1.Thesparsitypattensofthematricescomputedbythe space ^ V k 6 with k =1 ; 2andN=6.Eachdotrepresentsanon-zero elementinthematrix.(a): k =1,(b): k =2 : ........83 Figure3.2:Example3.3.4.Thesparsitypattensofthematricescomputedbythe space ^ V k 6 with(a) k =1and(b) k =2.N=6.............87 Figure3.3:Example3.3.6.(a) k =1;(b) k =2. N =4.Plottedalong x 1 =0 : 4930 ;x 2 =0 : 4930........................89 Figure3.4:Example3.3.6.Thesparsitypattensofthematricescomputedbythe space ^ V k 4 with(a) k =1and(b) k =2................90 ix Chapter1 Introduction 1.1Overview EversincethediscontinuousGalerkin(DG)elementmethodwasdevelopedby ReedandHilltosolvetheconservationlaws,theuseofDGdiscretizationshasbecome morewidespread.TheappealofDGmethodsrelatestotheirlitytochoosebases, combinedwithcompactstencilsandfavorablepropertiesforarbitrarilyunstructuredmeshes. Moreover,DGmethodsgenerallyareabletocapturethephysicallyrelevantdiscontinuities accuratelyforproblemswithroughsolutions.DGmethodsalsohaveexcellentparallel andcaneasilyaccommodatethe hp -adaptivity.Therefore,DGmethodshave attractedinterestofmanyresearchersandpractitionersandhavebeenprovedusefulinthe real-worldproblemslikemeteorology,weather-forecasting,semiconductordevicesimulation, electrodynamicsandplasmaphysics. Inthisthesis,wewillfocusontheimprovementoftheDGmethodsforthegeneral Hamilton-Jacobi(HJ)equationsandthedevelopmentofsparsegridDGmethodsforhigh- dimensionalellipticproblemstomakethenumericalsimulationsmoreaccurate,tand stable. 1 1.2NumericalMethodsforHJEquations InthissectionwewillintroducetheHJequationandreviewnumericalmethodsforsolving thisequation. Weconsiderthenumericalsolutionofageneraltime-dependentHJequation ' t + H ( r x '; x )=0 ;' ( x ; 0)= ' 0 ( x ) ; x 2 2 R d (1.1) withsuitableboundaryconditionson @ TheHJequationarisesinmanyapplications,e.g., optimalcontrol,tialgames,crystalgrowth,imageprocessingandcalculusofvaria- tions.ThesolutionofsuchequationisLipschitzcontinuousbutmaydevelopdiscontinuous derivativesintimeevenwhentheinitialdataissmooth. Theviscositysolution[32,33]wasintroducedastheuniquephysicallyrelevantsolution, andhasbeenthefocusofmanynumericalmethods.Startingfrom[34,78], methodssuchasessentiallynon-oscillatory(ENO)[67,68]orweightedENO(WENO)meth- ods[58,87]havebeendevelopedtosolvetheHJequation.Thosemethods workquiteetlyforCartesianmeshes,howevertheylosetheadvantageofsimplicityon unstructuredmeshes[1,87]. Alternatively,theRunge-KuttadiscontinuousGalerkin(RKDG)method,originallyde- visedtosolvetheconservationlaws[31],ismoreforarbitrarilyunstructuredmeshes. TheworkofDGmethodsforHJequations[56,61]reliesonsolvingtheconservationlaw systembythederivativesofthesolution.Themethodsworkwellnumericallyeven onunstructuredmesh,withprovablestabilityresultsforcertainspecialcases,andwerelater generalizedine.g.[50,24].Unfortunately,theprocedureofrecovering ' fromitsderivatives hasmadethealgorithmindirectandcomplicated.Incontrast,thedesignofDGmethodsfor 2 directlysolvingtheHJequationsisappealingbutchallenging,becausetheHJequationisnot writtenintheconservativeform,forwhichtheframeworkofDGmethodscouldeasilyapply. In[25],aDGmethodfordirectlysolvingtheHJequationwasdeveloped,motivatedbythe ideathattheone-dimensionallinearHJequationcanberewrittenasaconservationlaw withasourceterm.Later,thisalgorithmwasappliedtosolvefrontpropagationproblems [15]andfrontpropagationwithobstacles[16],inwhichimplementationsofthe entropyprocedurewereproposed.Meanwhile,centralDG[62]andlocalDG[84]meth- odswererecentlydevelopedfortheHJequation.Numericalexperimentsdemonstratethat bothmethodsworkfornonconvexHamiltonians.Inaddition,theorderversionofthe localDGmethod[84]reducestothemonotoneschemesandthushasprovableconvergence properties.However,thecentralDGmethodsbasedonoverlappingmeshesareultto implementonunstructuredmeshes,andthelocalDGmethodsstillneedtoresorttothe informationaboutthederivativesof ' ,makingthemethodlessdirectincomputation. L 2 errorestimatesforsmoothsolutionsoftheDGmethod[25]andlocalDGmethod[84]have beenestablishedin[83].ForrecentdevelopmentsofhighorderandDGmethodsforHJ equations,onecanrefertothereviewpapers[74,75]. Thedirectmethodin[25]workswellnumericallyforbothlinearandconvexcases,but stillneedstoresorttothecomplicatedprocedurein[56,61]fortheentropyBasedonthe observationthatthemethodin[25]iscloselyrelatedtoRoe'slinearization,weproposeto useinterfacialtermsinvolvingtheRoespeedanddevelopanewentropythatwasinspired bytheHartenandHyman'sentropy[53]forRoeschemefortheconservationlaws.In Chapter2,wedevelopsuchadirectsolver.Moreover,wewillshowthatthenewmethod hasthefollowingadvantages.Firstly,theschemeworksonunstructuredmeshesevenfor nonconvexHamiltonian.Secondly,themethodissimpletoimplement.Thecumbersome 3 L 2 reconstructionofthesolutions'derivativeatthecellinterfacein[25]isavoided,andthe entropyisautomaticallyincorporatedbytheaddedjumptermsinthederivativesofthe numericalsolution.Finally,theschemeisdirectandcompact,andthecomputationonly needstheinformationaboutthecurrentcellanditsimmediateneighbors. 1.3ReviewofDGSchemesforEllipticEquations Ellipticequationshavebeenusedsuccessfullyinmanyapplicationareassuchasaeroacous- tics,electro-magnetism,oilrecoverysimulation,weatherforecasting,etc.Therehasbeena lotofrtonthenumericalmethodsfortheellipticequations,includingthestandard nitemethods,collocationmethods,Galerkinelementmethods,leastsquares methods,amongtheothers.DGmethodsworkwellforpurelyhyperbolicproblemsbyna- ture,yetthesemethodsalsoprovetobeusefulforellipticequations.Aspointedoutinthe reviewpaper[7],manyDGdiscretizationmethodshavebeendevelopedsuchasthemethod ofBassiandRebay[12],thevariationsin[17],andthelocalDGmethodsintroducedin [23,27,28,30]. Inthe1970s,aclassofinteriorpenalty(IP)DGelementmethodswasproposedin [6,10,37,82].TheseIPDGmethodsarosefromNitsche'sideathat,justastheDirichlet boundaryconditionscanbeimposedweaklybyaddingapenaltyterminsteadofbeingre- strictedstronglyintheapproximationspace,thecontinuityacrossinterelementboundaries couldbeattainedsimilarly.Therefore,itispossibletousethemorediscontinuous elementspaceinthispenaltytechnique.In1973,Babuska[9]proposedanotherpenal- izationtechniquetoweaklyimpose C 1 continuity.In1978,Wheeler[82]generalizedNitsche's methodtosecond-orderellipticproblemsandlaterAlnoldgeneralizedthistechniqueandan- 4 alyzedinfurtherdetailforlinearandnonlinearellipticandparabolicproblemsinhisthesis [6].AfamilyofIPDGmethods,whichincludesOden-Baumann-Babusk[66],symmetricin- teriorpenaltyGalerkin[82],nonsymmetricinteriorpenaltyGalerkin[70],incompleteinterior penaltyGalerkin[35],hasbeenproposedtodealwithellipticproblemsduringthelastfew decades.Howeversince1980s,lessattentionhasbeenpaidtoIPmethodsmainlybecause thesepenaltymethodswereneverprovedtobemoreientthanconformingelement approximationspace.Inspiteofthis,IPmethodshavetheadvantageofyinchoos- ingtheapproximationspaceandaremoresuitedfor hp -adaptivity.Forinstance,in1990, Baker[11]usedthenonconformingteelementapproximationstoenforcethedivergence- freeconditionpoint-wiseineachtrianglemeshfortheStokessystem.Theinteriorpenalties wereusedtodealwiththediscontinuityinthevelocityacrossinterelementboundaries. 1.4SparseGridMethodsforHigh-dimensionalPDEs Inthisthesis,weareconcernedwiththenumericalsolutionofhigh-dimensionalPDEs.High- dimensionalPDEshavebeenamajorchallengeinthesciencomputingareasduetothe storagerequirementsandcomputationalcomplexity.Howtoconquerthe thecurseofdi- mensionality [14]isvitaltothereal-worldproblemsassuchhigh-dimensionalproblemsoften comefromkineticsimulations,stochasticanalysis,control,optimizationandmathematical modelinginorstatistics.Examplesincludehigh-dimensionalLaplaceproblemsand high-dimensionalconvproblemswhichresultfromapproximation techniquesortheFokker{Planckequation.Thechallengeofthoseproblemstypicallycannot besimplysolvedbyincreaseofcomputationalresources,butrequirestheimprovementof numericaltechniques,bettercomputationalimplementationandusageofparallelcomput- 5 ing.Thoserentperspectivesoftreatmenthaveattractedincreasingattentionoverthe lastdecades.Amongthem,thesparsegridtechniques,introducedbyZenger[86],havebeen developedasamajortooltobreakthecurseofdimensionalityofgrid-basedapproaches. Suchapproachesrelyonatensorproducthierarchicalbasisrepresentation,andcansuc- cessfullyreducethedegreesoffreedomfromthestandard O ( h d )to O ( h 1 j log h j d 1 )for d -dimensionalproblems,where h istheuniformmeshsize.Theunderlyingideasofsparse gridtechniquescanbetracedbacktoSmolyak[77]fornumericalintegration,andthemeth- odsarecloselyrelatedtohyperboliccross[8,79],booleanmethod[36],discreteblending method[13],andsplittingextrapolationmethod[63]intheliterature.Thetrickistobal- ancethecostcomplexitiesandtheaccuracyoftheschemeandapropertruncationof thetensorproducthierarchicalbases,whichcouldbeformallyderivedbysolvinganopti- mizationproblemofcost/bratios,asdiscussedin[45].Forrecentdevelopmentsof sparsegridsmethod,werefertothesurveypaper[21]andlecturenotes[38]. Whensolvinghigh-dimensionalPDEs,besidesthenaturalchoiceoftraditionalGalerkin elementmethods[86,21,71],sparsegridshavebeenincorporatedinerence methods[44,49],volumemethods[54],andspectralmethods[46,42,72,73].However, thepotentialofsparsegridshasnotyetbeenfullyrealizedundertheDGframework,in whichdiscontinuousbasisfunctionspacesareunderconsideration.Theyandthe maturedevelopmentofDGschememakeitanexcellentcandidatetobecombinedwiththe sparsegridapproachtosolvehigh-dimensionalPDEs.InChapter3,wewilldevelopDG methodsonsparsegridsfortcomputationsofhigh-dimensionalellipticequations.Our studyconsistsofathoroughinvestigationoftheunderlyingsparseapproximationspace,its utilizationinconjunctionwiththeIPDGmethod,andthepropertiesoftheschemesimplied. Numericalresultsvalidateourtheoreticalwhichgivepromisingoutlookforthe 6 extensionoftheschemetowiderapplications. 7 Chapter2 DGMethodforDirectlySolvingthe Hamilton-JacobiEquations Inthischapter,weimproveupontheDGmethodforHJequationwithconvexHamiltonians in[25]anddevelopanewDGmethodfordirectlysolvingthegeneralHJequations.The newmethodavoidsthereconstructionofthesolutionacrosselementsbyutilizingtheRoe speedatthecellinterface.Besides,weproposeanentropybyaddingpenaltyterms proportionaltothejumpofthenormalderivativeofthenumericalsolution.Theparticular formoftheentropywasinspiredbytheHartenandHyman'sentropy[53]forRoe schemefortheconservationlaws. Therestofthischapterisorganizedasfollows:inSection2.1,weintroducethenumerical schemeforone-dimensionalHJequations.Wegeneralizetheschemetocomputeontwo- dimensionalCartesianmeshesinSection2.2andongeneralunstructuredmeshesinSection 2.2.Section2.4isdevotedtothediscussionofthenumericalresults.Benchmarknumerical experimentsinonedimensionandtwodimensionsareprovidedtovalidatetheperformance ofthemethodonbothstructuredandunstructuredmeshes. 8 2.1SchemeinOneDimension Inthissection,wewilldescribethenumericalmethodsfortheone-dimensionalequation. Wefollowthemethodoflinesapproach,andbelowwewillonlydescribethesemi-discrete DGschemes.TheresultingmethodoflinesODEscanbesolvedbythetotalvariation diminishing(TVD)Runge-Kuttamethods[76]orstrongstabilitypreserving(SSP)Runge- Kuttamethods[41]. 2.1.1One-dimensionalFormulation Inthissubsection,wewillstartwiththesimpleone-dimensionalHJequation.Inthiscase, (1.1)becomes ' t + H ( ' x ;x )=0 ;' ( x; 0)= ' 0 ( x ) : (2.1) Assumethecomputationaldomainis[ a;b ],wewilldivideitinto M cellsasfollows a = x 1 2 > < > > : H (( ' h ) x ( x + ) ;x + ) H (( ' h ) x ( x ) ;x ) ( ' h ) x ( x + ) ( ' h ) x ( x ) ; if( ' h ) x ( x + ) 6 =( ' h ) x ( x ) ; 1 2 H 1 (( ' h ) x ( x + ) ;x + )+ H 1 (( ' h ) x ( x ) ;x ) ; if( ' h ) x ( x + )=( ' h ) x ( x ) : Inthenotationsabove,weusesuperscripts+, todenotetheright,andleftlimitsofa function.Noticethatinorderfortheabovetomakesense,werestrictourattention to k 1case,i.e.piecewiselinearpolynomialsandabove. SimilartoHartenandHyman'sentropy[53],todetecttheentropyviolatingcells,we introduce ' h ( x ):=max 0 ; ~ H ' h ( x ) H 1 (( ' h ) x ( x ) ;x ) ;H 1 (( ' h ) x ( x + ) ;x + ) ~ H ' h ( x ) and S ' h ( x ):=max ' h ( x ) ; j ~ H ' h ( x ) j : Wenotethat S ' h ( x ) 6 = j ~ H ' h ( x ) j onlyif j ~ H ' h ( x ) j < ' h ( x ). NowwearereadytoformulateourDGschemefor(2.1).Welookfor ' h ( x;t ) 2 V k h ,such 10 that Z I j ( @ t ' h ( x;t )+ H ( @ x ' h ( x;t ) ;x )) v h ( x ) dx +min ~ H ' h ( x j + 1 2 ) ; 0 [ ' h ] j + 1 2 ( v h ) j + 1 2 +max ~ H ' h ( x j 1 2 ) ; 0 [ ' h ] j 1 2 ( v h ) + j 1 2 C x j S ' h ( x j + 1 2 ) j ~ H ' h ( x j + 1 2 ) j [( ' h ) x ] j + 1 2 ( v h ) j + 1 2 C x j S ' h ( x j 1 2 ) j ~ H ' h ( x j 1 2 ) j [( ' h ) x ] j 1 2 ( v h ) + j 1 2 =0 ; 8 j =1 ;:::;M (2.6) holdsforany v h 2 V k h with k 1.Here[ u ]= u + u denotesthejumpofafunctionat thecellinterface, x j servesasthescalingfactor. C isapositivepenaltyparameter.The detaileddiscussionaboutthechoiceof C iscontainedinSection2.4.Inparticular,we that C =0 : 25workswellinpractice. 2.1.2InterpretationoftheScheme Inthissubsection,weprovideinterpretationofthescheme(2.6)forthelinearHJequation withvariablecot ' t + a ( x ) ' x =0 toillustratethemainideas. Tobetterinterpretourschemeandcompareitwiththeoldmethod,wereviewthe directDGschemein[25].Aswementioned,ChengandShuin[25]usedtheideathat ' t + a ( x ) ' x =0(2.7) 11 with a 0 ( x ) 0,isequivalenttoaconservationlawwithasourceterm: ' t +( a ( x ) ' ) x = a 0 ( x ) ': (2.8) Theauthorsassumed a ( x )issmoothandappliedDGmethodto(2.8)withRoewhich requiresanupwindingtoobtain: Z I j ( @ t ' h ( x;t )+ a ( x ) @ x ' h ( x;t )) v h ( x ) dx + 1 2 a ( x j + 1 2 ) j a ( x j + 1 2 ) j [ ' h ] j + 1 2 ( v ) + j + 1 2 + 1 2 a ( x j 1 2 )+ j a ( x j 1 2 ) j [ ' h ] j 1 2 ( v ) + j 1 2 =0 ;j =1 ;:::;M: (2.9) ThismotivatedthemtoproposethefollowingareschemeforgeneralHJequations: ' h 2 V k h ,suchthat Z I j ( @ t ' h ( x;t )+ H ( @ x ' h ( x;t ) ;x )) v h ( x ) dx + 1 2 0 B @ min x 2 I j + 1 2 H 1 ( @ x ' h ;x j + 1 2 ) j min x 2 I j + 1 2 H 1 ( @ x ' h ;x j + 1 2 ) j 1 C A [ ' h ] j + 1 2 ( v h ) j + 1 2 + 1 2 0 B @ max x 2 I j 1 2 H 1 ( @ x ' h ;x j 1 2 )+ j max x 2 I j 1 2 H 1 ( @ x ' h ;x j 1 2 ) j 1 C A [ ' h ] j 1 2 ( v h ) j 1 2 =0 ;j =1 ;:::;M (2.10) Thereconstructedinformationof @ x ' h onthecells I j + 1 2 and I j 1 2 wasneeded.Therefore, L 2 typeprojectionwasusedtoreconstructacontinuousapproximationof ' h ( x;t )intheir 12 scheme.Theyapolynomial w j + 1 2 2 P 2 k +1 on I j S I j +1 ,s.t. Z I j ' h vdx = Z I j w j + 1 2 vdx and Z I j +1 ' h vdx = Z I j +1 w j + 1 2 vdx then @ x ' h = @ x w j + 1 2 on I j + 1 2 . Theirschemehasprovablestabilityanderrorestimatesforlinearequationsanddemon- stratesgoodconvergencetotheviscositysolutionsfornonlinearequations.However,this schemeonlyworksforequationswithconvexHamiltonians.Moreover,inentropyviolat- ingcells,whereit H 1 ( ' x ( x j 1 2 )) < 0 0 ; and S ' h ( x j + 1 2 ) > 0.When j ~ H ' h ( x j + 1 2 ) j < ' h ( x j + 1 2 ),thepenaltyterm C x j S ' h ( x j + 1 2 ) j ~ H ' h ( x j + 1 2 ) j [( ' h ) x ] j + 1 2 ( v h ) j + 1 2 14 willbenonzero.Ontheotherhand,if a ( x j + 1 2 ) > 0 >a ( x + j + 1 2 ),correspondingtoashock in ' x ,weknowtheRoescheme(2.11)couldcorrectlycapturethisbehavior.Infact,inthis case ' h ( x j + 1 2 )=max 0 @ 0 ; [ a ( x ) ' h ] j + 1 2 [ ' h ] j + 1 2 a ( x j + 1 2 ) ;a ( x + j + 1 2 ) [ a ( x ) ' h ] j + 1 2 [ ' h ] j + 1 2 1 A =0 ; and S ' h ( x j + 1 2 ) j ~ H ' h ( x j + 1 2 ) j =0 ; themethod(2.6)willreduceto(2.11).Similararguments extendtothenonlinearcaseforsonicexpandingcellsforconvexHamiltonians, H 1 ( ' x ( x j + 1 2 )) < 0 > > > > > > > > > < > > > > > > > > > > : H (( ' h ) x ( x + ;y ) ; ( ' h ) y ;x + ;y ) H (( ' h ) x ( x ;y ) ; ( ' h ) y ;x ;y ) ( ' h ) x ( x + ;y ) ( ' h ) x ( x ;y ) ; if( ' h ) x ( x + ;y ) 6 =( ' h ) x ( x ;y ) ; 1 2 H 1 (( ' h ) x ( x + ;y ) ; ( ' h ) y ;x + ;y )+ H 1 (( ' h ) x ( x ;y ) ; ( ' h ) y ;x ;y ) ; if( ' h ) x ( x + ;y )=( ' h ) x ( x ;y ) ; where ( ' h ) y = 1 2 ( ' h ) y ( x + ;y )+( ' h ) y ( x ;y ) istheaverageofthetangentialderivative.Again,we 1 ;' h ( x ;y ):=max 0 ; ~ H 1 ;' h ( x ;y ) H 1 (( ' h ) x ( x ;y ) ; ( ' h ) y ;x ;y ) ; H 1 (( ' h ) x ( x + ;y ) ; ( ' h ) y ;x + ;y ) ~ H 1 ;' h ( x ;y ) and S 1 ;' h ( x ;y ):=max 1 ;' h ( x ;y ) ; j ~ H 1 ;' h ( x ;y ) j : Similarly,for y locatedatthecellinterfaceinthe y direction, ' h 2 V k h isdiscontinuousat 17 ( x;y )forany x ,andwetheRoespeedinthe y directionat( x;y )tobe ~ H 2 ;' h ( x;y ):= 8 > > > > > > > > > > < > > > > > > > > > > : H ( ( ' h ) x ; ( ' h ) y ( x;y + ) ;x;y + ) H ( ( ' h ) x ; ( ' h ) y ( x;y ) ;x;y ) ( ' h ) y ( x;y + ) ( ' h ) y ( x;y ) ; if( ' h ) y ( x;y + ) 6 =( ' h ) y ( x;y ) ; 1 2 H 1 ( ( ' h ) x ; ( ' h ) y ( x;y + ) ;x;y + )+ H 1 ( ( ' h ) x ; ( ' h ) y ( x;y ) ;x;y ) ; if( ' h ) y ( x;y + )=( ' h ) y ( x;y ) ; where ( ' h ) x = 1 2 ( ' h ) x ( x;y + )+( ' h ) x ( x;y ) istheaverageofthetangentialderivative.Again,we 2 ;' h ( x;y ):=max 0 ; ~ H 2 ;' h ( x;y ) H 2 ( ( ' h ) x ; ( ' h ) y ( x;y ) ;x;y ) ; H 2 ( ( ' h ) x ; ( ' h ) y ( x;y + ) ;x;y + ) ~ H 2 ;' h ( x;y ) and S 2 ;' h ( x;y ):=max 2 ;' h ( x;y ) ; j ~ H 2 ;' h ( x;y ) j : 18 Wenowformulateourschemeas: ' h ( x;t ) 2 V k h ,suchthat Z I i;j ( @ t ' h ( x;y;t )+ H ( @ x ' h ( x;y;t ) ;@ y ' h ( x;y;t ) ;x;y )) v h ( x;y ) dxdy + Z K j min ~ H 1 ;' h ( x i + 1 2 ;y ) ; 0 [ ' h ]( x i + 1 2 ;y ) v h ( x i + 1 2 ;y ) dy + Z K j max ~ H 1 ;' h ( x i 1 2 ;y ) ; 0 [ ' h ]( x i 1 2 ;y ) v h ( x + i 1 2 ;y ) dy + Z J i min ~ H 2 ;' h ( x;y j + 1 2 ) ; 0 [ ' h ]( x;y j + 1 2 ) v h ( x;y j + 1 2 ) dx + Z J i max ~ H 2 ;' h ( x;y j 1 2 ) ; 0 [ ' h ]( x;y j 1 2 ) v h ( x;y + j 1 2 ) dx (2.16) C x i Z K j S 1 ;' h ( x i + 1 2 ;y ) j ~ H 1 ;' h ( x i + 1 2 ;y ) j [( ' h ) x ]( x i + 1 2 ;y ) v h ( x i + 1 2 ;y ) dy C x i Z K j S 1 ;' h ( x i 1 2 ;y ) j ~ H 1 ;' h ( x i 1 2 ;y ) j [( ' h ) x ]( x i 1 2 ;y ) v h ( x + i 1 2 ;y ) dy C y j Z J i S 2 ;' h ( x;y j + 1 2 ) j ~ H 2 ;' h ( x;y j + 1 2 ) j [( ' h ) y ]( x;y j + 1 2 ) v h ( x;y j + 1 2 ) dx C y j Z J i S 2 ;' h ( x;y j 1 2 ) j ~ H 2 ;' h ( x;y j 1 2 ) j [( ' h ) y ]( x;y j 1 2 ) v h ( x;y + j 1 2 ) dx =0 holdsforany v h 2 V k h with k 1.Inpractice,thevolumeandlineintegralsin(2.16)can beevaluatedbyGaussquadratureformulas.Themainideain(2.16)isthatinthenormal directionoftheinterface,weapplytheideasfromtheone-dimensionalcase,buttangential totheinterface,weusetheaverageofthetangentialderivativesfromthetwoneighboring cells. 19 2.3SchemeonGeneralUnstructuredMeshes Inthissubsection,wedescribetheschemeongeneralunstructuredmeshesfor(1.1).Let T h = f K g beapartitionofwith K beingsimplices.Wethepiecewisepolynomial space V k h = n v 2 L 2 : v j K 2 P k ( K ) ; 8 K 2T h o ; where P k ( K )denotesthesetofpolynomialsoftotaldegreeatmost k on K with k 1. Foranyelement K ,andedgein @K ,we n K tobetheoutwardunitnormaltothe boundaryof K ,and t K istheunittangentialvectorsuchthat n K t K =0.Inhigher dimensions,i.e. d> 2, d 1tangentialvectorsneedtobeInaddition,forany function u 2 V k h ,and x 2 @K ,wethetracesof u h fromoutsideandinsideofthe element K tobe u h ( x )=lim # 0 u h ( x n k ) ; and[ u h ]( x )= u + h ( x ) u h ( x ), u h ( x )= 1 2 ( u + h ( x )+ u h ( x )).Wealsolet H n K = r r ' H n K . NowfollowingtheCartesiancase,weforany x 2 @K , ~ H n K ;' h ( x ):= 8 > > > > > > > > > < > > > > > > > > > : H (( r x ' h n K ) + ; r x ' h t K ; x + ) H (( r x ' h n K ) ; r x ' h t K ; x ) [ r x ' h n K ]( x ) ; if[ r x ' h n K ]( x ) 6 =0 ; 1 2 H n K (( r x ' h n K ) + ; r x ' h t K ; x + )+ H n K (( r x ' h n K ) ; r x ' h t K ; x ) ; otherwise ; 20 n K ;' h ( x ):=max 0 ; ~ H n K ;' h ( x ) H n K (( r x ' h n K ) ; r x ' h t K ; x ) ; H n K (( r x ' h n K ) + ; r x ' h t K ; x + ) ~ H n K ;' h ( x ) ; and S n K ;' h ( x ):=max n K ;' h ( x ) ; j ~ H n K ;' h ( x ) j : Thenwelookfor ' h 2 V k h ,suchthatforeach K , Z K (( ' h ) t + H ( r x ' h ; x )) v h d x + Z @K min ~ H n K ;' h ( x ) ; 0 [ ' h ]( x ) v h ( x ) ds C K S K Z @K S n K ;' h ( x ) j ~ H n K ;' h ( x ) j [ r x ' h n K ]( x ) v h ( x ) ds =0 foranytestfunction v h 2 V k h with k 1,where K , S K aresizeoftheelement K and edge S K respectively.Inpractice,thevolumeandedgeintegralsneedtobeevaluatedby quadratureruleswithenoughaccuracy.Forexample,weusequadraturerulesthatareexact for(2 k )-thorderpolynomialforthevolumeintegral,andquadraturerulesthatareexactfor (2 k +1)-thorderpolynomialfortheedgeintegrals. 2.4NumericalResults Inthissection,weprovidenumericalresultstodemonstratethehighorderaccuracyand reliabilityofourschemes.Inallnumericalexperiments,weusethethirdorderTVD-RK methodasthetemporaldiscretization[76]. 21 2.4.1One-dimensionalResults Inthissubsection,weprovidecomputationalresultsforone-dimensionalHJequations. Example2.4.1 Wesolvethefollowinglinearproblemwithsmoothvariablecot 8 > > > > > > > > < > > > > > > > > : ' t +sin( x ) ' x =0 ;x 2 [0 ; 2 ˇ ] ' ( x; 0)=sin( x ) ; ' (0 ;t )= ' (2 ˇ;t ) : (2.17) Since a ( x )issmoothinthisexample,thepenaltytermautomaticallyvanishesandthechoice of C doesnothaveanonthesolution.Weprovidethenumericalresultsfor P 1 , P 2 and P 3 polynomialsinTable2.1.TheCFLnumbersusedarealsolistedinthistable.For P 3 polynomials,weset t = O x 4 3 )inordertogetcomparablenumericalerrorsintime asinspace.Fromtheresults,wecouldclearlyobservetheoptimal( k +1)-thorderaccuracy for P k polynomials. Example2.4.2 Wesolvethefollowinglinearproblemwithnonsmoothvariablecot 8 > > > > > > > > < > > > > > > > > : ' t +sign(cos( x )) ' x =0 ;x 2 [0 ; 2 ˇ ] ' ( x; 0)=sin( x ) ; ' (0 ;t )= ' (2 ˇ;t ) : (2.18) Theviscositysolutionofthisexamplehasashockformingin ' x at x = ˇ= 2,anda rarefactionwaveat x =3 ˇ= 2.Weusethisexampletodemonstratetheofthechoiceof C onthenumericalsolution.Thesolutionsobtainedwithtvaluesof C areprovided 22 Table2.1:ErrorsandnumericalordersofaccuracyforExample2.4.1whenusing P k , k = 1 ; 2 ; 3,polynomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells.Finaltime t =1. P 1 CFL =0 : 3 M L 1 errororder L 2 errororder L 1 errororder 401.20E-032.55E-031.52E-02 803.07E-041.966.83E-041.904.32E-031.81 1607.84E-051.971.78E-041.941.14E-031.92 3201.99E-051.984.56E-051.972.94E-041.96 6405.03E-061.991.15E-051.987.43E-051.98 P 2 CFL =0 : 1 404.76E-059.97E-055.23E-04 805.97E-062.991.36E-052.888.77E-052.58 1607.48E-073.001.82E-062.901.35E-052.70 3209.38E-082.992.38E-072.931.96E-062.78 6401.18E-082.993.08E-082.952.72E-072.85 P 3 CFL =0 : 05 402.12E-065.13E-062.89E-05 801.36E-073.973.49E-073.892.16E-063.75 1608.71E-093.972.30E-083.931.57E-073.79 3205.14E-104.091.35E-094.109.47E-094.06 6404.83E-126.759.06E-127.244.52E-117.73 12802.03E-134.582.96E-134.941.42E-125.00 23 inFigure2.1.Ifwetakethepenaltyconstant C =0,thatis,withoutentropycorrection, theentropyconditionisviolatedatthetwocellsneighboring x =3 ˇ= 2,andthenumerical solutionisnotconvergenttowardstheexactsolution.Asweslowlyincreasingthevalueof C ,wecouldobservebetterandbetterconvergenceproperty.Inparticular,once C passes somethreshold,itsonthequalityofthesolutionisminimum,andbiggervaluesof C onlycauseslightlylargernumericalerrors.ThisisalsodemonstratedinTable2.2.Forthis problem,theviscositysolutionisnotsmooth,sowedonotexpectthefull( k +1)-thorder accuracyforthisexample.However,fortvaluesof C rangingfrom0.125to1.0,the numericalerrorslistedinTable2.2areallofsecondorder.Actually,forallofthesimulations performedinthispaper,wethat C =0 : 25tobeagoodchoiceofthepenaltyconstant. Unlessotherwisenoted,fortheremainingofthepaper,wewilluse C =0 : 25. Example2.4.3 One-dimensionalBurgers'equationwithsmoothinitialcondition 8 > > > > > > > > < > > > > > > > > : ' t + 1 2 ' 2 x =0 ;x 2 [0 ; 2 ˇ ] ' ( x; 0)=sin( x ) ; ' (0 ;t )= ' (2 ˇ;t ) : (2.19) At t =0 : 5,thesolutionisstillsmooth,andtheoptimal( k +1)-thaccuracyisobtainedfor P k polynomialswithbothuniformandrandommeshes,seeTables2.3and2.4.At t =1, therewillbeashockin ' x ,andourschemecouldcapturethekinksharplyasshownin Figure2.2. 24 (a) (b) (c) (d) Figure2.1:Example2.4.2.Thenumericalsolutionwithvariousvaluesofpenaltyconstant C :(a) C =0,(b) C =0 : 001,(c) C =0 : 25,and(d) C =1.Here t =1, CFL =0 : 1, P 2 polynomials, M =80.Solidline:theexactsolution;circles:thenumericalsolution. For interpretationofthereferencestocolorinthisandallotheres,thereaderisreferredto theelectronicversionofthisthesis. 25 Table2.2:ErrorsandnumericalordersofaccuracyforExample2.4.2whenusing P 2 polyno- mialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells.Final time t =1. CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder C =1 : 0 401.05E-031.85E-033.49E-03 802.71E-041.954.78E-041.958.73E-042.00 1606.89E-051.981.21E-041.982.18E-042.00 3201.73E-051.993.06E-051.985.46E-052.00 6404.34E-062.007.67E-062.001.37E-052.00 C =0 : 5 409.92E-041.74E-033.28E-03 802.56E-041.954.50E-041.958.22E-042.00 1606.49E-051.981.14E-041.982.06E-042.00 3201.63E-051.992.88E-051.985.14E-052.00 6404.09E-062.007.22E-062.001.29E-052.00 C =0 : 25 408.74E-041.53E-032.87E-03 802.25E-041.963.95E-041.957.19E-042.00 1605.69E-051.981.00E-041.981.80E-042.00 3201.43E-051.992.52E-051.994.50E-052.00 6403.58E-062.006.32E-061.991.13E-052.00 C =0 : 125 406.38E-041.10E-032.05E-03 801.62E-041.972.84E-041.965.14E-042.00 1604.09E-051.987.18E-051.981.29E-042.00 3201.03E-051.991.81E-051.993.23E-052.00 6402.57E-062.004.53E-062.008.57E-061.91 . 26 Table2.3:ErrorsandnumericalordersofaccuracyforExample2.4.3whenusing P 2 poly- nomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells. Penaltyconstant C =0 : 25.Finaltime t =0 : 5. CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder P 1 408.45E-041.23E-035.04E-03 802.02E-042.072.99E-042.041.27E-031.99 1604.93E-052.037.42E-052.013.42E-041.89 3201.22E-052.011.86E-052.009.08E-051.91 6403.04E-062.014.66E-062.002.36E-051.94 P 2 401.27E-052.33E-051.28E-04 801.53E-063.052.93E-062.992.10E-052.61 1601.91E-073.003.73E-072.982.52E-063.06 3202.39E-083.004.74E-082.983.56E-072.82 6403.63E-092.726.23E-092.934.82E-082.88 Table2.4:ErrorsandnumericalordersofaccuracyforExample2.4.3whenusing P 1 and P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationonarandommeshwith40% perturbationof M cells.Penaltyconstant C =0 : 25.Finaltime t =0 : 5. CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder P 1 401.23E-031.91E-031.01E-02 802.70E-042.194.25E-042.172.59E-031.96 1606.70E-052.011.05E-042.016.22E-042.06 3201.62E-052.052.67E-051.972.03E-041.61 6403.97E-062.036.69E-062.006.52E-051.64 P 2 402.27E-054.52E-052.96E-04 802.54E-063.165.84E-062.955.25E-052.50 1603.19E-073.006.87E-073.095.82E-063.17 3204.00E-083.009.34E-082.888.96E-072.70 6405.38E-092.891.16E-083.011.32E-072.77 27 Figure2.2:Example2.4.3.Here t =1 : 5, CFL =0 : 1, P 2 polynomials, M =40.Penalty constant C =0 : 25.Solidline:theexactsolution;circles:thenumericalsolution. Example2.4.4 One-dimensionalBurgers'equationwithanonsmoothinitialcondition 8 > > > > > > > > > > > > < > > > > > > > > > > > > : ' t + ' 2 x 2 =0 ;x 2 [0 ; 2 ˇ ] ' ( x; 0)= 8 > > > < > > > : ˇ x; if0 x ˇ; x ˇ; if0 x 2 ˇ; ' (0 ;t )= ' (2 ˇ;t ) : (2.20) Theexactsolutionshouldhaveararefactionwaveforminginitsderivative,sotheinitial sharpcornerat x = ˇ shouldbesmearedoutatlatertimes.Sincetheentropycondition isviolatedbytheRoetypescheme,theentropyisnecessaryforconvergence.Figure 2.3showsthecomparisonofourschemeswithvariousvaluesofpenaltyconstant C forthis nonlinearproblem.Again,wecouldseethat C =0 : 25isagoodchoiceforthisexample. 28 (a) (b) (c) (d) Figure2.3:Example2.4.4.Thenumericalsolutionwithvariousvaluesofpenaltyconstant C :(a) C =0,(b) C =0 : 001,(c) C =0 : 25,and(d) C =1 : 0.Here t =1, CFL =0 : 1, P 2 polynomials, M =80.Solidline:theexactsolution;circles:thenumericalsolution. 29 Table2.5:ErrorsandnumericalordersofaccuracyforExample2.4.5whenusing P 2 poly- nomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells. Penaltyconstant C =0 : 25.Finaltime t =1. CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder 406.24E-041.09E-032.13E-03 801.69E-041.882.98E-041.875.54E-041.94 1604.35E-051.967.67E-051.961.40E-041.98 3201.10E-051.991.94E-051.993.51E-052.00 6402.75E-062.004.88E-061.998.77E-062.00 Example2.4.5 One-dimensionalEikonalequation 8 > > > > > > > > < > > > > > > > > : ' t + j ' x j =0 ;x 2 [0 ; 2 ˇ ] ' ( x; 0)=sin( x ) ; ' (0 ;t )= ' (2 ˇ;t ) : (2.21) TheexactsolutionisthesameastheexactsolutionofExample2.4.2.Ourschemecould capturetheviscositysolutionofthisnonsmoothHamiltonian.Thenumericalerrorsand ordersofaccuracyusing P 2 polynomialsarelistedinTable2.5.Sincethesolutionisnot smooth,wedonotexpecttheoptimal( k +1)-thorderaccuracyfor P k polynomials. Example2.4.6 One-dimensionalequationwithanonconvexHamiltonian 8 > > > > > > > > < > > > > > > > > : ' t cos( ' x +1)=0 ;x 2 [ 1 ; 1] ' ( x; 0)= cos( ˇx ) ; ' ( 1 ;t )= ' (1 ;t ) : (2.22) ThisexampleinvolvesanonconvexHamiltonianwithsmoothinitialdata.At t =0 : 5 =ˇ 2 , theexactsolutionisstillsmooth,andnumericalresultsarepresentedinTable2.6,demon- 30 Table2.6:ErrorsandnumericalordersofaccuracyforExample2.4.6whenusing P 2 poly- nomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells. Penaltyconstants C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder 401.46E-052.16E-059.89E-05 801.79E-063.022.87E-062.911.59E-052.64 1602.22E-073.013.73E-072.952.39E-062.74 3202.76E-083.014.79E-082.963.39E-072.82 6403.51E-092.986.13E-092.974.53E-082.90 stratingtheoptimalorderofaccuracyofthescheme.Bythetime t =1 : 5 =ˇ 2 ,nonsmooth featureswoulddevelopin ' ,whicharereliablycapturedinFigure2.4. Figure2.4:Example2.4.6.Here t =1 : 5 =ˇ 2 , CFL =0 : 1, P 2 polynomials, M =80.Penalty constant C =0 : 25.Solidline:theexactsolution;circles:thenumericalsolution. Example2.4.7 One-dimensionalRiemannproblemwithanonconvexHamiltonian 8 > > > < > > > : ' t + 1 4 ( ' 2 x 1)( ' 2 x 4)=0 ;x 2 [ 1 ; 1] : ' ( x; 0)= 2 j x j : (2.23) 31 Table2.7:ErrorsandnumericalordersofaccuracyforExample2.4.7whenusing P 2 poly- nomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M cells. CFL =0 : 05.Penaltyconstant C =0 : 25.Finaltime t =1.Aminmodlimiterisused. M L 1 errororder L 2 errororder L 1 errororder EvenM 409.49E-032.21E-025.96E-02 804.64E-031.031.10E-021.003.17E-020.91 1602.28E-031.035.48E-031.001.64E-020.95 3201.12E-031.022.73E-031.018.40E-030.97 6405.60E-041.001.36E-031.004.27E-030.98 OddM 412.81E-036.74E-032.94E-02 811.34E-031.093.35E-031.032.38E-020.31 1616.41E-041.071.61E-031.069.88E-031.28 3213.17E-041.027.99E-041.014.36E-031.19 6411.56E-041.023.96E-041.023.12E-030.49 Forthisproblem,theinitialconditionhasasingularityat x =0.Similarto[62,84],a nonlinearlimiterisneededinordertocapturetheviscositysolution.Weusethestandard minmodlimiter[31].ThisexampleandExample2.4.14aretheonlyexamplesneeding nonlinearlimitinginthispaper. ThenumericalsolutionswithandwithoutthelimiterarelistedinFigure2.5foroddand evenvaluesof M .Thosetbehaviorsareduetothefactthatthesingularpoint x =0 wouldbeexactlylocatedatthecellinterfaceforeven M butnotodd M at t =0.Wenote thatthemethodwithlimitercancorrectlycapturetheviscositysolutionforbothevenand odd M .Thenumericalerrorsandordersofaccuracyusing P 2 polynomialswithlimiters arelistedinTable2.7.Wecouldseethatbothmethodsconverge,whiletheodd M giving slightlysmallererrors.However,similarto[62],themethodisonlyorderaccuratefor thisnonsmoothproblem. 32 (a) (b) (c) (d) Figure2.5:Example2.4.7.Comparisonofthenumericalsolutionwithandwithoutthe limiter:(a) M =80,withoutlimiter;(b) M =80,withlimiter;(c) M =81,withoutlimiter; and(d) M =81,withlimiter.Here t =1, P 2 polynomials, CFL =0 : 05.Penaltyconstant C =0 : 25.Solidline:theexactsolution;circles:thenumericalsolution. 33 2.4.2Two-dimensionalResults Inthissubsection,weprovidecomputationalresultsfortwo-dimensionalHJequationson bothCartesianandunstructuredmeshes. Example2.4.8 Two-dimensionallinearproblemwithsmoothvariablecots ' t y' x + x' y =0 : (2.24) Thecomputationaldomainis[ 1 ; 1] 2 .Theinitialconditionisgivenby ' 0 ( x;y )= 8 > > > > > < > > > > > : 0 ; 0 : 3 r; 0 : 3 r; 0 : 1 > < > > : ' t + ( ' x + ' y +1) 2 2 =0 ; ' ( x;y; 0)= cos ˇ ( x + y ) 2 ; (2.28) withperiodicboundaryconditiononthedomain[ 2 ; 2] 2 . Inthisexample,wetesttheperformanceofourmethodonunstructuredmeshes.A samplemeshusedwithcharacteristiclength h =1 = 4isgiveninFigure2.7.At t =0 : 5 =ˇ 2 , thesolutionisstillsmooth.Numericalerrorsandorderofaccuracyusing P 2 polynomials arelistedinTable2.10,demonstratingtheoptimalorderofaccuracy.At t =1 : 5 =ˇ 2 ,the solutionisnolongersmooth.Ourschemecouldcapturetheviscositysolutionasshownin Figure2.8. 36 Figure2.7:Examples2.4.10and2.4.13.Theunstructuredmeshusedwithcharacteristic length h =1 = 4. Table2.10:ErrorsandnumericalordersofaccuracyforExample2.4.10whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationontriangularmesheswith characteristiclength h .Penaltyconstant C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1. hL 1 errororder L 2 errororder L 1 errororder 11.36E-022.31E-022.22E-01 1/21.77E-032.933.23E-032.845.14E-022.11 1/42.25E-042.984.50E-042.848.95E-032.52 1/82.74E-053.045.82E-052.951.30E-032.78 1/163.40E-063.017.53E-062.951.84E-042.83 37 (a) (b) Figure2.8:Example2.4.10.Here CFL =0 : 1, P 2 polynomials.Triangularmeshwith characteristiclength1 = 8.2816elements.Penaltyconstant C =0 : 25.(a) t =0 : 5 =ˇ 2 ;(b) t =1 : 5 =ˇ 2 . Table2.11:ErrorsandnumericalordersofaccuracyforExample2.4.11whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationonauniformmeshof M M cells.Penaltyconstant C =0 : 25.Finaltime t =0 : 8. CFL =0 : 1. M L 1 errororder L 2 errororder L 1 errororder 102.22E-033.95E-034.78E-02 202.75E-042.984.50E-042.987.79E-032.62 403.70E-052.897.33E-052.771.50E-032.38 804.80E-062.959.83E-062.902.40E-042.64 . Example2.4.11 Two-dimensionalnonlinearequationfrom[62] 8 > < > : ' t + ' x ' y =0 ; ' ( x;y; 0)=sin( x )+cos( y ) ; (2.29) withperiodicboundaryconditiononthedomain[ ˇ;ˇ ] 2 . At t =0 : 8,thesolutionisstillsmooth,asshownintheleftofFigure2.9.Numerical errorsandorderofaccuracyusing P 2 polynomialsarelistedinTable2.11,demonstrating theoptimalorderofaccuracy.At t =1 : 5,singularfeatureswouldforminthesolution,as shownintherightofFigure2.9. 38 (a) (b) Figure2.9:Example2.4.11.Here CFL =0 : 1, P 2 polynomialsona80 80uniformmesh. Penaltyconstant: C =0 : 25.(a) t =0 : 8;(b) t =1 : 5. Example2.4.12 Anexamplerelatedtocontrollingoptimalcostdeterminationfrom[68] 8 > < > : ' t +sin( y ) ' x +(sin( x )+sign( ' y )) ' y 1 2 sin 2 ( y )+cos( x ) 1=0 ; ' ( x;y; 0)=0 ; (2.30) withperiodicboundaryconditiononthedomain[ ˇ;ˇ ] 2 . TheHamiltonianisnotsmoothinthisexample.Ourschemecancapturethefeatures oftheviscositysolutionwell.Thenumericalsolution(left)andtheoptimalcontrolterm sign( ' y )(right)at t =1areshowninFigure2.10. Example2.4.13 Two-dimensionalequationwithanonconvexHamiltonian 8 > < > : ' t cos( ' x + ' y +1)=0 ; ' ( x;y; 0)= cos( ˇ 2 ( x + y )) ; (2.31) withperiodicboundaryconditiononthedomain[ 2 ; 2] 2 . WeusethesameunstructuredmeshasinExample2.4.10,seeforexampleFigure2.7. 39 (a) (b) Figure2.10:Example2.4.12.Here t =1, CFL =0 : 1, P 2 polynomialsona40 40uniform mesh.Penaltyconstant: C =0 : 25.(a)thenumericalsolution;(b)sign( ' y ). At t =0 : 5 =ˇ 2 ,thesolutionisstillsmooth,seeTable2.12fornumericalerrorsandorder ofaccuracyusing P 2 polynomials.At t =1 : 5 =ˇ 2 ,singularfeatureswoulddevelopinthe solution,asshowninFigure2.11. Table2.12:ErrorsandnumericalordersofaccuracyforExample2.4.13whenusing P 2 polynomialsandthirdorderRunge-Kuttatimediscretizationontriangularmesheswith characteristiclength h .Penaltyconstant C =0 : 25.Finaltime t =0 : 5 =ˇ 2 . CFL =0 : 1. hL 2 errororder L 2 errororder L 1 errororder 11.05E-021.65E-021.48E-01 1/21.59E-032.712.49E-032.733.11E-022.25 1/42.42E-042.714.02E-042.636.35E-032.29 1/83.28E-052.895.84E-052.781.03E-032.62 1/163.96E-063.057.45E-062.971.72E-042.58 Example2.4.14 Two-dimensionalRiemannproblem 8 > < > : ' t +sin( ' x + ' y )=0 ; ' ( x;y; 0)= ˇ ( j y jj x j ) ; (2.32) onthedomain[ 1 ; 1] 2 . 40 (a) (b) Figure2.11:Example2.4.13.Here CFL =0 : 1, P 2 polynomials.Triangularmeshwith characteristiclength1 = 8.2816elements.Penaltyconstant: C =0 : 25.(a) t =0 : 5 =ˇ 2 .(b) t =1 : 5 =ˇ 2 . Similarto[56,84],anonlinearlimiterisneededforconvergenceinthisexample.Weuse themomentlimiter[60]andthenumericalsolutionobtainedby P 2 polynomialat t =1is providedinFigure2.12. Figure2.12:Example2.4.14.Here t =1, CFL =0 : 1, P 2 polynomialsona41 41uniform mesh.Penaltyconstant: C =0 : 25. 41 Example2.4.15 Theproblemofapropagatingsurface 8 > < > : ' t q ' 2 x + ' 2 y +1=0 ; ' ( x;y; 0)=1 1 4 (cos(2 ˇx ) 1) ; (cos(2 ˇy ) 1) (2.33) withperiodicboundaryconditiononthedomain[0 ; 1] 2 .Thisisaspecialcaseoftheexample usedin[67],andisalsothetwo-dimensionalEikonalequationarisingfromgeometricoptics [59].WeuseanunstructuredmeshshowninFigure2.13withtsnearthecenter ofthedomainwherethesolutiondevelopssingularity.Thenumericalsolutionsatt timesaredisplayedinFigure2.14.Noticethatthesolutionat t =0isshifteddownwardby 0.35toshowthedetailofthesolutionsatlatertimes. Figure2.13:Example2.4.15.Theunstructuredmeshusedinthecomputation.Numberof elements:3480. Example2.4.16 Theproblemofapropagatingsurfaceontheunitdisk f ( x;y ): x 2 + y 2 42 Figure2.14:Example2.4.15. CFL =0 : 1. P 2 polynomials.Penaltyconstant: C =0 : 25. Thenumericalsolutionattheindicatedtimes. 43 1 g 8 > < > : ' t q ' 2 x + ' 2 y +1=0 ; ' ( x;y; 0)= sin( ˇ ( x 2 + y 2 ) 2 ) : (2.34) WeuseanunstructuredmeshasdepictedinFigure2.15withtsneartheorigin wheresolutiondevelopssingularity.Thenumericalsolutionsatttimesaredisplayed inFigure2.16.Noticethatthesolutionat t =0isshifteddownwardby0.2toshowthe detailofthesolutionsatlatertimes. Figure2.15:Example2.4.16.Theunstructuredmeshusedinthecomputation.Numberof elements:5890. 44 Figure2.16:Example2.4.16.Here CFL =0 : 1, P 2 polynomials.Penaltyconstant: C =0 : 25. Thenumericalsolutionattheindicatedtimes. 45 Chapter3 SparseGridDGMethodsfor High-DimensionalEllipticEquations Inthischapter,wewilldevelopsparsegridDGmethodstotreathigh-dimensionalPDEs. Asaninitialinourinvestigation,wefocusonellipticproblemsandusethesymmetric IPmethodforthediscretizationofthefollowing d -dimensionalmodelequation, ( K r u )= f in=[0 ; 1] d ; (3.1) withDirichletboundarycondition u = g on @ ; (3.2) where u ( x ): ! R istheunknownfunctionandthematrix-valuedcocientfunction K =( k i;j ) 1 i;j d issymmetricpositiveandboundedbelowandaboveuniformly, i.e.thereexisttwopositiveconstant K 0 ;K 1 ,suchthat 8 x 2 ;K 0 x x Kx x K 1 x x : Asshowninthepreviouschapter,theDGmethodhastwoessentialingredientsinits design:(1)a(weak)formulationofthemethodbasedontheunderlyingPDEs,(2)anunder- 46 lyingapproximationspace.Theappropriatechoiceoftheformulationoftheschemeaswell asapproximationpropertiesofthespacecanguaranteethemethodswithdesirableproperties suchasstabilityandconvergence.OneofthemainadvantagesoftheDGmethodscompared tocontinuouselementmethodsistheirfreedominchoosingtheapproximationspace duetothelackofcontinuityrequirement.Infact,DGmethodsbasedontraditionalpiecewise polynomialspacehavebeenextensivelystudiedforthelastfewdecades,andthemethods arerathermatureforapplicationssuchaselliptic,parabolicandhyperbolicproblems.The- oreticalfoundationsarelaidoutusingtoolsfromelementanalysis.Inrecentyears,the ideaofusingnon-polynomialspaces[85,81],orpolynomialspaceswithspproperties suchaslocallydivergence-freeproperties[29]hasbeenexplored.Theyaremainlydrivenby theneedstomimicparticularpropertiesoftheexactsolution.Anotherinterestingandmore relevantdevelopment,whichwasinspiredbyearlysuccessinthevolumeframework [52],istousemultiresolutionanalysiswithDGmethodsforadaptivity[22,5,57,55,39]and trouble-cellindicator[80]forhyperbolicconservationlaws. Inthischapter,wewilldevelopsparsegridIPDGmethodsforthemodelellipticequation, staringwiththeconstructionandapproximationpropertiesofthesparseelementspace, andthenapplyittoellipticproblemsinconjunctionwithIPmethod,withfocusonerror estimates,implementationandnumericalsimulations.Therestofthischapterisorganized asfollows:inSection3.1,weconstructandanalyzetheDGapproximationspaceonsparse grids.InSection3.2,weformulatetheschemeandperformerroranalysisofthesparsegrid IPmethod.Numericalexamplesinmulti-dimensionsaregiventovalidatetheaccuracyand performanceoftheschemeinSection3.3. Noticethatourmethodisrestrictedtoproblemsonaboxshapeddomain.Formore generaldomains,eitheracoordinatetransformationoramorecomplexsparseelement 47 spacebasedonhierarchicaldecompositionsonunstructuredmesheswillberequired.Wedo notpursuesuchcasesinthisthesisandleavethemtofuturestudy. 3.1DGFiniteElementSpacesonSparseGrids Inthissection,wewillintroducethemainingredientofouralgorithm:theDGelement spaceonsparsegrids.Weproceedinseveralsteps.First,wewillreviewthestandard piecewisepolynomialspacesinonedimension,andintroduceahierarchicaldecomposition withasetoforthonormalbases.Second,wewillconstructthesparseelementspace frommulti-dimensionalmultiwaveletbasesbasedonthe1Dconstruction.Finally,wewill discusssomekeyfeaturesandapproximationpropertiesofthesparseelementspace. Numericaltestsaregiventocompareseveralofsparsediscontinuouselement spaces. 3.1.1HierarchicalDecompositionofPiecewisePolynomialSpaces inOneDimension Inthissubsection,wewillintroducethehierarchicalrepresentationofpiecewisepolynomial spacesinonedimension.Withoutlossofgenerality,considertheinterval=[0 ; 1],we the n thlevelgrid n ,consistingof I j n =(2 n j; 2 n ( j +1)], j =0 ;:::; 2 n 1withuniform cellsize h =2 n : Onthisgrid,weuse jjjj H s n ) todenotethebrokenSobolevnorm,i.e. jj v jj 2 H s n ) = P 2 n 1 j =0 jj v jj 2 H s ( I j n ) ; where jj v jj H s ( I j n ) isthestandardSobolevnormon I j n : Sim- ilarly, jj H s n ) denotesthebrokenSobolevsemi-norm,i.e. j v j 2 H s n ) = P 2 n 1 j =0 j v j 2 H s ( I j n ) : Wecan V k n = f v : v 2 P k ( I j n ) ; 8 j =0 ;:::; 2 n 1 g 48 tobetheusualpiecewisepolynomialsofdegreeatmost k onthisgrid. V k n hasdegreesof freedom2 n ( k +1),andwenoticethattheyhavethenestedstructurefortvaluesof n; V k 0 ˆ V k 1 ˆ V k 2 ˆ V k 3 ˆ Duetothenestedstructure,wecannethemultiwaveletsubspace W k n , n =1 ; 2 ;::: as theorthogonalcomplementof V k n 1 in V k n withrespecttothe L 2 innerproductoni.e. V k n 1 W k n = V k n ;W k n ? V k n 1 : Fornotationalconvenience,wealsodenotethebasespace W k 0 := V k 0 ,whichconsists ofallpolynomialsofuptodegree k on[0 ; 1].Now,wehavefoundahierarchicalrepre- sentationofthestandardpiecewisepolynomialspaceongrid f I j n ;j =0 ;:::; 2 n 1 g as V k N = L 0 n N W k n .Weremarkthatthespace W k n ,for n> 1,representsthelevel detailswhenthemeshbecomesandthisisthekeytothereductionindegreesof freedominhigherdimensions.Thedimensionof W k n is2 n 1 ( k +1)when n 1,and k +1 when n =0. Forimplementationpurpose,weneedtointroducebasisfunctionsforspace W k n .The caseof n =0istrivial.Ittouseastandardpolynomialbasison[0 ; 1].Forexample, byusingthescaledLegendrepolynomials,wecaneasilyobtainasetoforthonormalbases in W k 0 .When n> 1,wewillusetheorthonormalbasesintroducedin[4].Inparticular,the basesfor W k 1 areas h i ( x )=2 1 = 2 f i (2 x 1) ;i =1 ;:::;k +1 49 where f f i ( x ) ;i =1 ;:::;k +1 g arefunctionssupportedon[ 1 ; 1]anddependon k ,withthe followingproperties. 1. Therestrictionof f i totheinterval(0 ; 1)isapolynomialofdegree k . 2. Thefunction f i isextendedto( 1 ; 0)asanevenoroddfunctionaccordingtothe parityof i + k : f i ( x )=( 1) i + k f i ( x ) : 3. Thebaseshavevanishingmoments: Z 1 1 f j ( x ) x i dx =0 i =0 ; 1 ; ;j + k 1 : 4. Thebaseshavetheorthogonalityandnormalityproperties: Z 1 1 f i ( x ) f j ( x ) dx = = ij ;i;j =1 ;:::;k: Functions f i canbecomputedbyarepeatedGram-Schmidtalgorithm.Theparticular formof f i forupto k =4arelistedinTable1in[4].Forcompleteness,weprovidethemin Table3.1. Multiwaveletbasesin[4]retaintheorthonormalpropertiesofwaveletbasesfort hierarchicallevels.Moregenerally,thebasisfor W k n ;n 1areas v j i;n ( x )=2 ( n 1) = 2 h i (2 n 1 x j ) ;i =1 ;:::;k +1 ;j =0 ;:::; 2 n 1 1 : Tomakethenotationsconsistentandcompact,when n =0,thebases v 0 i; 0 ( x ) ;i = 1 ;:::k +1areastherescaledLegendrepolynomialson[0 ; 1]withorthonormal 50 Table3.1:Orthonormal,vanishing-momentfunctions f 1 ; ;f k +1 ,for k =0 ; ; 4,for x 2 (0 ; 1).Thefunctions f i isextendedtotheinterval( 1 ; 1)asanoddorevenfunction basedontherule f i ( x )=( 1) i + k f i ( x )for x 2 ( 1 ; 0),andiszeroelsewhere. k =0 f 1 ( x )= q 1 2 k =1 f 1 ( x )= q 3 2 ( 1+2 x ) f 2 ( x )= q 1 2 ( 2+3 x ) k =2 f 1 ( x )= 1 3 q 1 2 (1 24 x +30 x 2 ) f 2 ( x )= 1 2 q 3 2 (3 16 x +15 x 2 ) f 3 ( x )= 1 3 q 5 2 (4 15 x +12 x 2 ) k =3 f 1 ( x )= q 15 34 (1+4 x 30 x 2 +28 x 3 ) f 2 ( x )= q 1 42 ( 4+105 x 300 x 2 +210 x 3 ) f 3 ( x )= 1 2 q 35 34 ( 5+48 x 105 x 2 +64 x 3 ) f 4 ( x )= 1 2 q 5 42 ( 16+105 x 192 x 2 +105 x 3 ) k =4 f 1 ( x )= q 1 186 (1+30 x +210 x 2 840 x 3 +630 x 4 ) f 2 ( x )= 1 2 q 1 38 ( 5 144 x +1155 x 2 2240 x 3 +1260 x 4 ) f 3 ( x )= q 35 14694 (22 735 x +3504 x 2 5460 x 3 +2700 x 4 ) f 4 ( x )= 1 8 q 21 38 (35 512 x +1890 x 2 2560 x 3 +1155 x 4 ) f 5 ( x )= 1 2 q 7 158 (32 315 x +960 x 2 1155 x 3 +480 x 4 ) 51 property.Insummary,wehave[4,3], Z 1 0 v j i;n ( x ) v j 0 i 0 ;n 0 ( x ) dx = ii 0 nn 0 jj 0 ; where ii 0 ; nn 0 ; jj 0 aretheKroneckerdeltasymbols. Weremarkthatthemultiwaveletbasesunderconsiderationinthissectionareclosely relatedtotheoriginalHaarwavelet[51]andthemultiwaveletbasesconstructedin[4,3], andusedforadaptivecomputationsofDGmethods[22,5,57,55,39]. Theone-dimensionalconstructionofpiecewisepolynomialspaceiscomplete,ascanbe seenfromthefollowingproperty. Property3.1.1(CompletenessoftheOne-dimensionalConstruction[4].) Wede- V k :=lim N !1 V k N = M 0 n W k n whichisactuallytheunionofall V k N ,andobservethat V k = L 2 (0 ; 1) : Bytheorthogonalityofthemultiwaveletbases,thecompletenessoftheone-dimensionalcon- structioncanbeproved. Next,wewilldiscussabouttheprojectionoperatorswhichareessentialinthe elementanalysis.We P k n asthestandard L 2 projectionoperatorfrom L 2 [0 ; 1]to V k n . 52 Fromthere,wecanintroducetheincrementprojector, Q k n := 8 > < > : P k n P k n 1 ; if n 1 P k 0 ; if n =0 ; thenwecanseethat W k n = Q k n L 2 (0 ; 1) : Insummary,wearriveatthefollowingidentitiesforthehierarchicaldecompositionof thepiecewisepolynomialspaceandtheprojectionoperator: V k N = M 0 n N W k n ;P k N = X 0 n N Q k n : Thepropertiesof Q k n naturallyrelieson P k n .Forthe L 2 projection,werecallthefollowing approximationresults. Property3.1.2(ConvergencePropertyoftheProjectionOperator[26]) Forafunc- tion v 2 H p +1 (0 ; 1) ,wehavetheconvergencepropertyofthe L 2 projection P k n asfollows: foranyinteger t with 1 t min f p;k g , jj P k n v v jj H s n ) c k;s;t 2 n ( t +1 s ) jj v jj H t +1 ; (3.3) where c k;s;t isaconstantthatdependson k;s;t ,butnoton n . Fromthisproperty,usingbasicalgebra,wecandeducethatfor n 1, jj Q k n v jj H s n ) ~ c k;s;t 2 n ( t +1 s ) jj v jj H t +1 ; 53 with ~ c k;s;t = c k;s;t (1+2 ( t +1 s ) ) : (3.4) Finally,wewanttoremarkonasubtleissueconcerningthehierarchicaldecomposition andthemultiwaveletspace.Ifweuseaprojectionotherthan P k n ,say P k n isanotherprojec- tionfrom L 2 to V k n : Thentheincrementprojector Q k n 6 = Q k n .Thespace W k n = Q k n L 2 (0 ; 1) istfrom W k n ; andlikewiseforthemultiwaveletbases.However,thehierarchicalstruc- ture V k n 1 W k n = V k n stillholds.Inourdiscussioninthenextsubsection,wewillhighlight theimplicationofthisstatementandshowthatusingrentoftheprojec- torandtheincrementspacewillnottheofthesparsediscontinuous elementspace. 3.1.2SparseDiscontinuousFiniteElementSpacesinMulti-dimensions Inthissubsection,weintroducethesparseelementspaceconstructedfrommulti- dimensionalmultiwaveletbasesbasedontheone-dimensionalbasesinSection3.1.1. Fora d -dimensionalproblem,weconsiderthedomain x =( x 1 ;:::;x d ) 2 =[0 ; 1] d .To facilitatethediscussion,werstintroducesomenotationsonthenormsandoperationsof multi-indicesin N d 0 ,where N 0 denotesthesetofnonnegativeintegers.For =( 1 ;:::; d ) 2 N d 0 ; wethe l 1 and l 1 norms j j 1 := d X j =1 j ; j j 1 :=max 1 j d j ; thecomponent-wisearithmeticoperations :=( 1 1 ;:::; d d ) ;c :=( 1 ;:::; d ) ; 2 :=(2 1 ;:::; 2 d ) ; 54 andtherelationaloperators , j j ; 8 j < , and 6 = : Now,foramulti-index l =( l 1 ;:::;l d ) 2 N d 0 ,whichindicatesthelevelofthemesh inamultivariatesense,weconsiderthestandardrectangulargrid l withmeshsize h l := (2 l 1 ;:::; 2 l d ) : Wethesmallestsizeamongalldimensionstobe h =min f 2 l 1 ;:::; 2 l d g , anelementarycell I j l = f x : x i 2 (2 l i j i ; 2 l i ( j i +1) g ,and V k l = f v : v ( x ) 2 P k ( I j l ) ; 0 j 2 l 1 g ; where P k ( I j l )denotespolynomialsofdegreeupto k ineachdimensiononcell I j l .The space V k l containsthetraditionaltensor-productpiecewisepolynomialsusedintheDG discretizations.Moreover,ifweuseequaltofsize2 N ineachdirection,we denotethespacetobe V k N ,anditconsistsof(2 N ( k +1)) d degreesoffreedom. Thefoundationofsparsegridistousethetensorproductoftheone-dimensionalhier- archicaldecomposition,andonlychoosesenoughbasestoguaranteesuitableapproximation properties.Toillustratethemainideas,weintroduce W k l = W k l 1 ;x 1 W k l 2 ;x 2 W k l d ;x d ; where W k l i ;x i correspondstothespace W k l i inthe i -thdimensionasinthe 55 previoussubsection.Thenumberofdegreesoffreedomassociatedwith W k l is dim ( W k l )= d Y i =1 dim ( W k l i ) : Basedontheone-dimensionalhierarchicaldecomposition,itiseasytosee V k l = V k l 1 ;x 1 V k l 2 ;x 2 V k l d ;x d = M j 1 l 1 ;:::;j d l d W k j ; and V k N = V k N;x 1 V k N;x 2 V k N;x d = M j l j 1 N W k l : Thebasisfunctionsfor W k l canbebyatensorproduct v j i ; l ( x ):= d Y t =1 v j t i t ;l t ( x t ) ;j t =0 ;:::; max(0 ; 2 l t 1 1); i t =1 ;:::;k +1 : Theyformasetoforthonormalbasisduetothepropertyoftheone-dimensionalbases. Now,wearereadytointroducethesparseelementapproximationspace.Inpar- ticular,we ^ V k N := M j l j 1 N W k l : Thisismotivatedbycontinuouselementspaceonsparsegrid[21].Insteadof consideringthestandardpiecewisepolynomialspace V k N ; whichhasexponentialdependence onthedimension d ,weshalluseitssubspace ^ V k N : Thisspacehasgoodapproximationresults (seeSection3.1.3fordetails)withtlyreduceddegreesoffreedom.Weremarkthat thekeyintheconstructionliesinthechoiceofconditionfor l .Herewehavetakenittobe 56 j l j 1 N .Asdemonstratedin[21],otherconditionsarealsopossibletorealizedimension reductionwithaimsonoptimizingvarioustypesofapproximationresults.Wedeferthe numericalstudyforthecomparisonofdtspacestoSection3.1.4. Remark3.1.3 Wementionedintheprevioussubsectionthatthereareentwaysto constructtheincrementspace W k n : However,thechoicewon'tcttheof ^ V k N : Thisisbecause M j l j 1 N W k l = M j l j 1 N V k l = M j l j 1 N W k l ; foranyspace W k l constructedfromonedimensionalincrementspace W k n satisfying V k n 1 W k n = V k n : Thenextlemmawillgiveacountofdimensionsforthespace ^ V k N : Lemma3.1.4 Thedimensionof ^ V k N isgivenby dim ( ^ V k N )= ( k +1) d 8 < : d 1 X m =0 d m 0 @ ( 1) d m +2 N + m d +1 d m 1 X i =0 N i ( 2) d m 1 i 1 A +1 9 = ; : Supposethereisanupperboundonthedimension d d 0 ,thenthereexistconstants c d 0 ;C d 0 dependingonlyon d 0 ,suchthat c d 0 ( k +1) d 2 N N d 1 dim ( ^ V k N ) C d 0 ( k +1) d 2 N N d 1 : Proof :Duetothedistinctivenessofthezero-thlevelinamesh,weneedtodistinguishthe zero-thlevelfromotherlevelsintheproof.Therefore,foreachmulti-index l ,wethe 57 setofthedimensionswithmeshlevel0as l 0 = f i j l i =0 ;i =1 ;:::;d g andthenumberof suchdimensionsas j l j 0 :=#in l 0 : Then dim ( ^ V k N )= dim ( M j l j 1 N W k l ) = d X m =0 dim ( M j l j 0 = m; j l j 1 N W k l ) : Wewilldiscusstwocasesbasedonthevalueof j l j 0 : Case1. 0 j l j 0 = m d 1,i.e.,thereare m dimensionsoflevelzerofromthe d dimensionsofthemulti-index l .Clearly, dim ( M j l j 0 = m; j l j 1 N W k l )= d m dim ( M l t =0 ; 1 t m ; l t > 0 ;t>m j l j 1 N W k l ) : Sincethereare d m dimensionsthathavemeshesoflevelnolessthanone,wealways have j l j 1 d m . e m =(0 ; ; 0 ; 1 ; ; 1)tobeavectorin N d 0 whose m 58 dimensionsare0,andtherest d m dimensionsare1.Then,byLemma3.6in[21], dim ( M l t =0 ; 1 t m ; l t > 0 ;t>m j l j 1 N W k l )=( k +1) d X l t =0 ; 1 t m ; l t > 0 ;t>m j l j 1 N 2 j l e m j 1 =( k +1) d N X i = d m 2 i ( d m ) X l t =0 ; 1 t m ; l t > 0 ;t>m j l j 1 = i 1 =( k +1) d N X i = d m 2 i ( d m ) i 1 ( d m ) 1 =( k +1) d N + m d X i =0 2 i i +( d m ) 1 ( d m ) 1 =( k +1) d 0 @ ( 1) d m +2 N + m d +1 d m 1 X i =0 N i ( 2) d m 1 i 1 A : Case2. j l j 0 = d means l = 0 : Therefore, dim ( M j l j 0 = d; j l j 1 N W k l )= dim ( W k 0 )=( k +1) d : Finally,wecombinebothcases,andarriveat dim ( ^ V k N )= d X m =0 dim ( M j l j 0 = m; j l j 1 N W k l ) =( k +1) d 8 < : d 1 X m =0 d m 0 @ ( 1) d m +2 N + m d +1 d m 1 X i =0 N i ( 2) d m 1 i 1 A +1 9 = ; : 59 Wenoticethat d 1 X m =0 d m 2 N + m d +1 d m 1 X i =0 N i ( 2) d m 1 i d 1 X m =1 d m 2 N + m d +1 C d 0 N d m 1 C d 0 2 N d +1 N d 1 d X m =0 d m 2 m N m = C d 0 2 N N d 1 (1+ 2 N ) d C d 0 2 N N d 1 ; whereweuse C d 0 ;c d 0 todenotegenericconstantsthatdependonlyon d 0 ,noton d;k;N . Theymayhavetvaluesineachoccurrencethroughouttheproof. Similarly, dim ( ^ V k N ) dim ( M j l j 0 =0 ; j l j 1 N W k l )=( k +1) d 0 @ ( 1) d +2 N d +1 d 1 X i =0 N i ( 2) d 1 i 1 A ( k +1) d ( 1+ c d 0 2 N d +1 N d 1 ) c d 0 ( k +1) d 2 N N d 1 : Insummary,thereexistconstants c d 0 ;C d 0 ,suchthat c d 0 ( k +1) d 2 N N d 1 dim ( ^ V k N ) C d 0 ( k +1) d 2 N N d 1 ; andwearedone. Thislemmaimpliesthat,uponmeshret,thedegreesoffreedomforthesparse niteelementspacewillgrowintheorderof h 1 j log 2 ( h ) j d 1 insteadof h d forthetraditional piecewisepolynomialspace.Thistranslatesintoatreductionincomputationalcost when d islarge.However,westillneedtoverifytheapproximationpropertiesofthereduced 60 space,andwewilldiscussitinthenextsubsection. 3.1.3ApproximationResults Givenanyone-dimensionalprojectionoperator P k n anditsincrementoperator Q k n ,wecan naturallyaprojectionfrom H 1 to ^ V k N as, ^ P k N := X j l j 1 N Q k l 1 ;x 1 Q k l d ;x d ; (3.5) where Q k l i ;x i denotestheoperator Q k l i inthe i -thdimension.In[71],continuoussparse elementspaceisusedwithstreamlinemethodtosolvetransport-dominated problem.Theelementspaceconsideredis ^ V c;k N := ^ V k N \ C 0 for k 1 : Theapproximationpropertiesforprojectorin(3.5)in L 2 ;H 1 ;H 2 N )norms areobtainedwhen P k n isaunivariateprojectoronto V k n \ C 0 ([0 ; 1])satisfying(3.3).Because ^ V c;k N isasubsetof ^ V k N ; wecandirectlyusetheresultsin[71]andobtainanestimateofthe projectionerrorfor ^ P k N . Weintroducesomenotationsabouttheseminormofafunction'smixedderivatives.For anyset I = f i 1 ;:::i k gˆf 1 ;:::d g ,we I c tobethecomplementsetof I in f 1 ;:::d g : Fornon-negativeintegers ; andset I ,wedetheseminorm j v j H ;I := X 0 1 X 0 k X 0 1 X 0 d k 0 @ @ 1 @x 1 i 1 @ k @x k i k 1 A 0 B @ @ 1 @x 1 j 1 @ d k @x d k j d k 1 C A v L 2 ; 61 and j v j H t +1 :=max s 2f 0 ; 1 g max 1 k d max j v j H t +1 ;s;I : Werecallthefollowingresultsin[71]abouttheapproximationpropertiesin L 2 H 1 and H 2 N )norm. Theorem3.1.5 Let ^ P k N din (3.5) beconstructedfrom P k n whichisaunivariate projectoronto V k n \ C 0 ([0 ; 1]) satisfying (3.3) ,thenfor k 1 ,any 1 t min f p;k g ,there existconstant c k;t ; 0 ( k;t;N ) ; 1 ( k;t;N ) > 0 ,suchthatforany v 2H p +1 , N 1 , d 2 ,wehave j ^ P k N v v j H s N ) = j ^ P k N v v j H s c k;t d 1+ s= 2 s ( k;t;N ) d 1+ s 2 N ( t +1 s ) j v j H t +1 ; for s =0 ; 1 ( L 2 normand H 1 seminorm),and j ^ P k N v v j H 2 N ) 8 > < > : c k;t d 3 = 2 1 ( k;t;N ) d + d 2 0 ( k;t;N ) d 1 2 N 2 N ( t 1) j v j H t +1 ;k 2 c k;t d 1 = 2 + d 2 0 ( k;t;N ) d 1 2 N j v j H 2 ;k =1 ; where s ( k;t;N )= 8 > < > : ~ c k; 0 ;t ( N +1) e 1 = ( N +1) + c k; 0 ; 0 ;s =0 2~ c k; 0 ;t + c k; 0 ; 0 ;s =1 ; and ~ c k; 0 ;t ;c k; 0 ; 0 aredin (3.3) and (3.4) .Moreover,for s =0 ,if ~ c k; 0 ;t 2 t +1 = (2 t +1 1)+ c k; 0 ; 0 < 1 ; 62 thereexistsapositiveconstant c t;k ,suchthat ( k;t;s;N ) < 1 forall N 1 ;d 2 with N +1 c t;k ( d 1) : Thistheoremimpliesaconvergencerateof O ( h k +1 )uptothepolylogarithmicterm j log 2 h j d 1 inthe L 2 norm,whichiscomparablewiththetraditionalfullgridapproach whenthefunction v retainsenoughsmoothness.Thisestimateservesasthefoundationin theerrorestimatesofIPmethodintheenergynorm.Weremarkthatwhenswitchingthe projectionoperator(say L 2 projectionorotherprojectorsonto ^ V k N )theerrorboundmay change.However,ourestimatesinSection3.2.2doesnotrequireanyparticularproperty fromtheprojection.Therefore,itforustousethistheoremdirectlyfrom[71].In futurework,wewillestablishconvergencepropertyofprojectionsonto ^ V k N ; for k 0.This willbeessentialforerrorestimatesforbroadernsofDGmethodsforothertypesof equations. 3.1.4ApproximationsfromVariousSparseDiscontinuousFinite ElementSpaces:ANumericalInvestigation Inthissubsection,wenumericallyinvestigatetheapproximationpropertiesofseveralsparse elementspaces,including ^ V k N intheprevioussubsections,and ~ V k N := M j l j 1 N + d 1 j l j 1 N W k l ; whichisaslightlylargerspace. ~ V k N containsthesparsecontinuouspiecewiselinearspace in[21]when k 1.Moreover,byasimilarargumentasintheproofofLemma3.1.4,its degreesoffreedomisalsooftheorder h 1 j log 2 ( h ) j d 1 . 63 Theotherspaceweconsiderhereretainsnotonlysparsitywithrespectto h ,butalso withrespecttothedegreeofpolynomials(wecallthisas p -sparsity).Ifweintroduce ^ W k l = M j k j 1 k W k 1 l 1 ;x 1 W k 2 l 2 ;x 2 W k d l d ;x d ; with k =( k 1 ; ;k d ),thenewsparsespacecanbeas ^ ^ V k N := M j l j 1 N ^ W k l : Itisclearthat ^ ^ V k N ˆ ^ V k N ˆ ~ V k N : Acountofdimensionsforthespace ^ ^ V k N isgivenbythefollowinglemma. Lemma3.1.6 Thedimensionof ^ ^ V k N is dim ( ^ ^ V k N )= k + d d 8 < : d 1 X m =0 d m 0 @ ( 1) d m +2 N + m d +1 d m 1 X i =0 N i ( 2) d m 1 i 1 A +1 9 = ; : Supposethereisanupperboundonthedimension d d 0 ,thenthereexistconstants c d 0 ;C d 0 dependingonlyon d 0 ,suchthat c d 0 k + d d 2 N N d 1 dim ( ^ ^ V k N ) C d 0 k + d d 2 N N d 1 : Notethat,when k and d arelarge, dim ( ^ ^ V k N )canbetlysmallerthan dim ( ^ V k N ) and dim ( ~ V k N ). 64 Asfortheimplementationofthespace ^ ^ V k N ; wecannolongerusetheorthogonalhier- archicalbasesinSection3.1.1torepresentfunctionsin ^ ^ V k N ,sincethevanishing-moment functions f i ,whichareusedtoconstructtheorthogonalhierarchicalbases,havethesame degrees,seeTable3.1.Instead,wecanadoptanothersetofnon-orthogonalhierarchical basisfunctionsasfollows.Werstconstructthebasesfor W k n .Again,thecaseof n =0istrivial.Similartotheorthogonalcase,thebasesfor W k 1 areas ^ h i ( x )=2 1 = 2 ^ f i (2 x 1) ;i =1 ; ;k +1 ; where ^ f i ;i =1 ; ;k +1arefunctionssupportedon[ 1 ; 1].Ratherthanchoosing ^ f i from Table3.1,welet ^ f i ( x )= x i 1 ;x 2 ( 1 ; 0) and ^ f i ( x )= x i 1 ;x 2 (0 ; 1) : Thebasesfor W k n ;n 1canbeaccordinglyas ^ v j i;n ( x )=2 ( n 1) = 2 ^ h i (2 n 1 x j ) ;i =1 ;:::;k +1 ;j =0 ;:::; 2 n 1 1 : Therefore,thebasisfunctionsin ^ W k l (and ^ ^ V k N )areas ^ v j i ; l ( x ):= d Y t =1 j i j 1 k v j t i t ;l t ( x t ) ;j t =0 ;:::; max(0 ; 2 l t 1 1) : Thepurposeofourstudyinthissubsectionistoprovideanumericalcomparisonofthe 65 threetypesofsparseapproximationspaces.Inparticular,weconsiderasmoothfunction u ( x )=exp 0 @ d Y i =1 x i 1 A ; x 2 [0 ; 1] d ; where d =2 ; 3andthestandard L 2 projections: ^ P k n , ~ P k n ,and ^ ^ P k n from H 1 to ^ V k N , ~ V k N , and ^ ^ V k N ,respectively.Wemeasurevariousnormsoftheprojectionerrorsandthedegrees offreedomforeachspacetothebestbalancebetweenaccuracyandcy. InTables3.2-3.7,wereporttheprojectionerrors e 1 = ^ P k n u u , e 2 = ~ P k n u u and e 3 = ^ ^ P k n u u in L 1 , L 2 , L 1 ,and H 1 normsandtheassociatedordersofaccuracyfor k =1 ; 2 ; 3.Intheimplementation,theprojectionsareobtainedviatheGaussianquadrature basedonsparsegridstosavecomputationalcost.Whencomputingtheerrornorms,the domainisuniformlydividedinto2 dN cell.Notethatoneachcell,theprojectionfunctions aresmooth,andhenceweadoptthe6 d -pointgaussianquadraturewith12-thorderaccuracy toevaluatetheerrorsin L 1 , L 2 , L 1 ,and H 1 norms. Forallthreespaces,thedegreesoffreedomarealltlylessthan( k +1) d 2 Nd , whichisthedegreeoffreedomforthefullgridapproximation.Forspace ~ V k N ,( k +1)-th orderofaccuracyisclearlyobservedforthe L 1 and L 2 errors,and k -thorderofaccuracyis observedforthe H 1 error,whileslightreductionofaccuracyisobservedforthe L 1 error. Forspace ^ V k N , k -thorderofaccuracyisobservedforthe H 1 errorandslightreduction ofaccuracyisobservedfor L 1 and L 2 errors.However,wedoobserveabouthalf-order reductionofaccuracyforthe L 1 error.Weremarkthat,ononehand,themagnitudeof errorscomputedbyspace ^ V k N islargerthanthatbyspace ~ V k N fora N .Theapparent reasonisthatthedegreesoffreedomof ^ V k N issmallerthan ~ V k N .Ontheotherhand,whenthe degreesoffreedomarecomparableforthetwospaces,themagnitudeoferrorscomputedby 66 space ^ V k N issmallerthan ~ V k N .Therefore, ^ V k N ispreferredifthecomputationaleis concerned.For ^ ^ V k N ,whichhastheleastdegreesoffreedomamongthethreesparsespaces, severereductionofaccuracyisobservedforallerrornorms.Moreover,themagnitudeof errorsistlylargerthanthatbyspace ^ V k N or ~ V k N withcomparabledegreesof freedom. Insummary,basedonthediscussion,wewilladoptspace ^ V k N inthecomputationfor ellipticequationsinthenextsection.Afurtherreductionincomputationalcostispossible bytheoptimalsubsetof ^ V k N byadaptivealgorithms.Wedonotpursuethisdirection inthisthesis,butleaveittofuturestudy. 67 Table3.2: L 2 projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesof freedomofthefullgridapproximationspace. d =2. k =1. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 248322464 31928060256 43201921441024 57684483364096 61792102476816384 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 21.58E-032.41E-032.16E-027.45E-02 34.05E-041.976.14E-041.976.62E-031.713.73E-021.00 41.03E-041.971.56E-041.981.98E-031.741.86E-021.00 52.62E-051.983.96E-051.985.81E-041.779.32E-031.00 66.64E-061.981.00E-051.981.68E-041.794.66E-031.00 ^ V k N 22.28E-033.16E-033.21E-028.10E-02 36.30E-041.868.98E-041.821.17E-021.464.09E-020.99 41.72E-041.872.50E-041.854.01E-031.542.05E-021.00 54.68E-051.886.82E-051.871.31E-031.611.03E-021.00 61.26E-051.901.84E-051.894.13E-041.675.13E-031.00 ^ ^ V k N 21.95E-022.59E-021.94E-013.60E-01 38.47E-031.211.14E-021.181.07E-010.862.72E-010.40 43.77E-031.175.13E-031.165.69E-020.912.18E-010.32 51.72E-031.132.34E-031.132.94E-020.951.81E-010.27 67.94E-041.111.08E-031.111.49E-020.981.55E-010.23 68 Table3.3:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesoffreedom ofthefullgridapproximationspace. d =2. k =2. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 21087248144 3432180120576 47204322882304 5172810086729216 640322304153636864 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 22.82E-054.36E-054.05E-042.26E-03 33.50E-063.015.47E-062.995.94E-052.775.66E-042.00 44.39E-073.006.86E-072.998.54E-062.801.42E-042.00 55.51E-083.008.61E-083.001.21E-062.813.54E-052.00 66.90E-093.001.08E-083.001.71E-072.838.84E-062.00 ^ V k N 23.51E-055.23E-056.48E-042.41E-03 34.84E-062.867.26E-062.851.23E-042.406.08E-041.99 46.56E-072.889.96E-072.872.21E-052.471.53E-041.99 58.81E-082.901.35E-072.883.77E-062.553.82E-052.00 61.17E-082.911.81E-082.906.13E-072.629.55E-062.00 ^ ^ V k N 21.73E-032.51E-032.78E-025.62E-02 34.86E-041.837.22E-041.801.09E-021.352.80E-021.01 41.35E-041.852.02E-041.843.99E-031.461.39E-021.01 53.68E-051.885.53E-051.871.37E-031.556.95E-031.00 69.90E-061.891.49E-051.894.45E-041.623.47E-031.00 69 Table3.4:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesoffreedom ofthefullgridapproximationspace. d =2. k =3. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 219212880256 37683202001024 412807684804096 530721792112016384 671684096256065536 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 23.72E-076.12E-074.67E-064.66E-05 32.32E-084.003.84E-084.003.32E-073.825.83E-063.00 41.45E-094.002.40E-094.002.31E-083.857.29E-073.00 59.09E-114.001.50E-104.001.59E-093.869.11E-083.00 65.68E-124.009.39E-124.001.09E-103.861.14E-083.00 ^ V k N 24.37E-076.77E-077.54E-064.82E-05 32.90E-083.914.55E-083.907.47E-073.346.07E-062.99 41.92E-093.923.05E-093.907.08E-083.407.61E-073.00 51.26E-103.932.03E-103.916.33E-093.489.52E-083.00 68.28E-123.931.35E-113.925.35E-103.571.19E-083.00 ^ ^ V k N 21.95E-042.88E-043.57E-038.44E-03 34.20E-052.226.36E-052.181.10E-031.703.16E-031.42 49.26E-062.181.42E-052.173.19E-041.791.23E-031.35 52.09E-062.143.19E-062.158.77E-051.865.03E-041.29 64.81E-072.127.31E-072.132.32E-051.922.12E-041.24 70 Table3.5:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesoffreedom ofthefullgridapproximationspace. d =3. k =1. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 235210452512 312163041524096 4358483241632768 5972821761088262144 625088550427522097152 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 26.23E-041.20E-032.98E-023.76E-02 31.57E-041.993.02E-041.999.30E-031.681.87E-021.01 43.95E-051.997.60E-051.992.91E-031.679.34E-031.00 59.99E-061.981.91E-051.999.20E-041.664.67E-031.00 62.52E-061.984.82E-061.992.91E-041.662.33E-031.00 ^ V k N 21.18E-031.91E-036.13E-024.41E-02 33.65E-041.695.91E-041.692.71E-021.182.24E-020.98 41.09E-041.741.79E-041.721.13E-021.261.13E-020.99 53.21E-051.765.34E-051.754.45E-031.345.67E-031.00 69.28E-061.791.56E-051.771.68E-031.402.84E-031.00 ^ ^ V k N 22.16E-023.01E-023.76E-013.22E-01 31.10E-020.971.56E-020.952.80E-010.432.53E-010.35 45.61E-030.987.99E-030.961.94E-010.532.07E-010.30 52.83E-030.994.07E-030.971.27E-010.611.74E-010.25 61.42E-030.992.06E-030.987.97E-020.671.49E-010.22 71 Table3.6:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesoffreedom ofthefullgridapproximationspace. d =3. k =2. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 211883511301728 34104102638013824 41209628081040110592 53283273442720884736 6846721857668807077888 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 28.65E-061.88E-055.64E-049.83E-04 31.08E-063.002.36E-063.008.11E-052.802.45E-042.00 41.35E-073.002.95E-073.001.15E-052.826.12E-052.00 51.69E-083.003.69E-083.001.65E-062.801.53E-052.00 62.12E-093.004.62E-093.002.40E-072.783.83E-062.00 ^ V k N 21.41E-052.58E-051.33E-031.10E-03 32.12E-062.733.86E-062.743.16E-042.082.80E-041.98 43.15E-072.755.76E-072.747.07E-052.167.07E-051.99 54.62E-082.778.56E-082.751.50E-052.241.77E-051.99 66.66E-092.791.26E-082.763.01E-062.314.44E-062.00 ^ ^ V k N 24.50E-036.59E-031.13E-019.32E-02 31.82E-031.302.71E-031.287.36E-020.625.93E-020.65 47.51E-041.281.11E-031.294.30E-020.783.91E-020.60 53.10E-041.284.53E-041.292.32E-020.892.70E-020.54 61.30E-041.251.88E-041.261.18E-020.971.95E-020.47 72 Table3.7:Projectionerrorsandordersofaccuracy.FGDOFdenotesthedegreesoffreedom ofthefullgridapproximationspace. d =3. k =3. Ndim ~ V k N dim ^ V k N dim ^ ^ V k N FGDOF 228168322604096 39728243276032768 42867266562080262144 5778241740854402097152 6200704440321376016777216 N L 1 errororder L 2 errororder L 1 errororder H 1 errororder ~ V k N 29.39E-082.37E-076.61E-061.80E-085 35.96E-093.981.49E-083.995.33E-073.632.25E-063.00 43.66E-104.039.27E-104.013.13E-084.092.81E-073.00 52.30E-113.995.81E-114.002.47E-093.663.52E-083.00 62.09E-123.465.26E-123.466.07E-102.034.41E-092.99 ^ V k N 21.32E-072.82E-071.55E-051.92E-05 39.66E-093.782.01E-083.812.01E-062.952.43E-062.98 46.94E-103.801.44E-093.802.35E-073.103.05E-072.99 54.99E-113.801.04E-103.782.66E-083.153.83E-083.00 63.92E-123.678.49E-123.623.13E-093.084.80E-092.99 ^ ^ V k N 27.49E-041.18E-032.52E-022.24E-02 32.38E-041.653.86E-041.611.48E-020.771.11E-021.02 47.31E-051.701.22E-041.677.48E-030.985.46E-031.02 52.18E-051.753.71E-051.713.41E-031.132.69E-031.02 66.35E-061.781.10E-051.751.43E-031.251.76E-030.62 73 3.2IPMethodonSparseGridsforEllipticEquations Inthissection,wesolvethesecondorderlinearellipticboundaryvalueproblems(3.1)byIP methodswiththesparseelementspace ^ V k N : Wewillformulatetheschemeand discussitsimplementationissues,andthenperformerroranalysisintheenergynorm. 3.2.1FormulationoftheScheme First,wewillintroducesomebasicnotationsaboutjumpsandaveragesforpiecewisefunc- tionsonagrid N .Let:= S T 2 N @ T betheunionoftheboundariesforallthe elementsin N and S := T 2 N L 2 ( @T )bethesetof L 2 functionsonFor any q 2 S and q 2 [ S d ,wetheiraverages f q g ; f q g andjumps[ q ] ; [ q ]onthe interioredgesasfollows.Suppose e isaninterioredgesharedbyelements T + and T ,we theunitnormalvectors n + and n on e pointingexteriorto T + and T ,then [ q ]= q n + q + n + ; f q g = 1 2 ( q + q + ) ; [ q ]= q n + q + n + ; f q g = 1 2 ( q + q + ) : If e isaboundaryedge,thenwelet [ q ]= q n ; f q g = q ; where n istheoutwardunitnormal. NowwearereadytoformulatetheIPDGschemefor(3.1).Welookfor u h 2 ^ V k N ,such that B ( u h ;v )= L ( v ) ; 8 v 2 ^ V k N (3.6) 74 where B ( w;v )= Z K r w r vd x X e 2 Z e f K r w g [ v ] ds X e 2 Z e f K r v g [ w ] ds + X e 2 ˙ h Z e [ w ] [ v ] ds; (3.7) and L ( v )= Z fvd x Z @ K r v n + ˙ h v gds; (3.8) where ˙ isapositivepenaltyparameter, h =2 N istheuniformmeshsizeineachdimension. TheIPmethodsdevelopedin[82,6]arecommonlyusedtosolveellipticproblems,butusually withstandardpiecewisepolynomialspace.Here,byusingthesparseelementspace,we canachieveatreductioninthesizeofthelinearalgebraicsystem(3.6)especially whenthedimensionislarge. Wenoticethattherearestillseveralimportantfactorsinensuringrealcomputational gainsinimplementation.Firstofall,it'sobviousthatweneedtalgorithmstoevaluate L ( v )when v istakentobethebasisfunctions v j i ; l ( x )in ^ V k N : Astandardintegrationscheme willincurcomputationalcomplexitywithexponentialdependenceon dN .Toavoidthis,in ouralgorithm,wetakefulladvantageofnumericalintegrationonsparsegridsdevelopedin theliterature[77,40].Inparticular,foreachbasis v j i ; l ( x ),itsdomainofdependenceconsists of2 d smoothpatches.Therefore,whenevaluating R fv j i ; l d x ,wedividethisintegral into2 d partsaccordingly,andthenforeachpatch,weimplementasparsegridintegration withGaussquadrature,andthenumberoflevelsemployedinthiscalculationistakenas ( I quad j l j 1 = 2),where I quad isadintegerchosenlargeenoughtoguaranteet 75 accuracy.Theevaluationof R @ K r v n + ˙ h v gds canbeperformedinasimilarfashion. Anotherimportantfactorwhenweassemblethelinearsystemistheso-called unidirec- tionalprinciple [19].Todemonstratethemainideas,wecanseethatevaluating R ˚ ( x ) d x with ˚ ( x )= ˚ 1 ( x 1 ) :::˚ d ( x d )isequivalenttomultiplicationofone-dimensionalintegrals R [0 ; 1] ˚ 1 dx 1 R [0 ; 1] ˚ d dx d : Therefore,computing R fv j i ; l d x when f ( x )isseparable,i.e. f ( x )= f 1 ( x 1 ) :::f d ( x d )orwhen f ( x )isasumofseperablefunctionsisstraightforward, becauseweonlyneedsomesmalloverheadtocompute1Dintegralsandassemblethemto obtainthemulti-dimensionalintegrations. Thesamediscussionholdstrueforthecomputationofthebilinearterm B ( u h ;v ) : For example,ifweuseadirectmethod,weneedtoevaluate B ( w;v )for( w;v )beingallpossible basisfunctionsin ^ V k N : Fromthenitionof B ( w;v ),eachmatrixelementwillinvolve fourmulti-dimensionalintegrations.If K isseparable(inparticular,when K isaconstant function),duetotheunidirectionalprinciple,thematricescanbeassembledfast.When K isageneralfunction,weneedtocomputetruehighdimensionalintegrals.Thisyis idenasoneofthemainchallengingtasksforcomputingPDEsonsparsegrids,seee.g. [20,2].Inthiscase,wecaneitherusethesparsegridintegrationprocedurementionedabove orbyacomputationalprocedureoutlinedasfollows.Assume K tobeasmoothfunction, thenwecan K h = ^ P 2 k N K asthe L 2 projectionof K ontothesparseelement space ^ V 2 k N ; anduse K h inplaceof K inthescheme.Noticethat K h isasumofseparable functions,thereforethecomputationofthebilineartermisacceleratedastheunidirectional case.Thereasonweuseahigherordersparseelementforprojectionof K h istoobtain exactevaluationofthevolumeintegral R K r u r vd x .However,thisprocessdoeschange thevaluesofthreeothertermsuptoapproximationerrorof K h K : Anotherthingwedid notexploreisthetsolverforthelinearalgebraicsystem.Intheliterature,iterative 76 methodshavebeenproposedbasedonthesemi-coarseningapproachanditssparsegrid extensions[64,65,43,48,47,69,18].Weleavethoseinterestingimplementationaspectsto futurestudy. 3.2.2ErrorAnalysis ThissectioncontainserrorestimatesoftheIPDGmethodonsparsegrids.Following[6],we theenergynormofafunction v 2 H 2 N )by jjj v jjj 2 := X T 2 N Z T jr v j 2 d x + X e 2 h Z e ˆ @v @ n ˙ 2 ds + X e 2 1 h Z e [ v ] 2 ds: Wereviewsomebasicpropertiesofthebilinearoperator B ( ; ) : Lemma3.2.1(Orthogonality) Let u betheexactsolutionto (3.1) ,and u h bethenumer- icalsolutionto (3.6) ,then B ( u u h ;v )=0 ; 8 v 2 ^ V k N : Proof :Usingintegrationbyparts,wecaneasilyshow B ( u;v )=0 ; 8 v 2 ^ V k N : TheGalerkin orthogonalityimmediatelyfollows. Lemma3.2.2(Boundedness[6,7]) Thereexistsapositiveconstant C b ,dependingonly on K 1 ;˙ ,suchthat B ( w;v ) C b jjj w jjjjjj v jjj ; 8 w;v 2 H 2 N ) : 77 Lemma3.2.3(Stability[6,7]) When ˙ istakenlargeenough,thereexistsapositivecon- stant C s dependingonlyon K 0 ,suchthat B ( v;v ) C s jjj v jjj 2 ; 8 v 2 ^ V k N : Theorem3.2.4 Let u betheexactsolutionto (3.1) ,and u h bethenumericalsolutionto (3.6) .For k 1 , u 2H p +1 , 1 t min f p;k g , N 1 , d 2 ,wehave jjj u u h jjj 1+ C b C s p C d c k;t C 2 Nt j u j H t +1 : where C d isaconstantthatdependson d linearly. C b ;C s aredinLemmas3.2.2and 3.2.3. C =max q d 2 2 d 2 0 +3 d 3 2 d 1 +2 d 4 2 d 2 0 2 2 N ; q d 2 2 d 2 0 + d 3 2 d 1 +2 d +2 d 4 2 d 2 0 2 2 N ; where s = s ( k;t;N ) ;s =0 ; 1 and c k;t aredinTheorem3.1.5. Proof :Chooseanyfunction u I 2 ^ V k N ,thenwedecomposetheerrorinto e = u u h = ( u u I )+( u I u h ).ByCea'slemma,usingLemma3.2.1,3.2.2and3.2.3, C s jjj u I u h jjj 2 B h ( u I u h ;u I u h )= B h ( u I u;u I u h ) C b jjj u u I jjjjjj u I u h jjj : Therefore, jjj u I u h jj C b C s jjj u u I jjj ; and jjj e jjjjjj u I u h jjj + jjj u u I jjj 1+ C b C s jjj u u I jjj : 78 Wehave jjj e jjj 1+ C b C s inf u I 2 ^ V k N jjj u u I jjj 1+ C b C s jjj u ^ P k N u jjj ; wheretheprojectionoperator ^ P k N hasbeenspinTheorem3.1.5. Next,weneedtoboundtheenergynormof := u ^ P k N u .Recallthat jjj jjj 2 = X T 2 N Z T jr j 2 d x + X e 2 h Z e ˆ @ @ n ˙ 2 ds + X e 2 1 h Z e [ ] 2 ds: Theterminthesummationis X T 2 N Z T jr j 2 d x = j j 2 H 1 N ) : Toboundthesecondandthirdterms,weusethetraceinequalities[6]: jj ˚ jj 2 L 2 ( @T ) C d 1 h jj ˚ jj 2 L 2 ( T ) + h j ˚ j 2 H 1 ( T ) ; 8 ˚ 2 H 1 ( T ) @˚ @ n 2 L 2 ( @T ) C d 1 h j ˚ j 2 H 1 ( T ) + h j ˚ j 2 H 2 ( T ) ; 8 ˚ 2 H 2 ( T ) where C d isagenericconstantthatdependson d linearly.Itmayhaverentvaluesin eachoccurrenceintheproof.Sumoveralltheelements,weget X e 2 h Z e ˆ @ @ n ˙ 2 ds C d j j 2 H 1 N ) + h 2 j j 2 H 2 N ) X e 2 1 h Z e [ ] 2 ds C d 1 h 2 jj jj 2 L 2 N ) + j j 2 H 1 N ) : 79 Insummary, jjj jjj 2 C d 1 h 2 jj jj 2 L 2 N ) + j j 2 H 1 N ) + h 2 j j 2 H 2 N ) : ByTheorem3.1.5, jjj jjj 2 C d c 2 k;t d 2 2 d 2 0 +3 d 3 2 d 1 +2 d 4 2 d 2 0 2 2 N 2 2 Nt j u j 2 H t +1 ;k 2 jjj jjj 2 C d c 2 k;t d 2 2 d 2 0 + d 3 2 d 1 +2 d +2 d 4 2 d 2 0 2 2 N 2 2 Nt j u j 2 H t +1 ;k =1 wherewehaveusedtheshorthandnotation s = s ( k;t;N ) ;s =0 ; 1 : Let's C =max q d 2 2 d 2 0 +3 d 3 2 d 1 +2 d 4 2 d 2 0 2 2 N ; q d 2 2 d 2 0 + d 3 2 d 1 +2 d +2 d 4 2 d 2 0 2 2 N : Then, jjj jjj p C d c k;t C 2 Nt j u j H t +1 : Therefore,wehaveprovedtheerrorestimateintheenergynorm jjj e jjj 1+ C b C s p C d c k;t C 2 Nt j u j H t +1 : Thistheoremimpliesaconvergencerateof O ( h k )uptothepolylogarithmicterm j log 2 h j d 1 intheenergynormwhen u issmoothenough.However,wedorequiremoreregularityof u comparedwithIPmethodsusingtraditionalpiecewisepolynomialspace. 80 Remark3.2.5 Provingconvergencein L 2 normwiththestandarddualityargumentwill encountersomesinthisframework.Forexample,let ' bethesolutiontothe adjointproblem ( K r ' )= u u h on ;' =0 on @ : Since isconvex,wehave ' 2 H 2 ,and jj ' jj H 2 C jj u u h jj L 2 : Fromtheadjoint consistencyoftheIPmethod,weget jj u u h jj 2 L 2 = B ( u u h ;' ) : However,toproceedfromhere,wewillneedtoaninterpolantof ' : ' I 2 ^ V 1 N ,and bound jjj ' ' I jjj .Fromourpreviousdiscussion,thiswillrequireaboundin jj ' jj H 2 : This isastrongernormthantheclassical H 2 norm,andcannotbeboundedby jj u u h jj 2 L 2 . 3.3NumericalResults Inthissection,weprovidemulti-dimensionalnumericalresultstodemonstratetheperfor- manceofoursparsegridIPDGscheme. 3.3.1Two-dimensionalResults Inthissubsection,wegathercomputationalresultsfortwo-dimensionalcases.Thepenalty constantinthissubsectionischosentobe ˙ =10for k =1 ; and ˙ =20for k =2. Example3.3.1 Wesolvethefollowingtwo-dimensionalproblemwithconstantcot 81 Table3.8:NumericalerrorsandordersofaccuracyforExample3.3.1computedbyspace ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 34.49E-036.97E-033.26E-021.77E-01 41.18E-031.931.93E-031.859.71E-031.758.80E-021.01 53.03E-041.965.09E-041.923.19E-031.604.36E-021.01 67.68E-051.981.32E-041.989.68E-041.722.16E-021.01 k =2 39.52E-051.33E-045.74E-047.61E-03 41.42E-052.752.03E-052.719.65E-052.571.91E-031.99 52.05E-062.793.02E-062.751.59E-052.604.78E-042.00 62.89E-072.834.36E-072.792.66E-062.581.19E-042.00 on=[0 ; 1] 2 . 8 > > > < > > > : u =0 ; x 2 ; u =sin( ˇx 1 ) sinh( ˇx 2 ) sinh( ˇ ) ; x 2 @ ; (3.9) wheretheexactsolutionis u =sin( ˇx 1 ) sinh( ˇx 2 ) sinh( ˇ ) .Wetestschemewith k =1and k =2on tlevelsofmeshes.Numericalerrorsandordersofaccuracymeasuredin L 1 ;L 2 ;L 1 and H 1 normsarelistedinTable3.8.Weobserve k -thorderofaccuracyfor H 1 norm,close to( k +1)-thorderaccuracyfor L 1 ;L 2 normsandslightlylessthan( k +1)-thorderaccuracy forthe L 1 norm.Theresultsagreewiththeerrorestimatesperformedintheprevious section. Inaddition,weprovidethesparsitypatternsofthematricesfor k =1and k =2 inFigure3.1andTable3.9.FromTable3.9,thenumberofnonzeroelementsscaleslike O ( SGDOF 1 : 5 ),where SGDOF isthedegreeoffreedomofthespaceused.Thisisadenser matrixthantheonegeneratedfromtraditionalpiecewisepolynomialspace.However,this isnaturalconsideringthatthebasisfunctionsin ^ V k N arenolongerlocally 82 Table3.9:Sparsityandconditionnumberofthematrix.Example3.3.1com- putedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeoffreedomusedforthe sparsegridDGscheme.NNZisthenumberofnonzeroelementsinthematrix. Order=log(NNZ) = log(SGDOF) : NSGDOFNNZOrderConditionNumber k =1 3809921.573.58E+02 419232161.541.43E+03 544891681.495.68E+03 61024241441.452.26E+04 k =2 318034561.571.40E+03 4432111241.545.49E+03 51008315961.502.16E+04 62304830281.468.58E+04 (a) (b) Figure3.1:Example3.3.1.Thesparsitypattensofthematricescomputedbythespace ^ V k 6 with k =1 ; 2andN=6.Eachdotrepresentsanon-zeroelementinthematrix. (a): k =1,(b): k =2 : Example3.3.2 Wesolvethefollowingtwo-dimensionalproblemwithsmoothvariableco- ton=[0 ; 1] 2 . 8 > > > < > > > : ((sin( x 1 x 2 )+1) r u )= f; x 2 ; u =0 ; x 2 @ : (3.10) 83 Table3.10:NumericalerrorsandordersofaccuracyforExample3.3.2computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 31.30E-021.65E-034.50E-023.37E-01 43.18E-032.034.08E-032.011.34E-021.741.66E-011.02 57.81E-042.021.01E-032.014.43E-031.608.26E-021.01 61.94E-042.012.55E-041.991.48E-031.584.11E-021.00 k =2 31.77E-042.17E-045.74E-041.35E-02 42.71E-052.703.37E-052.691.01E-042.513.37E-032.00 53.99E-062.765.08E-062.731.91E-052.408.41E-042.00 65.67E-072.827.37E-072.782.99E-062.672.10E-042.00 f isagivenfunctionsuchthattheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 ).Thenumerical resultsareprovidedinTable3.10.TheconclusionisverysimilartoExample3.3.1. Example3.3.3 Wesolvethefollowingtwo-dimensionalproblemwithdiscontinuousco cienton=[0 ; 1] 2 . 8 > > > < > > > : ((sign(( x 1 0 : 5)( x 2 0 : 5))+2) r u )= f; x 2 ; u =0 ; x 2 @ : (3.11) f isagivenfunctionsuchthattheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 ).Weprovidethe numericalresultswith k =1and k =2inTable3.11.Forthisproblemwithsmoothsolution butdiscontinuouscot,theconvergenceratesaremaintained. 3.3.2Three-dimensionalResults Inthissubsection,wegathercomputationalresultsforthree-dimensionalellipticequations. Thepenaltyconstantinthissubsectionischosentobe ˙ =15for k =1 ; and ˙ =30for k =2. 84 Table3.11:NumericalerrorsandordersofaccuracyforExample3.3.3computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 31.24E-021.57E-024.55E-023.33E-01 43.07E-032.023.94E-032.001.36E-031.751.66E-021.00 57.58E-042.029.78E-042.014.50E-031.598.32E-021.00 61.89E-042.002.46E-041.991.50E-031.584.16E-021.00 k =2 31.96E-042.59E-041.21E-031.56E-02 42.72E-052.853.50E-052.891.55E-042.963.70E-032.08 53.85E-062.824.94E-062.822.05E-052.928.93E-042.05 65.36E-072.847.02E-072.823.01E-062.822.19E-042.03 Example3.3.4 Wesolvethefollowingthree-dimensionalproblemwithconstantcot on=[0 ; 1] 3 . 8 > > > < > > > : u =0 ; x 2 ; u =sin( ˇx 1 )sin( ˇx 2 ) sinh( ˇx 3 ) sinh( ˇ ) ; x 2 @ ; (3.12) wheretheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 ) sinh( ˇx 3 ) sinh( ˇ ) .Weprovidethenumericalresults with k =1and k =2inTable3.12.Forthisthree-dimensionalexample,weobtain k -thorder forthe H 1 norm,andcloseto( k +1)-thorderforthe L 1 and L 2 norm.However, L 1 error seemstodegradeto( k + 1 2 )-thorder.However,uponcloserexamination,similarbehaviors havebeenobservedinSection3.1.4forthe L 2 projectionerrorofasmoothfunctiononto ^ V k N : Thesparsitypatternsofthematricesfor k =1and k =2arereportedinFigure 3.2.FromTable3.13,wecanseethematricesscalelessthanthetwo-dimensional examples,i.e.thenumberofnonzeroelementsscaleslike O ( SGDOF 1 : 4 ),where SGDOF is thedegreeoffreedomofthespaceused. 85 Table3.12:NumericalerrorsandordersofaccuracyforExample3.3.4computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 31.29E-022.19E-021.09E-012.85E-01 44.05E-031.676.98E-031.654.75E-021.201.44E-010.98 51.07E-031.921.94E-031.852.34E-021.027.02E-021.04 62.76E-041.965.22E-041.898.44E-041.473.39E-021.05 k =2 31.41E-042.06E-041.26E-031.05E-02 42.51E-052.493.80E-052.443.35E-041.912.72E-021.95 54.18E-062.596.49E-062.556.51E-052.366.87E-041.98 66.69E-072.641.06E-062.621.09E-052.581.72E-042.00 Table3.13:Sparsityandconditionnumberofthematrix.Example3.3.4com- putedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeoffreedomusedforthe sparsegridDGscheme.NNZisthenumberofnonzeroelementsinthematrix. Order=log(NNZ) = log(SGDOF) : NSGDOFNNZOrderConditionNumber k =1 330437601.433.73E+02 4832140801.421.51E+03 52176457601.395.97E+03 655041358721.372.36E+04 k =2 31026202501.431.58E+03 42808746281.415.98E+03 573442405161.392.32E+04 6185767105321.379.15E+04 86 (a) (b) Figure3.2:Example3.3.4.Thesparsitypattensofthematricescomputedbythespace ^ V k 6 with(a) k =1and(b) k =2.N=6. Example3.3.5 Wesolvethefollowingthree-dimensionalproblemwithsmoothvariable coton=[0 ; 1] 3 . 8 > > > < > > > : ((sin( x 1 x 2 x 3 )+1) r u )= f; x 2 ; u =0 ; x 2 @ ; (3.13) f isagivenfunctionsuchthattheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 )sin( ˇx 3 ).We providethenumericalresultswith k =1and k =2inTable3.14.Theconclusionissimilar toExample3.3.4. 87 Table3.14:NumericalerrorsandordersofaccuracyforExample3.3.5computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 32.64E-023.40E-021.55E-014.32E-01 46.23E-032.088.58E-031.983.54E-022.132.04E-011.08 51.49E-032.062.10E-042.032.07E-020.779.82E-021.06 63.68E-042.025.32E-041.987.58E-031.454.80E-021.03 k =2 31.63E-042.05E-048.24E-041.19E-02 42.88E-052.503.66E-052.481.63E-042.343.00E-031.98 54.72E-062.616.06E-062.602.73E-052.587.54E-042.00 67.42E-072.679.58E-072.665.80E-062.231.88E-042.00 3.3.3Four-dimensionalResults Inthissubsection,wegathercomputationalresultsforfour-dimensionalcases.Thepenalty constantinthissubsectionischosentobe ˙ =30for k =1 ; and ˙ =60for k =2. Example3.3.6 Wesolvethefollowingfour-dimensionalproblemwithconstantvariable coton=[0 ; 1] 4 . 8 > > > < > > > : u =0 x 2 ; u =sin( ˇx 1 )sin( ˇx 2 )sin( ˇx 3 ) sinh( ˇx 4 ) sinh( ˇ ) x 2 @ (3.14) wheretheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 )sin( ˇx 3 ) sinh( ˇx 4 ) sinh( ˇ ) . Weplotthenumericalresultsfor k =1and k =2inFigure3.3andTable3.15.Forthis four-dimensionalexample,weobtain k -thorderforthe H 1 norm,andcloseto( k + 1 2 )-th orderforthe L 1 and L 2 norm.The L 1 errorseemstoHowever,weexpectthe orderofaccuracyin L 1 normtogrowuponment.Thesparsitypatternsofthe matricesfor k =1and k =2arereportedinFigure3.4.FromTable3.16,wecanseethe 88 Table3.15:NumericalerrorsandordersofaccuracyforExample3.3.6computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 32.44E-024.22E-023.31E-013.91E-01 41.08E-021.182.08E-021.021.16E-011.512.37E-010.73 53.68E-031.547.15E-031.549.33E-020.311.22E-010.96 k =2 28.21E-041.34E-031.11E-024.20E-02 31.76E-042.222.79E-042.272.76E-032.001.20E-021.81 43.32E-052.405.39E-052.378.76E-041.663.18E-031.91 matricesscalelessthanthetwo-dimensionalandthree-dimensionalexamples,i.e. thenumberofnonzeroelementsscaleslike O ( SGDOF 1 : 35 ),where SGDOF isthedegreeof freedomofthespaceused. (a) (b) Figure3.3:Example3.3.6.(a) k =1;(b) k =2. N =4.Plottedalong x 1 =0 : 4930 ;x 2 = 0 : 4930. 89 Table3.16:Sparsityandconditionnumberofthematrix.Example3.3.6com- putedbythespace ^ V k N with k =1 ; 2.SGDOFisthedegreeoffreedomusedforthe sparsegridDGscheme.NNZisthenumberofnonzeroelementsinthematrix. Order=log(NNZ) = log(SGDOF) : NSGDOFNNZOrderConditionNumber k =1 31008122721.364.27E+02 43072517121.352.26E+03 588321870081.349.27E+03 k =2 21539196831.357.40E+02 351031023031.352.62E+03 4155524203361.349.72E+03 (a) (b) Figure3.4:Example3.3.6.Thesparsitypattensofthematricescomputedbythespace ^ V k 4 with(a) k =1and(b) k =2. 90 Example3.3.7 Wesolvethefollowingfour-dimensionalproblemwithsmoothvariableco- ton=[0 ; 1] 4 . 8 > > > < > > > : ((sin( x 1 x 2 x 3 x 4 )+1) r u )= f; x 2 ; u =0 ; x 2 @ ; (3.15) f isagivenfunctionsuchthattheexactsolutionis u =sin( ˇx 1 )sin( ˇx 2 )sin( ˇx 3 )sin( ˇx 4 ). Weprovidethenumericalresultswith k =1and k =2inTable3.17.Theconclusionis similartoExample3.3.6. Table3.17:NumericalerrorsandordersofaccuracyforExample3.3.7computedbythe space ^ V k N with k =1 ; 2andindicated N . N L 1 errororder L 2 errororder L 1 errororder H 1 errororder k =1 36.15E-028.97E-022.94E-016.67E-01 41.89E-021.702.63E-021.772.54E-010.213.20E-011.06 54.51E-032.076.80E-031.957.15E-021.831.45E-011.14 k =2 28.38E-041.09E-033.49E-033.74E-02 31.62E-042.372.13E-042.361.34E-031.381.01E-021.90 42.97E-052.443.91E-052.453.80E-041.822.57E-031.97 91 Chapter4 Conclusion Inthisthesis,weproposedtDGschemesforHJequationsandhigh-dimensional ellipticequationstosavecomputationandstoragecostswhilemaintainingaccuracyofthe numericalsolution. InChapter2,weproposedanewentropyDGmethodtodirectlysolvefortheviscos- itysolutionofthegeneralHJequations.TheHartenandHymansentropyterm,which isproportionaltothejumpofthenormalderivativeofthenumericalsolution,isaddedto correcttheentropyviolationautomaticallywhenneeded.Oneandtwodimensionalnumeri- calexperimentsonbothstructuredandunstructuredmesheswereprovidedtodemonstrate goodperformanceofthismethod. InChapter3,wedevelopedasparsegridIPDGmethodfortcomputationsofhigh- dimensionalsecond-orderellipticproblems.Theorthonormalhierarchicaltensorproduct basisrepresentationallowedustoutilizethesparsegridtechniquetoreducethedegrees offreedomfromthestandardexponentialdependence O ( h d )to O ( h 1 j log 2 h j d 1 )for d -dimensionalproblems.ErrorestimateintheenergynormhasbeenprovedfortheIP formulationoftheellipticequations.Thegoodperformanceofthismethodisvalidated bythenumericalresultsinmulti-dimensions.Comparedtoconventionalfullgridmethods, thenewsparsegridDGmethodscansavestorageandcomputationcostasthesizeof approximationspacesaretlyreduced.Futureworkincludesthedevelopmentof adaptivesparsegridDGmethodsbasedonhierarchicalsurplusandapproximationtheory 92 forvarioustypesofsparseelementspace. 93 BIBLIOGRAPHY 94 BIBLIOGRAPHY [1] R.Abgrall.NumericaldiscretizationoftheHamilton-Jacobiequationon triangularmeshes. Comm.PureAppl.Math. ,49(12):1339{1373,1996. [2] SAchatz.Higherordersparsegridmethodsforellipticpartialtialequations withvariablecots. Computing ,71(1):1{15,2003. [3] B.Alpert,G.Beylkin,D.Gines,andL.Vozovoi.Adaptivesolutionofpartialtial equationsinmultiwaveletbases. J.Comput.Phys. ,182(1):149{190,2002. [4] B.K.Alpert.AclassofbasesinL^2forthesparserepresentationofintegraloperators. SIAMJ.Math.Anal. ,24(1):246{262,1993. [5] R.Archibald,G.Fann,andW.Shelton.AdaptivediscontinuousGalerkinmethodsin multiwaveletsbases. Appl.Numer.Math. ,61(7):879{890,2011. [6] D.A.Arnold.Aninteriorpenaltyelementmethodwithdiscontinuouselements. SIAMJ.Numer.Anal. ,19(4):742{760,1982. [7] D.A.Arnold,F.Brezzi,B.Cockburn,andL.Marini.analysisofdiscontinuous Galerkinmethodsforellipticproblems. SIAMJ.Numer.Anal. ,39:1749{1779,2002. [8] K.I.Babenko.Approximationofperiodicfunctionsofmanyvariablesbytrigonometric polynomials. DokladyAkademiiNaukSSSR ,132(2):247{250,1960. [9] I.BabuskaandM.amal.Nonconformingelementsintheelementmethodwith penalty. SIAMJ.Numer.Anal. ,10(5):863{875,1973. [10] G.A.Baker.Finiteelementmethodsforellipticequationsusingnonconformingelements. Math.Comp. ,31(137):45{59,1977. [11] G.A.Baker,W.N.Jureidini,andO.A.Karakashian.Piecewisesolenoidalvector andtheStokesproblem. SIAMJ.Numer.Anal. ,27(6):1466{1485,1990. [12] F.BassiandS.Rebay.Ahigh-orderaccuratediscontinuouselementmethodfor thenumericalsolutionofthecompressibleNavier-Stokesequations. J.Comput.Phys. , 131:267{279,1997. 95 [13] G.Baszenski,F.-J.Delvos,andS.Jester.Blendingapproximationswithsinefunctions. In NumericalMethodsinApproximationTheory ,volume9,pages1{19.Springer,1992. [14] R.E.Bellman. Adaptivecontrolprocesses:aguidedtour ,volume4.PrincetonUniversity PressPrinceton,1961. [15] O.Bokanowski,Y.Cheng,andC.-W.Shu.AdiscontinuousGalerkinsolverforfront propagation. SIAMJ.Sci.Comput. ,33:923{938,2011. [16] O.Bokanowski,Y.Cheng,andC.-W.Shu.AdiscontinuousGalerkinschemeforfront propagationwithobstacles. Numer.Math. ,126(1):1{31,2014. [17] F.Brezzi,G.Manzini,D.Marini,P.Pietra,andA.Russo.DiscontinuousGalerkin approximationsforellipticproblems. NumericalMethodsforPartialentialEqua- tions ,16(4):365{378,2000. [18] H.-J.Bungartz.Amultigridalgorithmforhigherorderelementsonsparsegrids. ElectronT.Numer.Ana. ,6:63{77,1997. [19] H.-J.Bungartz. Finiteelementsofhigherorderonsparsegrids .Shaker,1998. [20] H.-J.BungartzandT.Dornseifer.Sparsegrids:Recentdevelopmentsforellipticpartial tialequations.In MultigridMethodsV ,pages45{70.Springer,1998. [21] H.-J.BungartzandM.Griebel.Sparsegrids. Actanumer. ,13:147{269,2004. [22] J.L.D.Calle,P.R.B.Devloo,andS.M.Gomes.Waveletsandadaptivegridsforthe discontinuousGalerkinmethod. NumericalAlgorithms ,39(1-3):143{154,2005. [23] P.Castillo,B.Cockburn,I.Perugia,andD.Scotzau.Anapriorierroranalysisof thelocaldiscontinuousGalerkinmethodforellipticproblems. SIAMJ.Numer.Anal. , 38(5):1676{1706,2000. [24] Y.ChenandB.Cockburn.Anadaptivehigh-orderdiscontinuousGalerkinmethodwith errorcontrolfortheHamilton-Jacobiequations.PartI:Theone-dimensionalsteady statecase. J.Comput.Phys. ,226(1):1027{1058,2007. [25] Y.ChengandC.-W.Shu.AdiscontinuousGalerkinelementmethodfordirectly solvingtheHamilton-Jacobiequations. J.Comput.Phys. ,223:398{415,2007. 96 [26] P.Ciarlet. Theelementmethodforellipticproblems .North-Holland,Amsterdam, 1975. [27] B.CockburnandC.Dawson.SomeextensionsofthelocaldiscontinuousGalerkin methodforconvequationsinmultidimensions.In TheProceedingsof theConferenceontheMathematicsofFiniteElementsandApplications:MAFELAP X.Elsevier ,pages225{238,2000. [28] B.Cockburn,G.Kanschat,I.Perugia,andD.Scotzau.Superconvergenceofthelocal discontinuousGalerkinmethodforellipticproblemsoncartesiangrids. SIAMJ.Numer. Anal. ,39(1):264{285,2001. [29] B.Cockburn,F.Li,andC.-W.Shu.Locallydivergence-freediscontinuousGalerkin methodsfortheMaxwellequations. J.Comput.Phys. ,194:588{610,2004. [30] B.CockburnandC.-W.Shu.ThelocaldiscontinuousGalerkinmethodfortime- dependentconvsystems. SIAMJ.Numer.Anal. ,35(6):2440{2463,1998. [31] B.CockburnandC.-W.Shu.Runge-KuttadiscontinuousGalerkinmethodsfor convection-dominatedproblems. J.Sci.Comput. ,16:173{261,2001. [32] M.G.Crandall,L.C.Evans,andP.-L.Lions.Somepropertiesofviscositysolutionsof Hamilton-Jacobiequations. Trans.Amer.Math.Soc. ,282(2):487{502,1984. [33] M.G.CrandallandP.-L.Lions.ViscositysolutionsofHamilton-Jacobiequations. Trans. Amer.Math.Soc. ,277:1{42,1983. [34] M.G.CrandallandP.-L.Lions.TwoapproximationsofsolutionsofHamilton-Jacobi equations. Math.Comp. ,43:1{19,1984. [35] C.Dawson,S.Sun,andM.F.Wheeler.Compatiblealgorithmsforcoupledwand transport. Comput.MethodsAppl.Mech.Eng. ,193(23):2565{2580,2004. [36] F.-J.Delvos. d -variateBooleaninterpolation. J.Approx.Theory. ,34(2):99{114,1982. [37] J.DouglasandT.Dupont.Interiorpenaltyproceduresforellipticandparabolicgalerkin methods.In Computingmethodsinappliedsciences ,pages207{216.Springer,1976. [38] J.GarckeandM.Griebel. Sparsegridsandapplications .Springer,2013. 97 [39] N.GerhardandS.Muller.AdaptivemultiresolutiondiscontinuousGalerkinschemes forconservationlaws:multi-dimensionalcase. Comput.Appl.Math. ,pages1{29,2013. [40] T.GerstnerandM.Griebel.Numericalintegrationusingsparsegrids. Numerical algorithms ,18(3-4):209{232,1998. [41] S.Gottlieb,C.-W.Shu,andE.Tadmor.Strongstabilitypreservinghighordertime discretizationmethods. SIAMRev ,43:89{112,2001. [42] V.Gradinaru.Fouriertransformonsparsegrids:codedesignandthetimedependent Scodingerequation. Computing ,80(1):1{22,2007. [43] M.Griebel.Aparallelizableandvectorizablemulti-levelalgorithmonsparsegrids.In W.Hackbusch,editor, Parallelalgorithmsforpartialentialequations ,volume31 of Notesonnumericalmechanics ,pages94{100.1991. [44] M.Griebel.AdaptivesparsegridmultilevelmethodsforellipticPDEsbasedon Computing ,61(2):151{179,1998. [45] M.Griebel.Sparsegridsandrelatedapproximationschemesforhigherdimensional problems.In Proceedingsoftheconferenceonfoundationsofcomputationalmathemat- ics ,Santander,Spain,2005. [46] M.GriebelandJ.Hamaekers.SparsegridsfortheScodingerequation. ESAIM: MathematicalModellingandNumericalAnalysis ,41(02):215{247,2007. [47] M.GriebelandP.Oswald.Tensorproducttypesubspacesplittingsandmultilevel iterativemethodsforanisotropicproblems. Adv.Comput.Math. ,4(1):171{206,1995. [48] M.Griebel,C.Zenger,andS.Zimmer.MultilevelGauss-Seidel-algorithmsforfulland sparsegridproblems. Computing ,50(2):127{148,1993. [49] M.GriebelandG.Zumbusch.Adaptivesparsegridsforhyperbolicconservationlaws. In Hyperbolicproblems:theory,numerics,applications ,pages411{422.Springer,1999. [50] W.Guo,F.Li,andJ.Qiu.Local-structure-preservingdiscontinuousGalerkinmethods withLax-WtypetimediscretizationsforHamilton-Jacobiequations. J.Sci. Comput. ,47(2):239{257,2011. [51] A.Haar.Zurtheoriederorthogonalenfunktionensysteme. MathematischeAnnalen , 69(3):331{371,1910. 98 [52] A.Harten.Multiresolutionalgorithmsforthenumericalsolutionofhyperbolicconser- vationlaws. Comm.PureAppl.Math. ,48(12):1305{1342,1995. [53] A.HartenandJ.M.Hyman.Selfadjustinggridmethodsforone-dimensionalhyperbolic conservationlaws. J.Comput.Phys. ,50(2):235{269,1983. [54] P.W.Hemker.Sparse-gridolumemultigridfor3D-problems. Adv.Comput. Math. ,4(1):83{110,1995. [55] N.Hovhannisyan,S.Muller,andR.Scafer.Adaptivemultiresolutiondiscontinuous Galerkinschemesforconservationlaws. Math.Comp. ,83(285):113{151,2014. [56] C.HuandC.-W.Shu.AdiscontinuousGalerkinelementmethodforHamilton- Jacobiequations. SIAMJ.Sci.Comput. ,21:666{690,1999. [57] F.Iacono,G.May,S.Muller,andR.Scafer.Ahigh-orderdiscontinuousGalerkin discretizationwithmultiwavelet-basedgridadaptationforcompressiblews. AICES PreprintAICES-2011/08-1,RWTHAachen ,2011. [58] G.JiangandD.Peng.WeightedENOschemesforHamilton-Jacobiequations. SIAM J.Sci.Comput. ,21:2126{2143,1999. [59] S.JinandZ.Xin.NumericalpassagefromsystemsofconservationlawstoHamilton- Jacobiequations,andrelaxationschemes. SIAMJ.Numer.Anal. ,35(6):2385{2404, 1998. [60] L.Krivodonova.Limitersforhigh-orderdiscontinuousGalerkinmethods. J.Comput. Phys. ,226(1):879{896,2007. [61] F.LiandC.-W.Shu.Reinterpretationandimplementationofadiscontinuous GalerkinmethodforHamilton-Jacobiequations. Appl.Math.Lett. ,18:1204{1209,2005. [62] F.LiandS.Yakovlev.AcentraldiscontinuousGalerkinmethodforHamilton-Jacobi equations. J.Sci.Comput. ,45(1-3):404{428,2010. [63] C.B.Liem,T.Lu,andT.M.Shih. Thesplittingextrapolationmethod:anewtechnique innumericalsolutionofmultidimensionalproblems ,volume7.WorldScien1995. [64] W.A.Mulder.Anewmultigridapproachtoconvectionproblems. J.Comput.Phys. , 83(2):303{323,1989. 99 [65] N.H.NaikandJ.VanRosendale.Theimprovedrobustnessofmultigridellipticsolvers basedonmultiplesemicoarsenedgrids. SIAMJ.Numer.Anal. ,30(1):215{229,1993. [66] J.T.Oden,I.Babuska,andC.E.Baumann.Adiscontinuous hp elementmethod forproblems. J.Compt.Phys. ,146(2):491{519,1998. [67] S.OsherandJ.A.Sethian.Frontspropagatingwithcurvature-dependentspeed:algo- rithmsbasedonHamilton-Jacobiformulations. J.Comput.Phys. ,79(1):12{49,1988. [68] S.OsherandC.-W.Shu.Highorderessentiallynon-oscillatoryschemesforHamilton- Jacobiequations. SIAMJ.Numer.Anal. ,28:907{922,1991. [69] C..Amultilevelalgorithmforthesolutionofsecondorderelliptictial equationsonsparsegrids. Numer.Math. ,79(1):141{155,1998. [70] B.Riviere,M.F.Wheeler,andV.Girault.Apriorierrorestimatesforelement methodsbasedondiscontinuousapproximationspacesforellipticproblems. SIAMJ. Numer.Anal. ,39(3):902{931,2001. [71] C.Schwab,E.Suli,andR.A.Todor.Sparseelementapproximationofhigh- dimensionaltransport-dominatedusionproblems. ESAIM:MathematicalModelling andNumericalAnalysis ,42(05):777{819,2008. [72] J.ShenandL.-L.Wang.Sparsespectralapproximationsofhigh-dimensionalproblems basedonhyperboliccross. SIAMJ.Numer.Anal. ,48(3):1087{1109,2010. [73] J.ShenandH.Yu.tspectralsparsegridmethodsandapplicationstohigh- dimensionalellipticproblems. SIAMJ.Sci.Comput. ,32(6):3228{3250,2010. [74] C.-W.Shu.HighordernumericalmethodsfortimedependentHamilton-Jacobiequa- tions. MathematicsandComputationinImagingScienceandInformationProcessing, Lect.NotesSer.Inst.Math.Sci.Natl.Univ.Singap ,11:47{91,2007. [75] C.-W.Shu.SurveyondiscontinuousGalerkinmethodsforHamilton-Jacobiequations. RecentAdvancesinComputingandApplications ,586:323,2013. [76] C.-W.ShuandS.Osher.timplementationofessentiallynon-oscillatoryshock- capturingschemes. J.Comput.Phys. ,77:439{471,1988. [77] S.A.Smolyak.Quadratureandinterpolationformulasfortensorproductsofcertain classesoffunctions.In Dokl.Akad.NaukSSSR ,volume4,pages240{243,1963. 100 [78] P.E.Souganidis.ApproximationschemesforviscositysolutionsofHamilton-Jacobi equations. J.Equations ,59(1):1{43,1985. [79] V.N.Temlyakov.Approximationsoffunctionswithboundedmixedderivative. Trudy MatematicheskogoInstitutaim.VASteklova ,178:3{113,1986. [80] M.J.VuikandJ.K.Ryan.Multiwavelettroubled-cellindicatorfordiscontinuitydetec- tionofdiscontinuousGalerkinschemes. J.Comput.Phys. ,270:138{160,2014. [81] W.WangandC.-W.Shu.TheWKBlocaldiscontinuousGalerkinmethodforthe simulationofScodingerequationinaresonanttunnelingdiode. J.Sci.Comput. , 40(1-3):360{374,2009. [82] M.F.Wheeler.Anellipticcolloelementmethodwithinteriorpenalties. SIAMJ.Numer.Anal. ,15(1):152{161,1978. [83] T.Xiong,C.-W.Shu,andM.Zhang.Apriorierrorestimatesforsemi-discretediscon- tinuousGalerkinmethodssolvingnonlinearHamilton-Jacobiequationswithsmooth solutions. Int.J.Numer.Anal.Mod. ,10:154{177,2013. [84] J.YanandS.Osher.AlocaldiscontinuousGalerkinmethodfordirectlysolving Hamilton-Jacobiequations. J.Comput.Phys. ,230(1):232{244,2011. [85] L.YuanandC.-W.Shu.DiscontinuousGalerkinmethodbasedonnon-polynomial approximationspaces. J.Comput.Phys. ,218(1):295{323,2006. [86] C.Zenger.Sparsegrids.In ParallelAlgorithmsforPartialentialEquations, ProceedingsoftheSixthGAMM-Seminar ,volume31,1990. [87] Y.-T.ZhangandC.-W.Shu.HighorderWENOschemesforHamilton-Jacobiequations ontriangularmeshes. SIAMJ.Sci.Comput. ,24:1005{1030,2003. 101