Reduced Basis Method - How to Best Sample the Solution Manifold? Wolfgang Dahmen Institut fur ¨ Geometrie und Praktische Mathematik RWTH Aachen joint work with: Christian Plesken, Gerrit Welper W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 1 / 29 Outline Outline 1 Introduction W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Outline Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Outline Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Outline Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Outline Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Outline Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation 6 Summary and Outlook W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 2 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Parameter dependent family of PDEs: F (u, µ) = 0, µ ∈ P, u(x, µ) Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Parameter dependent family of PDEs: F (u, µ) = 0, µ ∈ P, online parameter optimization: I(µ) u(x, µ) → opt Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Parameter dependent family of PDEs: F (u, µ) = 0, µ ∈ P, u(x, µ) online parameter optimization: I(µ) = `(u(µ)) → opt is practically infeasible Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization ⇒ Navier-Stokes equations in “homogenized” domain Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Parameter dependent family of PDEs: F (u, µ) = 0, µ ∈ P, u(x, µ) online parameter optimization: I(µ) = `(u(µ)) → opt is practically infeasible Model reduction needed... Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Background...Turbulent Drag Reduction - FOR 1779 Turbulence modeling Geometric homogenization Navier-Stokes equations in “homogenized” domain ⇒ Robin-type effective boundary conditions depending on frequency, amplitude,...= µ Parameter dependent family of PDEs: F (u, µ) = 0, µ ∈ P, u(x, µ) online parameter optimization: I(µ) = `(u(µ)) → opt is practically infeasible Model reduction needed... u(x, µ) ≈ Pm j=1 cj (µ)u(x, µj ) RBM Central methodological topic in AICES Aachen Institute for Advanced Study in Computational Engineering Science W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 3 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 4 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems Classical techniques do not work well for indefinite, singularly perturbed, unsymmetric ... transport dominated problems W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 4 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems Classical techniques do not work well for indefinite, singularly perturbed, unsymmetric ... transport dominated problems Guiding examples: Convection-diffusion-reaction: −∆u + b(µ) · ∇u + cu = f W. Dahmen (RWTH Aachen) in Ω, u |∂Ω = 0, µ ∈ P How to Best Sample a Solution Manifold? July 2, 2013 4 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems Classical techniques do not work well for indefinite, singularly perturbed, unsymmetric ... transport dominated problems Guiding examples: Convection-diffusion-reaction: −∆u + b(µ) · ∇u + cu = f in Ω, u |∂Ω = 0, µ ∈ P Transport/kinetic models: b(µ) · ∇u(µ) + cu(µ) = f W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? in Ω, u |Γ− =0 July 2, 2013 4 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems Classical techniques do not work well for indefinite, singularly perturbed, unsymmetric ... transport dominated problems Guiding examples: Convection-diffusion-reaction: −∆u + b(µ) · ∇u + cu = f in Ω, u |∂Ω = 0, µ ∈ P Transport/kinetic models: b(µ) · ∇u(µ) + cu(µ) = f + W. Dahmen (RWTH Aachen) Z K (µ, µ0 )u(µ0 )dµ0 P How to Best Sample a Solution Manifold? in Ω, u |Γ− =0 July 2, 2013 4 / 29 Introduction Where do we Stand? RBMs well understood for elliptic problems Classical techniques do not work well for indefinite, singularly perturbed, unsymmetric ... transport dominated problems Guiding examples: Convection-diffusion-reaction: −∆u + b(µ) · ∇u + cu = f in Ω, u |∂Ω = 0, µ ∈ P Transport/kinetic models: b(µ) · ∇u(µ) + cu(µ) = f + Z K (µ, µ0 )u(µ0 )dµ0 P in Ω, u |Γ− =0 Nonlinear conservation laws: ∂t u + ∇ · f (u, µ) = 0 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 4 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P Global coupling - collision operators W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P Global coupling - collision operators High-dimensional parameter space P W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P Global coupling - collision operators High-dimensional parameter space P Nonlinearities W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P Global coupling - collision operators High-dimensional parameter space P Nonlinearities Here: Best-sampling for non-elliptic problems find smallest possible reduced models ! W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction Challenges... Lack of stabilizing viscosity - pure Galerkin does not work! Non-smooth dependence on µ ∈ P Global coupling - collision operators High-dimensional parameter space P Nonlinearities Here: Best-sampling for non-elliptic problems find smallest possible reduced models ! ...in a rigorous sense! W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 5 / 29 Introduction General Philosophy Offline mode: precompute a “reduced basis” consisting of suitable solution samples W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 6 / 29 Introduction General Philosophy Offline mode: precompute a “reduced basis” consisting of suitable solution samples heavy computational cost in the “truth space” X M u(x, µj ) W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 6 / 29 Introduction General Philosophy Offline mode: precompute a “reduced basis” consisting of suitable solution samples heavy computational cost in the “truth space” Online mode: for each parameter query solve only a small reduced system X M Pn j=1 W. Dahmen (RWTH Aachen) cj (µ)u(x, µj ) How to Best Sample a Solution Manifold? July 2, 2013 6 / 29 Introduction General Philosophy Offline mode: precompute a “reduced basis” consisting of suitable solution samples heavy computational cost in the “truth space” Online mode: for each parameter query solve only a small reduced system - with certified accuracy X M Pn j=1 W. Dahmen (RWTH Aachen) cj (µ)u(x, µj ) ≈ u(x, µ) How to Best Sample a Solution Manifold? July 2, 2013 6 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? in Ω, u = 0 on ∂Ω, July 2, 2013 7 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), Find u ∈ H01 (Ω) Z Z fv dx , Ω Ω W. Dahmen (RWTH Aachen) u = 0 on ∂Ω, such that ∇u · ∇v + (b(µ) · ∇u)v + cuv dx = | in Ω, {z } v ∈ H01 (Ω) | {z } | {z } How to Best Sample a Solution Manifold? July 2, 2013 7 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), in Ω, u = 0 on ∂Ω, Find u ∈ H01 (Ω) =: X such that Z ∇u · ∇v + (b(µ) · ∇u)v + cuv dx = W. Dahmen (RWTH Aachen) fv dx , Ω Ω | Z {z =:bµ (u,v ) } v ∈ H01 (Ω) | {z } =:Y | {z } =:hf ,v i How to Best Sample a Solution Manifold? July 2, 2013 7 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), in Ω, u = 0 on ∂Ω, Find u ∈ H01 (Ω) =: X such that Z ∇u · ∇v + (b(µ) · ∇u)v + cuv dx = Z fv dx , Ω Ω | {z =:bµ (u,v ) } v ∈ H01 (Ω) | {z } =:Y | {z } =:hf ,v i hB µ u(µ), v i := bµ (u(µ), v ) W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 7 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), in Ω, u = 0 on ∂Ω, Find u ∈ H01 (Ω) =: X such that Z ∇u · ∇v + (b(µ) · ∇u)v + cuv dx = Z fv dx , Ω Ω | {z =:bµ (u,v ) hB µ u(µ), v i := bµ (u(µ), v ) W. Dahmen (RWTH Aachen) } v ∈ H01 (Ω) | {z } =:Y | {z } =:hf ,v i B µ u(µ) = f , How to Best Sample a Solution Manifold? Bµ : X → Y 0 July 2, 2013 7 / 29 Introduction A Guiding Model Problem - variational formulation Convection-diffusion equation −div(∇u(x)) + b(µ) · ∇u(x) + cu(x) = f (x), in Ω, u = 0 on ∂Ω, Find u ∈ H01 (Ω) =: X such that Z ∇u · ∇v + (b(µ) · ∇u)v + cuv dx = Z fv dx , Ω Ω | {z =:bµ (u,v ) hB µ u(µ), v i := bµ (u(µ), v ) } v ∈ H01 (Ω) | {z } =:Y | {z } =:hf ,v i B µ u(µ) = f , Bµ : X → Y 0 M := {u(µ) = B −1 µ f : µ ∈ P} ⊂ X W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 7 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P bµ (u(µ), v ) = hf , v i, W. Dahmen (RWTH Aachen) v ∈ Y, How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, W. Dahmen (RWTH Aachen) v ∈ Y , ⇔ B µ u(µ) = f , How to Best Sample a Solution Manifold? Bµ : X → Y 0 July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. inf ku(µ) − v kX v ∈Xn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. max inf ku(µ) − v kX =: σn (M)X µ∈P v ∈Xn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. maxdist (M, Xn )X := max inf ku(µ) − v kX =: σn (M)X µ∈P v ∈Xn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. ! maxdist (M, Xn )X := max inf ku(µ) − v kX =: σn (M)X ≤ µ∈P v ∈Xn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. ! maxdist (M, Xn )X := max inf ku(µ) − v kX =: σn (M)X ≤ µ∈P v ∈Xn Surrogate: suppose one has inf ku(µ) − v kX ≤ Rn (µ), v ∈Xn W. Dahmen (RWTH Aachen) µ ∈ P, How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. ! maxdist (M, Xn )X := max inf ku(µ) − v kX =: σn (M)X ≤ µ∈P v ∈Xn Surrogate: suppose one has inf ku(µ) − v kX ≤ Rn (µ), v ∈Xn µ ∈ P, Greedy Algorithm X0 := {0}; W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality The Greedy Paradigm... Y. Maday, A. Patera,... Given f ∈ Y 0 find u ∈ X s.t. for µ ∈ P hB µ u(µ), v i := bµ (u(µ), v ) = hf , v i, Solution manifold: v ∈ Y , ⇔ B µ u(µ) = f , Bµ : X → Y 0 −1 M := {u(µ) := Bµ f : µ ∈ P} Objective: construct Xn ⊂ X , n = n() as small as possible, s.t. ! maxdist (M, Xn )X := max inf ku(µ) − v kX =: σn (M)X ≤ µ∈P v ∈Xn Surrogate: suppose one has inf ku(µ) − v kX ≤ Rn (µ), v ∈Xn µ ∈ P, Greedy Algorithm X0 := {0}; for n = 1, 2, . . ., given Xn−1 µn := argmaxµ∈P Rn−1 (µ), W. Dahmen (RWTH Aachen) Xn := span {Xn−1 , {u(µn )}} How to Best Sample a Solution Manifold? July 2, 2013 8 / 29 The Greedy Paradigm - Rate Optimality How does the greedy search perform?... X W. Dahmen (RWTH Aachen) M How to Best Sample a Solution Manifold? July 2, 2013 9 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: W. Dahmen (RWTH Aachen) (Buffa, Maday, Patera, Prud’homme, Turinici...) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: (Buffa, Maday, Patera, Prud’homme, Turinici...) dist (u, Vn )X W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X u∈M W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := W. Dahmen (RWTH Aachen) inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X dim(Vn )=n u∈M How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := W. Dahmen (RWTH Aachen) inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X ≤ σn (M)X dim(Vn )=n u∈M How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X ≤ σn (M)X dim(Vn )=n u∈M THEOREM 1: Binev/Cohen/Dahmen/DeVore/Petrova/Wojtaszczyk If the surrogate is tight, i.e., ∃ cS independent of µ ∈ P, s.t. cS Rn (µ) ≤ inf ku(µ) − wkX ≤ Rn (µ), w∈Xn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X ≤ σn (M)X dim(Vn )=n u∈M THEOREM 1: Binev/Cohen/Dahmen/DeVore/Petrova/Wojtaszczyk If the surrogate is tight, i.e., ∃ cS independent of µ ∈ P, s.t. cS Rn (µ) ≤ inf ku(µ) − wkX ≤ Rn (µ), w∈Xn then O(n−α ), n ∈ N, dn (M)X = O(e−cnα ), n ∈ N, W. Dahmen (RWTH Aachen) ⇒ O(n−α ), n ∈ N, σn (M)X = O(e−c˜nα ), n ∈ N, How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X ≤ σn (M)X dim(Vn )=n u∈M THEOREM 1: Binev/Cohen/Dahmen/DeVore/Petrova/Wojtaszczyk If the surrogate is tight, i.e., ∃ cS independent of µ ∈ P, s.t. cS Rn (µ) ≤ inf ku(µ) − wkX ≤ Rn (µ), w∈Xn κ(Rn ) ≤ 1/cS then O(n−α ), n ∈ N, dn (M)X = O(e−cnα ), n ∈ N, ⇒ O(n−α ), n ∈ N, σn (M)X = O(e−c˜nα ), n ∈ N, C = C(α, c, κ(Rn )) W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality Rate Optimality Bench mark - Kolmogorov Widths: dn (M)X := inf (Buffa, Maday, Patera, Prud’homme, Turinici...) sup dist (u, Vn )X ≤ σn (M)X dim(Vn )=n u∈M THEOREM 1: Binev/Cohen/Dahmen/DeVore/Petrova/Wojtaszczyk If the surrogate is tight, i.e., ∃ cS independent of µ ∈ P, s.t. cS Rn (µ) ≤ inf ku(µ) − wkX ≤ Rn (µ), w∈Xn κ(Rn ) ≤ 1/cS then O(n−α ), n ∈ N, dn (M)X = O(e−cnα ), n ∈ N, ⇒ O(n−α ), n ∈ N, σn (M)X = O(e−c˜nα ), n ∈ N, C = C(α, c, κ(Rn )) Central goal: find well conditioned feasible surrogates ... W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 10 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have surrogate W. Dahmen (RWTH Aachen) ≈ best approximation error How to Best Sample a Solution Manifold? July 2, 2013 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have f − Bµ un∗ (µ) W. Dahmen (RWTH Aachen) ≈ u(µ) − un∗ (µ) How to Best Sample a Solution Manifold? July 2, 2013 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have kf − Bµ un∗ (µ)kY 0 W. Dahmen (RWTH Aachen) ≈ ku(µ) − un∗ (µ)kX How to Best Sample a Solution Manifold? (1) July 2, 2013 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have kf − Bµ un∗ (µ)kY 0 ≈ ku(µ) − un∗ (µ)kX (1) One must have kbest approximation errorkX ≈ kmethod projection errorkX W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 (2) 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have kf − Bµ un∗ (µ)kY 0 ≈ ku(µ) − un∗ (µ)kX (1) One must have kbest approximation errorkX ≈ kmethod projection errorkX (2) Works well for elliptic problems: X = Y = H01 (Ω) W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 11 / 29 The Greedy Paradigm - Rate Optimality The only Conceivable Way... Surrogate must be based on residuals One must have kf − Bµ un∗ (µ)kY 0 ≈ ku(µ) − un∗ (µ)kX (1) One must have kbest approximation errorkX ≈ kmethod projection errorkX (2) Works well for elliptic problems: X = Y = H01 (Ω) Idea: find suitable (X , Y )-stable variational formulation of the problem to ensure (3), (4) W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 11 / 29 Finding Good Projections Renormation Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation 6 Summary and Outlook W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 12 / 29 Finding Good Projections Renormation Renormation...Dahmen/Huang/Schwab/Welper, Demkowicz et al., Cai et al, Manteuffel et al..... Suppose Bµ u(µ) = f is well-posed, i.e.: inf sup u∈Xµ v ∈Yµ bµ (u, v ) ≥ β(µ), kukXµ kv kYµ W. Dahmen (RWTH Aachen) sup sup u∈Xµ v ∈Yµ |bµ (u, v )| ≤ Cb (µ) kukXµ kv kYµ How to Best Sample a Solution Manifold? July 2, 2013 13 / 29 Finding Good Projections Renormation Renormation...Dahmen/Huang/Schwab/Welper, Demkowicz et al., Cai et al, Manteuffel et al..... Suppose Bµ u(µ) = f is well-posed, i.e.: inf sup u∈Xµ v ∈Yµ bµ (u, v ) ≥ β(µ), kukXµ kv kYµ sup sup u∈Xµ v ∈Yµ |bµ (u, v )| ≤ Cb (µ) kukXµ kv kYµ Re-define k · kXˆµ through (see also Nguyen/Patera/Rozza, Deparis, but 6=) kukXˆµ := sup v ∈Yµ bµ (u, v ) kv kYµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? u ∈ Xµ , µ ∈ P July 2, 2013 13 / 29 Finding Good Projections Renormation Renormation...Dahmen/Huang/Schwab/Welper, Demkowicz et al., Cai et al, Manteuffel et al..... Suppose Bµ u(µ) = f is well-posed, i.e.: inf sup u∈Xµ v ∈Yµ bµ (u, v ) ≥ β(µ), kukXµ kv kYµ sup sup u∈Xµ v ∈Yµ |bµ (u, v )| ≤ Cb (µ) kukXµ kv kYµ Re-define k · kXˆµ through (see also Nguyen/Patera/Rozza, Deparis, but 6=) kukXˆµ := sup v ∈Yµ bµ (u, v ) = kBµ ukYµ0 = kRY−1 Bµ ukYµ , µ kv kYµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? u ∈ Xµ , µ ∈ P July 2, 2013 13 / 29 Finding Good Projections Renormation Renormation...Dahmen/Huang/Schwab/Welper, Demkowicz et al., Cai et al, Manteuffel et al..... Suppose Bµ u(µ) = f is well-posed, i.e.: inf sup u∈Xµ v ∈Yµ bµ (u, v ) ≥ β(µ), kukXµ kv kYµ κXµ →Yµ0 (Bµ ) ≤ Cb (µ)/β(µ) sup sup u∈Xµ v ∈Yµ |bµ (u, v )| ≤ Cb (µ) kukXµ kv kYµ Re-define k · kXˆµ through (see also Nguyen/Patera/Rozza, Deparis, but 6=) kukXˆµ := sup v ∈Yµ bµ (u, v ) = kBµ ukYµ0 = kRY−1 Bµ ukYµ , µ kv kYµ u ∈ Xµ , µ ∈ P Perfect Condition: sup sup v ∈Xµ y ∈Yµ bµ (v , y) bµ (v , y ) = inf sup = 1, v ∈Xµ y∈Yµ kykYµ kv kX ky kYµ kv kXˆµ ˆµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? ⇒ κXˆµ →Y 0 (Bµ ) = 1 µ July 2, 2013 13 / 29 Finding Good Projections Renormation Renormation...Dahmen/Huang/Schwab/Welper, Demkowicz et al., Cai et al, Manteuffel et al..... Suppose Bµ u(µ) = f is well-posed, i.e.: inf sup u∈Xµ v ∈Yµ bµ (u, v ) ≥ β(µ), kukXµ kv kYµ κXµ →Yµ0 (Bµ ) ≤ Cb (µ)/β(µ) sup sup u∈Xµ v ∈Yµ |bµ (u, v )| ≤ Cb (µ) kukXµ kv kYµ Re-define k · kXˆµ through (see also Nguyen/Patera/Rozza, Deparis, but 6=) kukXˆµ := sup v ∈Yµ bµ (u, v ) = kBµ ukYµ0 = kRY−1 Bµ ukYµ , µ kv kYµ u ∈ Xµ , µ ∈ P Perfect Condition: sup sup v ∈Xµ y ∈Yµ bµ (v , y) bµ (v , y ) = inf sup = 1, v ∈Xµ y∈Yµ kykYµ kv kX ky kYµ kv kXˆµ ˆµ ⇒ κXˆµ →Y 0 (Bµ ) = 1 µ ...How to use this numerically? W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 13 / 29 Finding Good Projections A Saddle Point Formulation Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation 6 Summary and Outlook W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 14 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , bµ (un (µ), v ) = hf , v i, v ∈ Vn , W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 15 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , yn (µ) ∈ Vn ⊂ Yµ (yn (µ) ≈ f − Bµ un (µ)) solve: (yn (µ), v )Yµ + bµ (un (µ), v ) = hf , v i, v ∈ Vn , bµ (w, yn (µ)) W. Dahmen (RWTH Aachen) = 0, How to Best Sample a Solution Manifold? w ∈ Xn , July 2, 2013 15 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , yn (µ) ∈ Vn ⊂ Yµ (yn (µ) ≈ f − Bµ un (µ)) solve: (yn (µ), v )Yµ + bµ (un (µ), v ) = hf , v i, v ∈ Vn , bµ (w, yn (µ)) = 0, w ∈ Xn , if and only if bµ (un (µ), v ) = hf , v i, W. Dahmen (RWTH Aachen) ∀ v ∈ Yn := PYµ ,Vn (RY−1 Bµ (Xn )) µ How to Best Sample a Solution Manifold? July 2, 2013 15 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , yn (µ) ∈ Vn ⊂ Yµ (yn (µ) ≈ f − Bµ un (µ)) solve: (yn (µ), v )Yµ + bµ (un (µ), v ) = hf , v i, v ∈ Vn , bµ (w, yn (µ)) = 0, w ∈ Xn , if and only if bµ (un (µ), v ) = hf , v i, Moreover inf sup w∈Xn v ∈Vn W. Dahmen (RWTH Aachen) ∀ v ∈ Yn := PYµ ,Vn (RY−1 Bµ (Xn )) µ p bµ (w, v ) ≥ 1 − δ2 kwkXˆµ kv kYµ How to Best Sample a Solution Manifold? July 2, 2013 15 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , yn (µ) ∈ Vn ⊂ Yµ (yn (µ) ≈ f − Bµ un (µ)) solve: (yn (µ), v )Yµ + bµ (un (µ), v ) = hf , v i, v ∈ Vn , bµ (w, yn (µ)) = 0, w ∈ Xn , if and only if bµ (un (µ), v ) = hf , v i, Moreover inf sup w∈Xn v ∈Vn ∀ v ∈ Yn := PYµ ,Vn (RY−1 Bµ (Xn )) µ p bµ (w, v ) ≥ 1 − δ2 kwkXˆµ kv kYµ if and only if sup inf kRY−1 Bµ w − φkYµ ≤ δkwkXˆµ µ w∈Xn φ∈Vn W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 15 / 29 Finding Good Projections A Saddle Point Formulation Main Result un (µ) ∈ Xn ⊂ Xµ , yn (µ) ∈ Vn ⊂ Yµ (yn (µ) ≈ f − Bµ un (µ)) solve: (yn (µ), v )Yµ + bµ (un (µ), v ) = hf , v i, v ∈ Vn , bµ (w, yn (µ)) = 0, w ∈ Xn , if and only if bµ (un (µ), v ) = hf , v i, Moreover inf sup w∈Xn v ∈Vn ∀ v ∈ Yn := PYµ ,Vn (RY−1 Bµ (Xn )) µ p bµ (w, v ) ≥ 1 − δ2 kwkXˆµ kv kYµ if and only if sup inf kRY−1 Bµ w − φkYµ ≤ δkwkXˆµ µ w∈Xn φ∈Vn ⇒ ku(µ) − un (µ)kXˆµ + kyn (µ)kYµ ≤ W. Dahmen (RWTH Aachen) 2 inf ku(µ) − wkXˆµ 1 − δ w∈Xn How to Best Sample a Solution Manifold? July 2, 2013 15 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn W. Dahmen (RWTH Aachen) bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem T truth-independent termination even when Yµ 6= Y := µ∈P Yµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem T truth-independent termination even when Yµ 6= Y := µ∈P Yµ stabilization residual based surrogate Rn (µ) := kf − Bµ un (µ)kYN0 is tight with a small µ-independent condition W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem T truth-independent termination even when Yµ 6= Y := µ∈P Yµ stabilization residual based surrogate Rn (µ) := kf − Bµ un (µ)kYN0 is tight with a small µ-independent condition SP-Galerkin projection ∼ best approximation W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem T truth-independent termination even when Yµ 6= Y := µ∈P Yµ stabilization residual based surrogate Rn (µ) := kf − Bµ un (µ)kYN0 is tight with a small µ-independent condition SP-Galerkin projection ∼ best approximation grow Xn → Xn+1 by outer greedy step W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Double Greedy Scheme Double Greedy Scheme: (Xn , Vn ) → (Xn+1 , Vn+1 ) stabilize: given Xn , generate inf-sup stable test space Vn - independent of µ - through a greedy inner loop (see Gerner/Veroy for Stokes) ¯ = argminµ∈P,w∈X sup (µ, ¯ w) n v ∈Vn bµ (w, v ) kv kYµ kwkXˆ −1 ¯ Vn → [Vn , v¯ ] v¯ = RY Bµ ¯ w, µ ¯ µ each µ-query requires only solving a small n-dimensional eigenvalue problem T truth-independent termination even when Yµ 6= Y := µ∈P Yµ stabilization residual based surrogate Rn (µ) := kf − Bµ un (µ)kYN0 is tight with a small µ-independent condition SP-Galerkin projection ∼ best approximation grow Xn → Xn+1 by outer greedy step Theorem: ... The scheme is rate-optimal with surrogate condition close to one W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 16 / 29 Numerical Experiments Convection-Diffusion Equations Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation 6 Summary and Outlook W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 17 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations cos µ · ∇u + u = 1, in Ω = (0, 1)2 , −∆u + sin µ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? u = 0, on ∂Ω July 2, 2013 18 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations cos µ · ∇u + u = 1, in Ω = (0, 1)2 , −∆u + sin µ u = 0, on ∂Ω Choice of the test norm: 1 hBµ u, v i + hBµ v , ui , 2 1/2 2 1 v := sµ (v , v ) = |v |2H 1 (Ω) + c − div b(µ) 2 L2 (Ω) sµ (u, v ) := kv k2Yµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 18 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations cos µ · ∇u + u = 1, in Ω = (0, 1)2 , −∆u + sin µ u = 0, on ∂Ω Choice of the test norm: 1 hBµ u, v i + hBµ v , ui , 2 1/2 2 1 v := sµ (v , v ) = |v |2H 1 (Ω) + c − div b(µ) 2 L2 (Ω) sµ (u, v ) := kv k2Yµ + boundary penalization at outflow boundary: (see Cohen/Dahmen/Welper, M2AN 2012) ¯ µ uk2¯ 0 = kB ¯ µ uk2 0 + λkuk2 kuk2X¯µ := kB Yµ Hb (µ) Y µ 1/2 ¯µ := Yµ × Hb (µ)0 Hb (µ) = H00 (Γ+ (µ)), Y W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 18 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations cos µ · ∇u + u = 1, in Ω = (0, 1)2 , −∆u + sin µ u = 0, on ∂Ω Choice of the test norm: 1 hBµ u, v i + hBµ v , ui , 2 1/2 2 1 v := sµ (v , v ) = |v |2H 1 (Ω) + c − div b(µ) 2 L2 (Ω) sµ (u, v ) := kv k2Yµ + boundary penalization at outflow boundary: (see Cohen/Dahmen/Welper, M2AN 2012) ¯ µ uk2¯ 0 = kB ¯ µ uk2 0 + λkuk2 kuk2X¯µ := kB Yµ Hb (µ) Y µ 1/2 ¯µ := Yµ × Hb (µ)0 Hb (µ) = H00 (Γ+ (µ)), Y ¯ µ w − f k2¯ 0 + λkγwk2 u(µ) = argminw∈X− kB Hb (µ) Y µ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 18 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations (a) = 2−5 RB dim n = 6, m(n) = 13, angle µ = 0.885115, (b) = 2−7 RB dim n = 7, m(n) = 20, angle µ = 0.257484, (c) = 2−26 RB dim n = 20, m(n) = 57, angle µ = 0.587137 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 19 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations = 2−5 = 2−7 = 2−26 0.12 6 · 10−2 0.15 8 · 10−2 4 · 10−2 6 · 10−2 0.1 4 · 10−2 2 · 10−2 0 0.2 0.1 5 · 10−2 2 · 10−2 2 3 4 5 reduced basis trial dimension W. Dahmen (RWTH Aachen) 6 0 2 3 4 5 6 7 reduced basis trial dimension How to Best Sample a Solution Manifold? 0 5 10 15 20 reduced basis trial dimension July 2, 2013 20 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations: = 2−5 a-post. error 0.0057 dim trial dim test δ max surr surr/a-post 2 3 2.51e-01 7.04e-02 1.24e+01 3 6 3.74e-01 3.08e-02 5.40e+00 4 7 3.74e-01 7.43e-03 1.30e+00 5 10 3.51e-01 5.81e-03 1.02e+00 6 13 1.86e-01 5.70e-03 1.00e+00 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 21 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations: = 2−7 a-post. error 0.0197 dim trial dim test δ max surr surr/a-post 2 5 8.92e-03 1.25e-01 6.37e+00 3 8 1.22e-01 9.65e-02 4.90e+00 4 11 1.13e-02 3.21e-02 1.63e+00 5 14 1.27e-02 2.61e-02 1.32e+00 6 17 5.55e-03 2.21e-02 1.12e+00 7 20 4.82e-03 1.97e-02 1.00e+00 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 22 / 29 Numerical Experiments Convection-Diffusion Equations Convection-Diffusion Equations: = 2−26 a-post. error 0.0011 trial test δ surrogate a-post trial test δ surrogate surr/a-post 2 5 1.35e-03 2.11e-01 2.00e+02 12 33 3.47e-04 1.60e-02 1.52e+01 4 9 1.09e-02 7.58e-02 7.19e+01 14 39 1.10e-04 8.46e-03 8.02e+00 6 15 1.61e-03 5.02e-02 4.76e+01 16 45 9.39e-05 7.87e-03 7.46e+00 8 21 7.99e-04 2.39e-02 2.26e+01 18 51 6.11e-05 7.69e-03 7.29e+00 10 27 3.55e-04 2.10e-02 2.00e+01 20 57 5.28e-05 6.35e-03 6.02e+00 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 23 / 29 Numerical Experiments Transport Equation Outline 1 Introduction 2 The Greedy Paradigm - Rate Optimality 3 Finding Good Projections - Stable Variational Formulations Renormation A Saddle Point Formulation 4 Double Greedy Scheme 5 Numerical Experiments Convection-Diffusion Equations Transport Equation 6 Summary and Outlook W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 24 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation (1) Homogeneous B.C.s: cos µ · ∇u + u = 1, in Ω = (0, 1)2 , sin µ W. Dahmen (RWTH Aachen) u = 0, on Γ− (µ) How to Best Sample a Solution Manifold? July 2, 2013 25 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation (1) Homogeneous B.C.s: cos µ · ∇u + u = 1, in Ω = (0, 1)2 , sin µ u = 0, on Γ− (µ) (2) Discontinuous boundary data: 0.5 cos µ ·∇u+u = 1 sin µ W. Dahmen (RWTH Aachen) x <y , x ≥y 1−y u= 0 How to Best Sample a Solution Manifold? x ≤ 0.5 , x > 0.5 on Γ− (µ) July 2, 2013 25 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation (1) Homogeneous B.C.s: cos µ · ∇u + u = 1, in Ω = (0, 1)2 , sin µ u = 0, on Γ− (µ) (2) Discontinuous boundary data: 0.5 cos µ ·∇u+u = 1 sin µ x <y , x ≥y kv kYµ = kBµ∗ v kL2 (Ω) , 1−y u= 0 x ≤ 0.5 , x > 0.5 on Γ− (µ) k · kXˆµ = k · kL2 (Ω) , i.e. RYµ = Bµ Bµ∗ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 25 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation Figure: (1): reduced basis of dimension n = 24, m(n) = 91, angle µ = 0.244579 W. Dahmen (RWTH Aachen) Figure: (2): reduced basis of dimension n = 24, m(n) = 96, angle µ = 0.256311 How to Best Sample a Solution Manifold? July 2, 2013 26 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation: Convergence jump boundary zero boundary 6 · 10−2 1.2 · 10−2 1 · 10−2 4 · 10−2 8 · 10−3 6 · 10−3 2 · 10−2 4 · 10−3 2 · 10−3 0 5 10 15 20 reduced basis trial dimension W. Dahmen (RWTH Aachen) 25 0 5 10 15 20 25 reduced basis trial dimension How to Best Sample a Solution Manifold? July 2, 2013 27 / 29 Numerical Experiments Transport Equation (Pure) Transport Equation (2): truth L2 -error 0.0154 trial test δ surr rb truth rb L2 surr/err 4 14 4.97e-01 5.91e-02 1.29e-01 1.30e-01 4.54e-01 8 31 4.29e-01 4.34e-02 7.78e-02 7.95e-02 5.46e-01 12 49 3.71e-01 3.48e-02 7.40e-02 7.53e-02 4.63e-01 16 64 3.74e-01 2.99e-02 6.20e-02 6.41e-02 4.67e-01 20 81 3.73e-01 2.71e-02 5.46e-02 5.62e-02 4.82e-01 24 96 3.91e-01 2.51e-02 4.51e-02 4.79e-02 5.25e-01 1 cycle of iterative tightening: trial test δ surr rb truth rb L2 surr/err 20 81 3.73e-01 2.71e-02 5.46e-02 5.62e-02 4.82e-01 10 87 3.51e-01 6.45e-02 7.40e-02 7.53e-02 8.57e-01 W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 28 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes iterative tightening restores efficient offline-online procedures for Y 6= Yµ W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes iterative tightening restores efficient offline-online procedures for Y 6= Yµ low smoothness w.r.t. the parameters in the pure transport case ... ...limitation of RBMs... W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes iterative tightening restores efficient offline-online procedures for Y 6= Yµ low smoothness w.r.t. the parameters in the pure transport case ... ...limitation of RBMs... In progress: High-dimensional (empirical) interpolation - compressed sensing W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes iterative tightening restores efficient offline-online procedures for Y 6= Yµ low smoothness w.r.t. the parameters in the pure transport case ... ...limitation of RBMs... In progress: High-dimensional (empirical) interpolation - compressed sensing reparametrizations W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29 Summary Summary and Outlook Reference: W. Dahmen, C. Plesken, G. Welper, Double Greedy Algorithms: Reduced Basis Methods for Transport Dominated Problems, ESAIM: Mathematical Modelling and Numerical Analysis, 48(3) (2014), 623–663. works the same for space-time formulations applies to “classical saddle point problems” as well, see Gerner/Veroy, Rozza in principle, stability constants can be driven as close to one as one wishes iterative tightening restores efficient offline-online procedures for Y 6= Yµ low smoothness w.r.t. the parameters in the pure transport case ... ...limitation of RBMs... In progress: High-dimensional (empirical) interpolation - compressed sensing reparametrizations Relaxation W. Dahmen (RWTH Aachen) How to Best Sample a Solution Manifold? July 2, 2013 29 / 29

© Copyright 2020