Processing math: 100%
edoc-vmtest

Approximation of bi-variate functions : singular value decomposition versus sparse grids

Griebel, Michael and Harbrecht, Helmut. (2014) Approximation of bi-variate functions : singular value decomposition versus sparse grids. Ima Journal of Numerical Analysis, Vol. 34, H. 1. pp. 8-54.

[img] PDF - Published Version
897Kb

Official URL: http://edoc.unibas.ch/dok/A6223408

Downloads: Statistics Overview

Abstract

We compare the cost complexities of two approximation schemes for functions finHp(Omega1timesOmega2) which live on the product domain Omega1timesOmega2 of sufficiently smooth domains Omega1subsetmathbbRn1 and Omega2subsetmathbbRn2, namely the singular value / Karhunen-L`oeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated {em fixed} order r of accuracy are given on the domains Omega1 and Omega2. Then, the sparse grid approximation essentially needs only mathcalO(varepsilonq) with q=fracmaxn1,n2r unknowns to reach a prescribed accuracy varepsilon provided that the smoothness of f satisfies pgerfracn1+n2maxn1,n2, which is an almost optimal rate. The singular value decomposition produces this rate only if f is analytical since otherwise the decay of the singular values is not fast enough. If p>rfracn1+n2maxn1,n2, then the sparse grid approach gives essentially the rate mathcalO(varepsilonq) with q=fracn1+n2p while, for the singular value decomposition, we can only prove the rate mathcalO(varepsilonq) with q=frac2minr,pminn1,n2+2pmaxn1,n2(2pminn1,n2)minr,p. We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practice. pfracn1+n2maxn1,n2, then the sparse grid approach gives essentially the rate mathcalO(varepsilonq) with q=fracn1+n2p while, for the singular value decomposition, we can only prove the rate mathcalO(varepsilonq) with q=frac2minr,pminn1,n2+2pmaxn1,n2(2pminn1,n2)minr,p. We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practi
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Mathematik > Computational Mathematics (Harbrecht)
UniBasel Contributors:Harbrecht, Helmut
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:Oxford University Press
ISSN:0272-4979
Note:Publication type according to Uni Basel Research Database: Journal article
Language:English
Identification Number:
edoc DOI:
Last Modified:13 Mar 2018 17:15
Deposited On:27 Mar 2014 13:13

Repository Staff Only: item control page