Volume

Dagstuhl Seminar Proceedings, Volume 4401

Publication Details

  • published at: 2005-04-19
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.04401.1
04401 Abstracts Collection – Algorithms and Complexity for Continuous

Authors: Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub

Abstract
From 26.09.04 to 01.10.04, the Dagstuhl Seminar ``Algorithms and Complexity for Continuous Problems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub. 04401 Abstracts Collection – Algorithms and Complexity for Continuous. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{mullergronbach_et_al:DagSemProc.04401.1,
  author =	{M\"{u}ller-Gronbach, Thomas and Novak, Erich and Petras, Knut and Traub, Joseph F.},
  title =	{{04401 Abstracts Collection – Algorithms and Complexity for Continuous}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.1},
  URN =		{urn:nbn:de:0030-drops-1545},
  doi =		{10.4230/DagSemProc.04401.1},
  annote =	{Keywords: Complexity and regularization of ill-posed problems , nonlinear approximation , tractability of high-dimensional numerical problems quantum computing , stochastic computation and quantization , global optimization , differential and integral equations}
}
Document
DOI: 10.4230/DagSemProc.04401.2
04401 Summary – Algorithms and Complexity for Continuous Problems

Authors: Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub

Abstract
The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.
Cite as

Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub. 04401 Summary – Algorithms and Complexity for Continuous Problems. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{mullergronbach_et_al:DagSemProc.04401.2,
  author =	{M\"{u}ller-Gronbach, Thomas and Novak, Erich and Petras, Knut and Traub, Joseph F.},
  title =	{{04401 Summary – Algorithms and Complexity for Continuous Problems}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.2},
  URN =		{urn:nbn:de:0030-drops-1530},
  doi =		{10.4230/DagSemProc.04401.2},
  annote =	{Keywords: Complexity and Regularization of Ill-Posed Problems , Non-Linear Approximation , Tractability of High-Dimensional Numerical Problems Quasi-Monte Carlo Methods , Quantum Computing , Stochastic Computation and Quantization , Global Optimization , Differential and Integral Equation}
}
Document
DOI: 10.4230/DagSemProc.04401.3
Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II)

Authors: Dirk Nuyens and Ronald Cools

Abstract
Part I: (this part of the talk by Ronald Cools) We restate our previous result which showed that it is possible to construct the generating vector of a rank-1 lattice rule in a fast way, i.e. O(s n log(n)), with s the number of dimensions and n the number of points assumed to be prime. Here we explicitly use basic facts from algebra to exploit the structure of a matrix – which introduces the crucial cost in the construction – to get a matrix-vector multiplication in time O(n log(n)) instead of O(n^2). We again stress the fact that the algorithm works for any tensor product reproducing kernel Hilbert space. Part II: (this part of the talk by Dirk Nuyens) In the second part we generalize the tricks used for primes to non-primes, by basically falling back to algebraic group theory. In this way it can be shown that also for a non-prime number of points, this crucial matrix-vector multiplication can be done in time O(n log(n)). We conclude that the construction of rank-1 lattice rules in an arbitrary r.k.h.s. for an arbitrary amount of points can be done in a fast way of O(s n log(n)).
Cite as

Dirk Nuyens and Ronald Cools. Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II). In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{nuyens_et_al:DagSemProc.04401.3,
  author =	{Nuyens, Dirk and Cools, Ronald},
  title =	{{Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II)}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--26},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.3},
  URN =		{urn:nbn:de:0030-drops-1486},
  doi =		{10.4230/DagSemProc.04401.3},
  annote =	{Keywords: numerical integration , cubature/quadrature , rank-1 lattice , component-by-component construction , fast algorithm}
}
Document
DOI: 10.4230/DagSemProc.04401.4
Functional Quantization and Entropy for Stochastic Processes

Authors: Harald Luschgy and Gilles Pagès

Abstract
Let X be a Gaussian process and let U denote the Strassen ball of X. A precise link between the L^2-quantization error of X and the Kolmogorov (metric) entropy of U in a Hilbert space setting is established. In particular, the sharp asymptotics of the Kolmogorov entropy problem is derived. The condition imposed is regular variation of the eigenvalues of the covariance operator. Good computable quantizers for Gaussian and diffusion processes and their numerical efficieny are discussed. This is joint work with G. Pagès, Université de Paris 6.
Cite as

Harald Luschgy and Gilles Pagès. Functional Quantization and Entropy for Stochastic Processes. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{luschgy_et_al:DagSemProc.04401.4,
  author =	{Luschgy, Harald and Pag\`{e}s, Gilles},
  title =	{{Functional Quantization and Entropy for Stochastic Processes}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.4},
  URN =		{urn:nbn:de:0030-drops-1446},
  doi =		{10.4230/DagSemProc.04401.4},
  annote =	{Keywords: Functional quantization , entropy , product quantizers}
}
Document
DOI: 10.4230/DagSemProc.04401.5
Information-Based Nonlinear Approximation: An Average Case Setting

Authors: Leszek Plaskota

Abstract
Nonlinear approximation has usually been studied under deterministic assumption and complete information about the underlying functions. We assume only partial information and we are interested in the average case error and complexity of approximation. It turns out that the problem can be essentially split into two independent problems related to average case nonlinear (restricted) approximation from complete information, and average case unrestricted approximation from partial information. The results are then applied to average case piecewise polynomial approximation, and to average case approximation of real sequences.
Cite as

Leszek Plaskota. Information-Based Nonlinear Approximation: An Average Case Setting. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{plaskota:DagSemProc.04401.5,
  author =	{Plaskota, Leszek},
  title =	{{Information-Based Nonlinear Approximation: An Average Case Setting}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.5},
  URN =		{urn:nbn:de:0030-drops-1504},
  doi =		{10.4230/DagSemProc.04401.5},
  annote =	{Keywords: average case setting , nonlinear approximation , information-based comlexity}
}
Document
DOI: 10.4230/DagSemProc.04401.6
Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations

Authors: Klaus Ritter and Thomas Müller-Gronbach

Abstract
We study algorithms for approximation of the mild solution of stochastic heat equations on the spatial domain ]0,1[^d. The error of an algorithm is defined in L_2-sense. We derive lower bounds for the error of every algorithm that uses a total of N evaluations of one-dimensional components of the driving Wiener process W. For equations with additive noise we derive matching upper bounds and we construct asymptotically optimal algorithms. The error bounds depend on N and d, and on the decay of eigenvalues of the covariance of W in the case of nuclear noise. In the latter case the use of non-uniform time discretizations is crucial.
Cite as

Klaus Ritter and Thomas Müller-Gronbach. Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ritter_et_al:DagSemProc.04401.6,
  author =	{Ritter, Klaus and M\"{u}ller-Gronbach, Thomas},
  title =	{{Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--37},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.6},
  URN =		{urn:nbn:de:0030-drops-1518},
  doi =		{10.4230/DagSemProc.04401.6},
  annote =	{Keywords: Stochastic heat equation , Non-uniform time discretization , minimal errors , upper and lower bounds}
}
Document
DOI: 10.4230/DagSemProc.04401.7
Monte Carlo solution for the Poisson equation on the base of spherical processes with shifted centres

Authors: Nina Golyandina

Abstract
We consider a class of spherical processes rapidly converging to the boundary (so called Decentred Random Walks on Spheres or spherical processes with shifted centres) in comparison with the standard walk on spheres. The aim is to compare costs of the corresponding Monte Carlo estimates for the Poisson equation. Generally, these costs depend on the cost of simulation of one trajectory and on the variance of the estimate. It can be proved that for the Laplace equation the limit variance of the estimation doesn't depend on the kind of spherical processes. Thus we have very effective estimator based on the decentred random walk on spheres. As for the Poisson equation, it can be shown that the variance is bounded by a constant independent of the kind of spherical processes (in standard form or with shifted centres). We use simulation for a simple model example to investigate variance behavior in more details.
Cite as

Nina Golyandina. Monte Carlo solution for the Poisson equation on the base of spherical processes with shifted centres. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{golyandina:DagSemProc.04401.7,
  author =	{Golyandina, Nina},
  title =	{{Monte Carlo solution for the Poisson equation on the base of spherical processes with shifted centres}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.7},
  URN =		{urn:nbn:de:0030-drops-1393},
  doi =		{10.4230/DagSemProc.04401.7},
  annote =	{Keywords: Poisson equation , Laplace operator , Monte Carlo solution , spherical process , random walk on spheres , rate of convergence}
}
Document
DOI: 10.4230/DagSemProc.04401.8
Numerical Approximation of Parabolic Stochastic Partial Differential Equations

Authors: Erika Hausenblas

Abstract
The topic of the talk were the time approximation of quasi linear stochastic partial differential equations of parabolic type. The framework were in the setting of stochastic evolution equations. An error bounds for the implicit Euler scheme was given and the stability of the scheme were considered.
Cite as

Erika Hausenblas. Numerical Approximation of Parabolic Stochastic Partial Differential Equations. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{hausenblas:DagSemProc.04401.8,
  author =	{Hausenblas, Erika},
  title =	{{Numerical Approximation of Parabolic Stochastic Partial Differential Equations}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.8},
  URN =		{urn:nbn:de:0030-drops-1417},
  doi =		{10.4230/DagSemProc.04401.8},
  annote =	{Keywords: Stochastic Partial Differential Equations , Stochastic evolution Equations , Numerical Approximation , implicit Euler scheme}
}
Document
DOI: 10.4230/DagSemProc.04401.9
On the Complexity of Computing Multi-Homogeneous Bézout Numbers

Authors: Klaus Meer and Gregorio Malajovich

Abstract
We study the question how difficult it is to compute the multi-homogeneous B\'ezout number for a polynomial system of given number $n$ of variables and given support $A$ of monomials with non-zero coefficients. We show that this number is NP-hard to compute. It cannot even be efficiently approximated within an arbitrary, fixed factor unless P = NP. This is joint work with Gregorio Malajovich.
Cite as

Klaus Meer and Gregorio Malajovich. On the Complexity of Computing Multi-Homogeneous Bézout Numbers. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{meer_et_al:DagSemProc.04401.9,
  author =	{Meer, Klaus and Malajovich, Gregorio},
  title =	{{On the Complexity of Computing Multi-Homogeneous B\~{A}ƒ\^{A}©zout Numbers}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.9},
  URN =		{urn:nbn:de:0030-drops-1460},
  doi =		{10.4230/DagSemProc.04401.9},
  annote =	{Keywords: multi-homogeneous B\~{A}ƒ\^{A}©zout numbers , number of roots of polynomials , approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.04401.10
On the Complexity of Parabolic Initial Value Problems with Variable Drift

Authors: Knut Petras and Klaus Ritter

Abstract
We consider linear parabolic initial value problems of second order in several dimensions. The initial condition is supposed to be fixed and we investigate the comutational complexity if the coefficients of the parabolic equations may vary in certain function spaces. Using the parametrix method (or Neumann series), we prove that lower bounds for the error of numerical methods are related to lower bounds for integration problems. On the other hand, approximating the Neumann series with Smolyak's method, we show that the problem is not much harder than a certain approximation problem. For Hölder classes on compact sets, e.g., lower and upper bounds are close together, such that we have an almost optimal method.
Cite as

Knut Petras and Klaus Ritter. On the Complexity of Parabolic Initial Value Problems with Variable Drift. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{petras_et_al:DagSemProc.04401.10,
  author =	{Petras, Knut and Ritter, Klaus},
  title =	{{On the Complexity of Parabolic Initial Value Problems with Variable Drift}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.10},
  URN =		{urn:nbn:de:0030-drops-1495},
  doi =		{10.4230/DagSemProc.04401.10},
  annote =	{Keywords: Partial differential equations , parabolic problems , Smolyak method , optimal methods}
}
Document
DOI: 10.4230/DagSemProc.04401.11
Optimal algorithms for global optimization in case of unknown Lipschitz constant

Authors: Matthias U. Horn

Abstract
We consider a family of function classes which allow functions with several minima and which demand only Lipschitz continuity for smoothness. We present an algorithm almost optimal for each of these classes.
Cite as

Matthias U. Horn. Optimal algorithms for global optimization in case of unknown Lipschitz constant. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{horn:DagSemProc.04401.11,
  author =	{Horn, Matthias U.},
  title =	{{Optimal algorithms for global optimization in case of unknown Lipschitz constant}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.11},
  URN =		{urn:nbn:de:0030-drops-1430},
  doi =		{10.4230/DagSemProc.04401.11},
  annote =	{Keywords: Global optimization , Lipschitz functions , optimal rate of convergence , complexity}
}
Document
DOI: 10.4230/DagSemProc.04401.12
Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings

Authors: Erich Novak, Stephan Dahlke, and Winfried Sickel

Abstract
We study the optimal approximation of the solution of an operator equation Au=f by linear mappings of rank n and compare this with the best n-term approximation with respect to an optimal Riesz basis. We consider worst case errors, where f is an element of the unit ball of a Hilbert space. We apply our results to boundary value problems for elliptic PDEs on an arbitrary bounded Lipschitz domain. Here we prove that approximation by linear mappings is as good as the best n-term approximation with respect to an optimal Riesz basis. Our results are concerned with approximation, not with computation. Our goal is to understand better the possibilities of nonlinear approximation.
Cite as

Erich Novak, Stephan Dahlke, and Winfried Sickel. Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{novak_et_al:DagSemProc.04401.12,
  author =	{Novak, Erich and Dahlke, Stephan and Sickel, Winfried},
  title =	{{Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.12},
  URN =		{urn:nbn:de:0030-drops-1471},
  doi =		{10.4230/DagSemProc.04401.12},
  annote =	{Keywords: elliptic operator equation , worst case error , linear approximation method , nonlinear approximation method , best n-term approximation Bernstein widths , manifold widths}
}
Document
DOI: 10.4230/DagSemProc.04401.13
Optimal Approximation of Elliptic Problems II: Wavelet Methods

Authors: Stephan Dahlke, Erich Novak, and Winfried Sickel

Abstract
This talk is concerned with optimal approximations of the solutions of elliptic boundary value problems. After briefly recalling the fundamental concepts of optimality, we shall especially discuss best n-term approximation schemes based on wavelets. We shall mainly be concerned with the Poisson equation in Lipschitz domains. It turns out that wavelet schemes are suboptimal in general, but nevertheless they are superior to the usual uniform approximation methods. Moreover, for specific domains, i.e., for polygonal domains, wavelet methods are in fact optimal. These results are based on regularity estimates of the exact solution in a specific scale of Besov spaces.
Cite as

Stephan Dahlke, Erich Novak, and Winfried Sickel. Optimal Approximation of Elliptic Problems II: Wavelet Methods. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.04401.13,
  author =	{Dahlke, Stephan and Novak, Erich and Sickel, Winfried},
  title =	{{Optimal Approximation of Elliptic Problems II: Wavelet Methods}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.13},
  URN =		{urn:nbn:de:0030-drops-1381},
  doi =		{10.4230/DagSemProc.04401.13},
  annote =	{Keywords: Elliptic operator equations , worst case error , best n-term approximation , wavelets , Besov regularity}
}
Document
DOI: 10.4230/DagSemProc.04401.14
Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights; Worst Case Setting

Authors: Gregorz W. Wasilkowski and Henryk Wozniakowski

Abstract
We present polynomial-time algorithms for multivariate problems defined over tensor product spaces of finite order. That is, algorithms that solve the problem with error not exceeding \epsilon at cost bounded by C d^q \epsilon^{-1}, where d denotes the number of variables.
Cite as

Gregorz W. Wasilkowski and Henryk Wozniakowski. Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights; Worst Case Setting. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{wasilkowski_et_al:DagSemProc.04401.14,
  author =	{Wasilkowski, Gregorz W. and Wozniakowski, Henryk},
  title =	{{Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights; Worst Case Setting}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.14},
  URN =		{urn:nbn:de:0030-drops-1526},
  doi =		{10.4230/DagSemProc.04401.14},
  annote =	{Keywords: Multivariate integration , multivariate approximation , complexity , polynomial-time algorithms , finite-order weights}
}
Document
DOI: 10.4230/DagSemProc.04401.15
Quantization of self-similar Probabilities

Authors: Siegfried Graf and Harald Luschgy

Abstract
The asymptotic behaviour of the quantization errors for self-similar probabilities is determined.
Cite as

Siegfried Graf and Harald Luschgy. Quantization of self-similar Probabilities. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{graf_et_al:DagSemProc.04401.15,
  author =	{Graf, Siegfried and Luschgy, Harald},
  title =	{{Quantization of self-similar Probabilities}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.15},
  URN =		{urn:nbn:de:0030-drops-1402},
  doi =		{10.4230/DagSemProc.04401.15},
  annote =	{Keywords: quantization , self-similar probabilities}
}
Document
DOI: 10.4230/DagSemProc.04401.16
Upper Error Bounds for Approximations of Stochastic Differential Equations with Markovian Switching

Authors: Norbert Hofmann

Abstract
We consider stochastic differential equations with Markovian switching (SDEwMS). An SDEwMS is a stochastic differential equation with drift and diffusion coefficients depending not only on the current state of the solution but also on the current state of a right-continuous Markov chain taking values in a finite state space. Consequently, an SDEwMS can be viewed as the result of a finite number of different scenarios switching from one to the other according to the movement of the Markov chain. The generator of the Markov chain is given by transition probabilities involving a parameter which controls the intensity of switching from one state to another. We construct numerical schemes for the approximation of SDE'swMS and present upper error bounds for these schemes. Our numerical schemes are based on a time discretization with constant step-size and on the values of a discrete Markov chain at the discretization points. It turns out that for the Euler scheme a similar upper bound as in the case of stochastic ordinary differential equations can be obtained, while for the Milstein scheme there is a strong connection between the power of the step-size appearing in the upper bound and the intensity of the switching.
Cite as

Norbert Hofmann. Upper Error Bounds for Approximations of Stochastic Differential Equations with Markovian Switching. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{hofmann:DagSemProc.04401.16,
  author =	{Hofmann, Norbert},
  title =	{{Upper Error Bounds for Approximations of Stochastic Differential Equations with Markovian Switching}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.16},
  URN =		{urn:nbn:de:0030-drops-1422},
  doi =		{10.4230/DagSemProc.04401.16},
  annote =	{Keywords: stochastic differential equations with Markovian switching , Markov chains , numerical methods , Euler scheme , Milstein scheme}
}

Filters

  • Authors
  • C
  • Cools, Ronald
  • D
  • Dahlke, Stephan
  • G
  • Golyandina, Nina
  • Graf, Siegfried
  • H
  • Hausenblas, Erika
  • Hofmann, Norbert
  • Horn, Matthias U.
  • L
  • Luschgy, Harald
  • M
  • Malajovich, Gregorio
  • Meer, Klaus
  • Müller-Gronbach, Thomas
  • N
  • Novak, Erich
  • Nuyens, Dirk
  • P
  • Pagès, Gilles
  • Petras, Knut
  • Plaskota, Leszek
  • R
  • Ritter, Klaus
  • S
  • Sickel, Winfried
  • T
  • Traub, Joseph F.
  • W
  • Wasilkowski, Gregorz W.
  • Wozniakowski, Henryk

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact