Fulltext

Multiple point evaluation on combined tensor product supports

Hiptmair, R. ; Phillips, G. ; Sinha, G.

In: Numerical Algorithms, 2013, vol. 63, no. 2, p. 317-337

Ajouter à la liste personnelle
    Titre
    • Multiple point evaluation on combined tensor product supports
    Auteur
    • Hiptmair, R.. SAM, ETH Zürich, 8092, Zürich, Switzerland
    • Phillips, G.. Neue Kantonsschule Aarau, 5000, Aarau, Switzerland
    • Sinha, G.. Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA
    Type de document
    • Postprint
    Langue
    • Anglais
    Publié dans
    • Numerical Algorithms, 2013, vol. 63, no. 2, p. 317-337. Springer US; http://www.springer-ny.com
    Autre version électronique
    Identifiant OAI-PMH
    • oai:doc.rero.ch:313714
    Summary
    We consider the multiple point evaluation problem for an n-dimensional space of functions [ − 1,1[ d ↦ℝ spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m ≥ n point evaluations of a function in this space with computational cost O(mlog d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog d − 1 n)