Fast computation tools for adaptive wavelet schemes [Elektronische Ressource] / vorgelegt von Arne Barinka

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2005
• Nombre de lectures: 10
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Fast Computation Tools
for Adaptive Wavelet Schemes
VonderMathematisch–Naturwissenschaftlichen Fakult¨atder
Rheinisch–Westf¨alischenTechnischenHochschuleAachen
zurErlangungdesakademischenGrades
einesDoktorsderNaturwissenschaften
genehmigteDissertation
vorgelegtvon
Diplom–Mathematiker
Arne Barinka
ausTrier
Berichter: Univ.–Prof.Dr.rer.nat.WolfgangDahmen
Univ.–Prof.Dr.rer.nat.ReinholdSchneider
Tag der mundlic¨ henPrufung:¨ 17.03.2005
DieseDissertationistaufdenInternetseitenderHochschulbibliothek
onlineverfugbar.¨Acknowledgments
IwishtoexpressmysinceregratitudetoProf.Dr.W.Dahmen,Prof.Dr.
R.Schneider,Prof.Dr.St.Dahlke,Dr.M.Konik,Dr.T.Barsch,Prof.Dr.
K.Urban,andA.Voß–mycollaborators,co-authorsandteachers.
Special thanks are devoted to Prof. Wolfgang Dahmen, who provides so
much inspiring challenge, Alexander Voß my math- and soul-mate, Nina
Gierforbeingtherewhenitcounts,andmyparents,fortheirbullet-proof
support. Danke.Abstract
Duringthepastfewyears,anewalgorithmicparadigmforadaptivewavelet
schemes was developed. First approaches covered elliptic problems, but
meanwhile, the class of feasible problems could be significantly enlarged,
includingevencertainnonlinearproblems.
Thisthesiswillpresentandanalyzeroutinesforkeytasksarisingincon-
nectionwiththoseschemes. Thecentralpointwillbeasocalled recovery
schemethatallowstocomputearraysofwaveletcoefficientsefficientlyby
treatingthearrayasawholeinsteadoftreatingeachentryseparatelyby
quadratureschemes.
The tools and methods we develop are realized in a C++ implementa-
tionbytheauthor,whichwepresentinformofaschematicoverview. All
numericalstudiespresentedinthethesisarebasedonthisimplementation.
Zusammenfassung
IndenletztenJahrenwurdeeinneuesalgorithmischesParadigmafur¨ adap-
tive Wavelet-Algorithmen entwickelt. Erste Ans¨atze behandelten ellip-
tische Probleme, doch mittlerweile konnte die Klasse der behandelbaren
Probleme starkerweitert werden unddeckt mittlerweile sogarbestimmte
nichtlineareProblemeab.
IndervorliegendenArbeitpr¨asentierenundanalysierenwirL¨osungsmetho-
denfur¨ zentraleTeil-AufgabendieserneuenSchemata. DerzentralePunkt
wirdeinsogenanntes recovery schemesein,welcheserlaubt,Vektorenvon
Wavelet-KoeffizientenalsGanzeszuberechnen,anstattjedenEintrageinzeln
mittelsQuadraturzubestimmen.
Die entwickelten Werkzeuge und Methoden wurden vom Autor in einer
C++Implementierungumgesetzt. DiesewirdinschematischerFormvorge-
stellt. Allehierpr¨asentiertennumerischenBeispielewurdenmitHilfedieser
Implementierungerstellt.Contents
Introduction 1
I Prerequisites 7
1 Nonlinear Approximation: Sorting and Thresholding 11
1.1 N-termApproximation.....................1
1.2Binning:ApproximateSorting......17
1.2.1ConstructionandEstimates...18
1.2.2ComputationalIsues..................19
2 Wavelet Prerequisites 25
2.1ConstructionandEsentialFeatures...25
2.2CardinalB-splineWavelets...................3
2.3Tre–likeStructuredIndexSets.....35
II Development of the Tools 41
3 The Recovery Scheme 45
3.1ObjectivesandBackground..................45
3.2TheAlgorithm..............49
3.2.1MotivationandMainIdea....50
3.2.2ATop–To–BotomScheme...........53
3.3ErorEstimates..............56
3.3.1ExactQuadrature.........57
3.3.2 The L-Case............582ii Contents
3.3.3DualNorms.......................62
3.3.4 AWishlistfortheQuadratureMappings L .....68j
3.4 RecoverforCardinalB-SplineWavelets..........70
3.4.1 Determinationof G ............70j
3.4.2 Well-Gradedness .........72
4 Supporting Tools 75
4.1Quadrature...........................75
4.1.1ReliableQuadrature.7
4.1.2 Gauss-QuadratureforRefinableFunctions......80
4.2Index-Structure...................8
∗4.3 Recover:EverythinginoneSwep.............91
III Applications and Numerical Results 95
5LayoutoftheTests 9
6 Approximation in L 1012
6.1 DirectApplications: g= v...................101
6.1.1 Applying Recover..101
6.1.2 Failures: Significance of the Safety Region and the
CorectionStep..........19
6.2 ApproximatingCompositions: g= y ◦u......120
7 Prediction Sets for Compositions 127
7.1PredictingApproximationSpacesforCompositions.....127
7.2NumericalResults........................13
8 Dual Norms 141
8.1 GausQuadrature.............141
8.2LeastSquaresQuadrature.............143
IV Realization 147
9 Conceptual Remarks 151Contents iii
9.1KeyRequirementsforaRealization..............153
9.1.1HowtoTreatWaveletExpansions?..........154
9.1.2TheImportanceofPointValues.15
9.2IndexManagement:WhyNoTreStructure?........15
10 Implementation 159
10.1RequirementsontheComponents ..............159
10.2ATourThroughtheWaveletLibrary .160
10.2.1 IndexManagement igpm t lib .162
10.2.2WaveletImplementation................165
10.2.3Index-Manipulation........167
10.2.4Binning..............167
10.2.5 AuxiliaryClassesandRoutines ............167
ListofFigures.......169
ListofAlgorithms...............171Introduction
Duringthepastfewyears,anewalgorithmicparadigmforadaptivewavelet
schemes was developed, [DHU00, CDD01, CDD00, CDD03a, CDD03c].
Firstapproachescoveredellipticproblemssuchasellipticboundaryintegral
andboundaryvalueproblems,butmeanwhile,theclassoffeasibleproblems
couldbesignificantlyenlarged,includingevencertainnonlinearproblems.
Thistheseswillpresentandanalyzeroutinesforkeytasksarisingincon-
nectionwiththeseschemes. Thecentralpointwillbeasocalled recovery
schemethatallowstocomputearraysofwaveletcoefficientsefficientlyby
treatingthearrayasawhole,insteadoftreatingeachentryseparatelyby
quadratureschemes.
The new paradigm comes with new challenges concerning computational
issues, whence thereisaneedfornewcomputationaltoolssuitedforthe
new adaptive schemes. This is mainly due to their special requirements
concerninga)data-handlingandb)efficiency.
a)Thedata-handlingrequirementsresultfromthefactthattheproposed
strategyisaniterativeroutineusingfiniteapproximantsthatare dynami-
cally updatedduringeachstepoftheiteration.
b) Efficiency is a major issue, because the central points of investigation
inthedevelopmentofthenewparadigmweretheoreticalconvergenceand
complexityestimates. Theyfinallyleadtonumericalschemesthatareca-
pableofsolvingagivenproblemwithan asymptotically optimalexpenseof
computationalcomplexitywhenevertheircomputationalingredientssatisfy
certainnow well identified requirements. Optimalmeansinthiscontext,
that the work in terms of floating point operations and storage manipu-
lations stays proportional to the number of degrees of freedom that are
intrinsicallyneededtoachieveadesiredtargetaccuracy.
Forcertainmodelcases,computationalingredientsthatatleastasymptot-
ically satisfy these requirements can be easily realized, however the next
crucialstepistodevelopcomputationaltoolsthatstillsatisfythesecon-
ditionsforawiderrealisticclassofproblems. Thefinalgoalisofcourseis2 Introduction
toputatdisposalefficient andflexible computationaltoolsthatallowto
fastlyrealizethenewschemesinformofcomputerprogramsthatpreserve
alltheoreticalachievements.
Background and Motivation
Thegeneralformatoftheproblemsweareconcernedwithcanbestated
asfollows. Let HbeaHilbertspaceand H itsdual. Given F :H→H
andany f ∈Hwewishtofinda u∈Hsuchthat
v,F(u)= v,fv∈H, (0.0.1)
wherethisproblemisassumedtobe well-posedinthesense,cf. [CDD03a],
thatthereexistsauniquesolution u∈Handthatfor vinaneighborhood
U of u,thereexistconstants c ,C ,suchthatforall w∈HF,v F,v
c
w
≤ DF(v)w
≤ C
w
, (0.0.2)F,v H H F,v H
(seealso[CDD03d,CDD03b]). Here DF(·)denotesthe Frechetderivative,
whichisdefinedasmappingfrom Hto H by
−1
v,DF(·)w=limh v,F(·+hw)−F(·).
h→0
Itisessentialinthiscontext,that Hpermitsa wavelet characterization.A
waveletbasisΨ= {ψ ;λ∈J}iscalleda Riesz-basis for Handissaidtoλ
characterize H,ifanorm-equivalencecanbeestablished,i.e.,the H-norm
ofanelementisequivalenttothe -normofits(wavelet-)coefficients.2
Underthesecircumstancesithasbeenshown([CDD01])thatonecanfind
anequivalentformulationoftheoriginalproblemintermsofwaveletcoef-
ficientsinformofan infinite dimensionalsystem F(u)=f,whichisnow
well-posedin .Hereuistheunknownarrayofwaveletcoefficientsofthe2
solution uand f arethedualwaveletcoefficientsoftheright-handside f.
Onethencanformulatean idealiterativeschemeforthediscrete, infinite
dimensionalproblem Fu=f,e.g.

i+1 i iu =u −C F(u)−f ,i=0,1,2,..., (0.0.3)i
where C isa’preconditioner’,chosensuchthatineachstepoftheitera-i
tion,theerrorisatleastreducedbyafixedfactor,whichispossiblebecause
oftheasserted l -well-posedness([CDD01]). Eachstepoftheiterationof2
this idealized scheme is (approximately) executed by approximating theIntroduction 3
iweightedresiduals C (F(u)−f)withincertaindynamicallyupdatedtol-i
ierances.ThisisdonebyadaptiveevaluationofF(u), which mainly re-
quiresthecomputationof(0.0.1)andanadaptiveapplicationof C.Thei
lattertaskbeingproblemdependent,wefocushereonthecomputationof
(0.0.1).
Anevaluationscheme asmentioned above, e.g.for Factingona finitely
supportedarray v,consistsoftwostepsandtakesthefollowingform:
S1) Prediction step: Given a set Λ = Λ(ε) such that
v −v|
≤ ε,Λ 2
forthecurrentaccuracytoleranceε>0,predictapossi