Multiscale, Nonlinear and Adaptive Approximation (eBook)

Ronald DeVore's speciality is Nonlinear Approximation Theory. He is The Walter E. Koss Professor of Mathematics at Texas A&M University.He was elected a member of the American Academy of Arts and Sciences in 2001 and received an Honorary Doctorate from RWTH Aachen in 2004. In 2006, he was a Plenary Lecturer at the International Congress of Mathematicians in Madrid. Angela Kunoth is working on wavelet and multiscale methods for solving partial differential equations and for data analysis purposes. She holds the Chair of Complex Systems at Universitaet Paderborn since 2007 and is an editor of five journals in applied mathematics and numerics.

Preface 6
Acknowledgements 7
Contents 8
List of Contributors 17
Introduction: Wolfgang Dahmen's mathematical work 20
Introduction 20
The early years: Classical approximation theory 21
Bonn, Bielefeld, Berlin, and multivariate splines 21
Computer aided geometric design 22
Subdivision and wavelets 23
Wavelet and multiscale methods for operator equations 24
Multilevel preconditioning 24
Compression of operators 24
Adaptive solvers 25
Construction and implementation 26
Hyperbolic partial differential equations and conservation laws 27
Engineering collaborations 28
The present 28
Final remarks 29
Publications by Wolfgang Dahmen (as of summer 2009) 29
The way things were in multivariate splines: A personal view 37
Tensor product spline interpolation 37
Quasiinterpolation 38
Multivariate B-splines 39
Kergin interpolation 41
The recurrence for multivariate B-splines 43
Polyhedral splines 45
Box splines 46
Smooth multivariate piecewise polynomials and the B-net 49
References 52
On the efficient computation of high-dimensional integrals and the approximation by exponential sums 56
Introduction 56
Approximation of completely monotone functions by exponential sums 58
Rational approximation of the square root function 60
Heron's algorithm and Gauss' arithmetic-geometric mean 60
Heron's method and best rational approximation 61
Extension of the estimate (19) 65
An explicit formula 66
Approximation of 1/x by exponential sums 67
Approximation of 1/x on finite intervals 67
Approximation of 1/x on [1,) 68
Approximation of 1/x, > 0
Applications of 1/x approximations 72
About the exponential sums 72
Application in quantum chemistry 72
Inverse matrix 73
Applications of 1/x approximations 75
Basic facts 75
Application to convolution 75
Modification for wavelet applications 77
Expectation values of the H-atom 77
Computation of the best approximation 79
Rational approximation of x on small intervals 80
The arithmetic-geometric mean and elliptic integrals 82
A direct approach to the infinite interval 84
Sinc quadrature derived approximations 85
References 90
Adaptive and anisotropic piecewise polynomial approximation 92
Introduction 92
Piecewise polynomial approximation 92
From uniform to adaptive approximation 94
Outline 96
Piecewise constant one-dimensional approximation 97
Uniform partitions 98
Adaptive partitions 100
A greedy refinement algorithm 102
Adaptive and isotropic approximation 104
Local estimates 105
Global estimates 107
An isotropic greedy refinement algorithm 108
The case of smooth functions 112
Anisotropic piecewise constant approximation on rectangles 117
A heuristic estimate 117
A rigourous estimate 120
Anisotropic piecewise polynomial approximation 125
The shape function 125
Algebraic expressions of the shape function 126
Error estimates 128
Anisotropic smoothness and cartoon functions 129
Anisotropic greedy refinement algorithms 133
The refinement algorithm for piecewise constants on rectangles 136
Convergence of the algorithm 138
Optimal convergence 141
Refinement algorithms for piecewise polynomials on triangles 145
References 151
Anisotropic function spaces with applications 153
Introduction 153
Anisotropic multiscale structures on Rn 155
Anisotropic multilevel ellipsoid covers (dilations) of Rn 155
Comparison of ellipsoid covers with nested triangulations in R2 158
Building blocks 159
Construction of a multilevel system of bases 159
Compactly supported duals and local projectors 161
Two-level-split bases 162
Global duals and polynomial reproducing kernels 164
Construction of anisotropic wavelet frames 167
Discrete wavelet frames 170
Two-level-split frames 171
Anisotropic Besov spaces (B-spaces) 172
B-spaces induced by anisotropic covers of Rn 172
B-spaces induced by nested multilevel triangulations of R2 174
Comparison of different B-spaces and Besov spaces 175
Nonlinear approximation 176
Measuring smoothness via anisotropic B-spaces 178
Application to preconditioning for elliptic boundary value problems 180
References 182
Nonlinear approximation and its applications 184
The early years 184
Smoothness and interpolation spaces 186
The role of interpolation 187
The main types of nonlinear approximation 189
n-term approximation 189
Adaptive approximation 193
Tree approximation 193
Greedy algorithms 196
Image compression 200
Remarks on nonlinear approximation in PDE solvers 202
Learning theory 204
Learning with greedy algorithms 208
Compressed sensing 210
Final thoughts 214
References 214
Univariate subdivision and multi-scale transforms: The nonlinear case 217
Introduction 217
Nonlinear multi-scale transforms: Functional setting 224
Basic notation and further examples 224
Polynomial reproduction and derived subdivision schemes 229
Convergence and smoothness 231
Stability 237
Approximation order and decay of details 241
The geometric setting: Case studies 244
Geometry-based subdivision schemes 245
Geometric multi-scale transforms for planar curves 254
References 259
Rapid solution of boundary integral equations by wavelet Galerkin schemes 262
Introduction 262
Problem formulation and preliminaries 265
Boundary integral equations 265
Parametric surface representation 266
Kernel properties 268
Wavelet bases on manifolds 269
Wavelets and multiresolution analyses 269
Refinement relations and stable completions 271
Biorthogonal spline multiresolution on the interval 272
Wavelets on the unit square 274
Patchwise smooth wavelet bases 279
Globally continuous wavelet bases 280
The wavelet Galerkin scheme 284
Historical notes 285
Discretization 286
A-priori compression 287
Setting up the compression pattern 288
Computation of matrix coefficients 290
A-posteriori compression 292
Wavelet preconditioning 292
Numerical results 294
Adaptivity 297
References 303
Learning out of leaders 308
Introduction 308
Various learning algorithms in Wolfgang Dahmen's work 311
Greedy learning algorithms 311
Tree thresholding procedures 312
Learning out leaders: LOL 316
Gaussian regression model 316
LOL procedure 317
Sparsity conditions on the target function f 318
Results 319
Discussion 320
Restricted LOL 321
Practical performances of the LOL procedure 322
Experimental design 322
Algorithm 323
Simulation results 325
Quality reconstruction 326
Discussion 327
Proofs 329
Preliminaries 329
Concentration lemma 5.4 331
Proof of Theorem 3.2 332
References 336
Optimized wavelet preconditioning 338
Introduction 338
Systems of elliptic partial differential equations (PDEs) 342
Abstract operator systems 342
A scalar elliptic boundary value problem 343
Saddle point problems involving essential boundary conditions 344
PDE-constrained control problems: Distributed control 347
PDE-constrained control problems: Dirichlet boundary control 349
Wavelets 350
Basic properties 350
Norm equivalences and Riesz maps 353
Representation of operators 354
Multiscale decomposition of function spaces 355
Problems in wavelet coordinates 369
Elliptic boundary value problems 369
Saddle point problems 371
Control problems: Distributed control 374
Control problems: Dirichlet boundary control 378
Iterative solution 380
Finite systems on uniform grids 381
Numerical examples 385
References 389
Multiresolution schemes for conservation laws 392
Introduction 392
Governing equations and finite volume schemes 394
Multiscale analysis 396
Multiscale-based spatial grid adaptation 400
Adaptive multiresolution finite volume schemes 402
From the reference scheme to an adaptive scheme 402
Approximate flux and source approximation strategies 403
Prediction strategies 405
Multilevel time stepping 406
Error analysis 410
Numerical results 410
The solver Quadflow 411
Application 411
Conclusion and trends 415
References 418
Theory of adaptive finite element methods: An introduction 422
Introduction 423
Classical vs adaptive approximation in 1d 423
Outline 424
Linear boundary value problems 426
Sobolev spaces 426
Variational formulation 429
The inf-sup theory 432
Two special problem classes 436
Applications 440
Problems 443
The Petrov-Galerkin method and finite element bases 445
Petrov-Galerkin solutions 446
Finite element spaces 451
Problems 458
Mesh refinement by bisection 460
Subdivision of a single simplex 460
Mesh refinement by bisection 464
Basic properties of triangulations 467
Refinement algorithms 470
Complexity of refinement by bisection 475
Problems 481
Piecewise polynomial approximation 482
Quasi-interpolation 482
A priori error analysis 485
Principle of error equidistribution 487
Adaptive approximation 489
Problems 492
A posteriori error analysis 493
Error and residual 494
Global upper bound 495
Lower bounds 500
Problems 508
Adaptivity: Convergence 510
The adaptive algorithm 510
Density and convergence 512
Properties of the problem and the modules 514
Convergence 516
Problems 524
Adaptivity: Contraction property 525
The modules of AFEM for the model problem 526
Properties of the modules of AFEM 527
Contraction property of AFEM 531
Example: Discontinuous coefficients 533
Problems 535
Adaptivity: Convergence rates 537
Approximation class 538
Cardinality of Mk 543
Quasi-optimal convergence rates 546
Marking vs optimality 547
Problems 551
References 552
Adaptive wavelet methods for solving operator equations: An overview 556
Introduction 556
Non-adaptive methods 556
Adaptive methods 558
Best N-term approximation and approximation classes 559
Structure of the paper 560
Some properties of the (quasi-) norms ||.||As 560
Well-posed linear operator equations 562
Reformulation as a bi-infinite matrix vector equation 562
Some model examples 563
Adaptive wavelet schemes I: Inexact Richardson iteration 565
Richardson iteration 565
Practical scheme 566
The routines COARSE and APPLY 571
Non-coercive B 575
Alternatives for the Richardson iteration 577
Adaptive wavelet schemes II: The Adaptive wavelet-Galerkin method 578
The adaptive wavelet-Galerkin method (AWGM) in a idealized setting 578
Practical scheme 581
Discussion 587
The approximation of operators in wavelet coordinates by computable sparse matrices 587
Near-sparsity of partial differential operators in wavelet coordinates 588
The approximate computation of the significant entries 593
Trees 596
Adaptive frame methods 598
Introduction 598
Frames 598
The adaptive solution of an operator equation in frame coordinates 599
An adaptive Schwarz method for aggregated wavelet frames 601
Adaptive methods based on tensor product wavelet bases 603
Tensor product wavelets 603
Non-adaptive approximation 603
Best N-term approximation and regularity 604
s-computability 605
Truly sparse stiffness matrices 605
Problems in space high dimension 605
Non-product domains 606
Other, non-elliptic problems 607
References 607
Optimal multilevel methods for H(grad), H(curl), and H(div) systems on graded and unstructured grids 611
Introduction 611
The method of subspace corrections 613
Iterative methods 614
Space decomposition and method of subspace correction 616
Sharp convergence identities 619
Multilevel methods on quasi-uniform grids 621
Finite element methods 621
Multilevel space decomposition and multigrid method 623
Stable decomposition and optimality of BPX preconditioner 624
Uniform convergence of V-cycle multigrid 628
Systems with strongly discontinuous coefficients 630
Multilevel methods on graded grids 633
Bisection methods 634
Compatible bisections 636
Decomposition of bisection grids 637
Generation of compatible bisections 639
Node-oriented coarsening algorithm 641
Space decomposition on bisection grids 642
Strengthened Cauchy-Schwarz inequality 646
BPX preconditioner and multigrid on graded bisection grids 648
Multilevel methods for H(curl) and H(div) systems 648
Preliminaries 650
Space decomposition and multigrid methods 658
Stable decomposition 660
The auxiliary space method and HX preconditioner for unstructured grids 663
The auxiliary space method 663
HX preconditioner 665
References 667