Data Structures and Concepts for Adaptive Finite E

DATASTRUCTURESANDCONCEPTSFORADAPTIVEFINITEELEMENTMETHODSPETERLEINEN,TUBINGENAbstract|ZusammenfassungDataStructuresandConceptsforAdaptiveFiniteElementMethods.Theadminis-trationofstronglynonuniform,adaptivelygeneratedniteelementmeshesrequiresspecializedtechniquesanddatastructures.Aspecialdatastructureofthiskindisdescribedinthispaper.Itreliesonpoints,edgesandtrianglesasbasicstructuresandisespeciallywellsuitedfortherealizationofiterativesolverslikethehierarchicalbasisorthemultilevelnodalbasismethod.AMSSubjectClassications:65N50,65Y99,65N30,65N55,65F10Keywords:Datastructures,adaptiveniteelementmethods.DatenstrukturenundStrategienfuradaptiveFiniteElemente.FurdieVerwal-tungvonextremnichtuniformen,adaptiverzeugtenFiniteElementGitternbenotigtmanspezielleTechnikenundDatenstrukturen.EineDatenstrukturdieserArtwirdindiesemAr-tikelbeschrieben.BasisstrukturensindPunkte,KantenundDreiecke.DieDatenstrukturistbesonderszugeschnittenaufiterativeLoserwiediehierarchischeBasisoderdiemultilevelnodalbasisMethode.1.Introduction.Formanyproblemsofpracticalinterest,adaptivelyrened,stronglynonuniformgridsarenecessarytokeepcontroloftheamountofwork.Clearly,theadministrationofadaptivelyrenedgridsandtheimplementationofsolversusingsuchgridsrequiresspecializedtechniques.Forexample,alocalrenementorderenementshouldnotrequireacompletereconstructionofthedatastructures.Inaddition,thetimeneededtochangethegridshouldremainproportionaltothenumberofchangedelements.Toreachthisoptimalcomplexity,datastructuresareneededwhichtthestructureoftheproblemaswellastherenementscheme.Ofcourse,suchadatastructureshouldbeaslocalaspossiblewhichinturnleadstoatreelikerepresentationoftheinformation.Informationconcerningthetopologicalstructureoftheinvolvedgridsshouldclearlybeseparatedfrompurelynumericalinformationsuchaslocalstinessmatrices.Theconstructionandanalysisofsuchrealizationsofadaptiveniteelementmethodshasbeensubjectofextensiveresearchduringthelastyears.OneoftheoriginatorsoftheeldwasR.E.Bank.HisPiecewiseLinearTriangleMultiGridpackagehasrootsgoingbacktotheseventies[4].Sincethen,ithasevolvedcontinually[3].AmongthenumerousrecentliteraturewementionexplicitlyBastianetal.[7],Bey[11],Bornemannetal.[13],Griebel[24]andRude[42].ThecodesofBastianandBeyaredesignedastoolboxesfortheadaptiveniteelementmethod.GriebeldiscussesmoregeneralconceptsandRudetheimportanceofdatastructures.Astheworkpresentedinthisarticle,theworkofBornemannetal.tracesbacktoacooperationfromthelateeigthies.Forearlyreferencessee[20,22,30].Inthispaper,adetaileddescriptionofadatastructureisgiven,whichfulllstheseyComputing,55:325{354,19952P.Leinenrequirements.Toshowhowtoutilizethisdatastructure,wegivesometypicalsubpro-gramsusedinaniteelementcode.Howeverthereisnorestrictiontoniteelementapplications.Programsforadaptivenumericalquadratureoradaptivevisualizationofdatahavealsobeenderivedfromthesedatastructures.Anotherpossibleapplicationistheimplementationinthemultiresolutiontechniquesassociatedwithwavelets.ThedatastructureisespeciallytailoredtotheimplementationofthehierarchicalbasispreconditionerofYserentant[46,47]andthemultilevelnodalbasispreconditioner[15]ofBramble,PasciakandXubothofwhichareespeciallywellsuitedforadaptivelyrenedgridsandaredirectlybasedonthetreelikehierarchyofgrids.Theimplementationofthesepreconditionersisdiscussedindetail.Noattempthasbeenmadetocreateadatastructurewhicheasilyallowsoperationswhicharebasedonaspecialorderingofthegridpointswhicharethemselvesnotdirectlyassociatedwiththerenementstructure.Suchapproachesarediscussedin[7]and[11]forexample.Therestofthepaperisorganizedasfollows.InSection2,rstaspecialclassofnonuniformniteelementtriangulationisintroduced.Inastrictsense,ourdatastruc-turesrepresentrealizationsoftheserenementrulesbuttheycaneasilybemodiedforsequencesofquadrilateralgridsorfortetrahedralmeshesinthreespacedimensions,forexample.Thehierarchicalbasis{andthemultilevelnodalbasispreconditionersaredescribedinthisSection.InSection3wedenethedatastructuresanddiscussimplementationdetails.Section4and5dealwiththeimplementationofthehierar-chicalbasispreconditionerandthemultilevelnodalbasispreconditioner,respectively.InSection6wegivecomplexityestimates.WeclosewithsomeexamplesinSection7whichcomparetheruntimedierenceofthetwopreconditioners.Thealgorithmsdescribedinthispaperformthebodyofanadaptiveniteelementcodewithoneessentialexception:proceduresfortherenementofagiventriangulationstartingwithamarkedsetofedgesortrianglesarenotgiven.Forthispoint,werefertotherealizationinourniteelementcodeKASKADE[20,30]whichwillbemadeaccessibleinthenearfuture.2.ThePreconditioners.LetacoarsetriangulationT0ofthedomainIR2begiven.ThistriangulationisrenedseveraltimesgivingfurthertriangulationsT1,T2;:::accordingtothefollowingrules(cf.[3]).InthetransitionfromTktoTk+1atriangleiseitherkeptxedoritisdividedintofourcongruenttrianglesorintotwotrianglesbyconnectingoneofitsverticeswiththemidpointoftheoppositeside.Therstcaseiscalledaregularorredrenementandtheresultingtrianglesarecalledregulartriangles.T