Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Scientific Computing
Erschienen in: Journal of Scientific Computing 1/2018

21.04.2017

OpenCL Based Parallel Algorithm for RBF-PUM Interpolation

verfasst von: Roberto Cavoretto, Teseo Schneider, Patrick Zulian

Erschienen in: Journal of Scientific Computing | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a parallel algorithm for multivariate Radial Basis Function Partition of Unity Method (RBF-PUM) interpolation. The concurrent nature of the RBF-PUM enables designing parallel algorithms for dealing with a large number of scattered data-points in high space dimensions. To efficiently exploit this concurrency, our algorithm makes use of shared-memory parallel processors through the OpenCL standard. This efficiency is achieved by a parallel space partitioning strategy with linear computational time complexity with respect to the input and evaluation points. The speed of our approach allows for computationally more intensive construction of the interpolant. In fact, the RBF-PUM can be coupled with a cross-validation technique that searches for optimal values of the shape parameters associated with each local RBF interpolant, thus reducing the global interpolation error. The numerical experiments support our claims by illustrating the interpolation errors and the running times of our algorithm.
Vorheriger Artikel Positivity for Convective Semi-discretizations
Nächster Artikel High Order Accurate Finite Difference Modeling of Seismo-Acoustic Wave Propagation in a Moving Atmosphere and a Heterogeneous Earth Model Coupled Across a Realistic Topography

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
2.
3.
Bozzini, M., Lenarduzzi, L., Rossini, M.: Polyharmonic splines: an approximation method for noisy scattered data of extra-large size. Appl. Math. Comput. 216, 317–331 (2010)MathSciNetMATH
4.
Brent, R.P.: Algorithms for Minimization Without Derivatives. Courier Corporation (2013)
5.
Buhmann, M.D.: Radial Basis Functions: Theory and Implementation, Cambridge Monographs on Applied and Computational Mathematics, vol. 12. Cambridge University Press, Cambridge (2003)CrossRef
6.
Cavoretto, R.: A numerical algorithm for multidimensional modeling of scattered data points. Comput. Appl. Math. 34, 65–80 (2015)MathSciNetCrossRefMATH
7.
Cavoretto, R., De Rossi, A.: A trivariate interpolation algorithm using a cube-partition searching procedure. SIAM J. Sci. Comput. 37, A1891–A1908 (2015)MathSciNetCrossRefMATH
8.
Cavoretto, R., De Rossi, A., Perracchione, E.: Efficient computation of partition of unity interpolants through a block-based searching technique. Comput. Math. Appl. 71, 2568–2584 (2016)MathSciNetCrossRef
9.
Cavoretto, R., De Rossi, A., Perracchione, E., Venturino, E.: Robust approximation algorithms for the detection of attraction basins in dynamical systems. J. Sci. Comput. 68, 395–415 (2016)MathSciNetCrossRefMATH
10.
Cavoretto, R., Fasshauer, G.E., McCourt, M.: An introduction to the Hilbert–Schmidt SVD using iterated Brownian bridge kernels. Numer. Algorithms 68, 393–422 (2015)MathSciNetCrossRefMATH
11.
De Marchi, S., Santin, G.: Fast computation of orthonormal basis for rbf spaces through Krylov space methods. BIT 55, 949–966 (2015)MathSciNetCrossRefMATH
12.
Dell’Accio, F., Di Tommaso, F.: Complete Hermite–Birkhoff interpolation on scattered data by combined Shepard operators. J. Comput. Appl. Math. 300, 192–206 (2016)MathSciNetCrossRefMATH
13.
Deparis, S., Forti, D., Quarteroni, A.: A rescaled localized radial basis function interpolation on non-cartesian and nonconforming grids. SIAM J. Sci. Comput. 36, A2745–A2762 (2014)MathSciNetCrossRefMATH
14.
Ericson, C.: Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology). Morgan Kaufmann Publishers Inc., San Francisco (2004)
15.
Fasshauer, G., McCourt, M.: Kernel-Based Approximation Methods Using Matlab, Interdisciplinary Mathematical Sciences, vol. 19. World Scientific, Singapore (2015)MATH
16.
Fasshauer, G.E.: Meshfree Approximation Methods with Matlab, Interdisciplinary Mathematical Sciences, vol. 6. World Scientific, Singapore (2007)CrossRefMATH
17.
Fasshauer, G.E.: Positive definite kernels: past, present and future. Dolomites Res. Notes Approx. 4, 21–63 (2011)CrossRef
18.
Fernando, R.: GPU Gems: Programming Techniques. Tips and Tricks for Real-Time Graphics, Pearson Higher Education (2004)
19.
Fornberg, B., Flyer, N.: A Primer on Radial Basis Functions with Applications to the Geosciences. SIAM, Philadelphia (2015)CrossRefMATH
20.
Fornberg, B., Larsson, E., Flyer, N.: Stable computations with Gaussian radial basis functions. SIAM J. Sci. Comput. 33, 869–892 (2011)MathSciNetCrossRefMATH
21.
Forum, M.P.I.: MPI: A Message-Passing Interface Standard Version 3.0 (2012). Chapter author for Collective Communication, Process Topologies, and One Sided Communications
22.
Heryudono, A., Larsson, E., Ramage, A., von Sydow, L.: Preconditioning for radial basis function partition of unity methods. J. Sci. Comput. 67, 1089–1109 (2016)MathSciNetCrossRefMATH
23.
Hubbert, S., Le Gia, Q., Morton, T.: Spherical Radial Basis Functions, Theory and Applications. SpringerBriefs in Mathematics. Springer, London (2015)MATH
24.
Krause, R., Zulian, P.: A parallel approach to the variational transfer of discrete fields between arbitrarily distributed finite element meshes. SIAM J. Sci. Comput. 38, C307–C333 (2016)MathSciNetCrossRefMATH
25.
Melenk, J.M., Babuška, I.: The partition of unity finite element method: basic theory and applications. Comput. Methods. Appl. Mech. Eng. 139, 289–314 (1996)MathSciNetCrossRefMATH
26.
Nichols, B., Buttlar, D., Farrell, J.P.: Pthreads Programming. O’Reilly & Associates Inc, Sebastopol (1996)
27.
Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with CUDA. Queue 6(2), 40–53 (2008)CrossRef
28.
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems Volume 1: Linear Information. No. 6 in EMS Tracts in Mathematics. European Mathematical Society (2008)
29.
30.
31.
32.
R Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2014)
33.
Rashidinia, J., Fasshauer, G.E., Khasi, M.: A stable method for the evaluation of Gaussian radial basis function solutions of interpolation and collocation problems. Comput. Math. Appl. 72, 178–193 (2016)MathSciNetCrossRef
34.
35.
Rippa, S.: An algorithm for selecting a good value for the parameter \(c\) in radial basis function interpolation. Adv. Comput. Math. 11, 193–210 (1999)MathSciNetCrossRefMATH
36.
Safdari-Vaighani, A., Heryudono, A., Larsson, E.: A radial basis function partition of unity collocation method for convection-diffusion equations arising in financial applications. J. Sci. Comput. 64, 341–367 (2015)MathSciNetCrossRefMATH
37.
38.
Schling, B.: The Boost C++ Libraries. XML Press, Fort Collins (2011)
39.
Shcherbakov, V., Larsson, E.: Radial basis function partition of unity methods for pricing vanilla basket options. Comput. Appl. Math. 71, 185–200 (2016)MathSciNetCrossRef
40.
Speck, R., Gibbon, P., Hofmann, M.: Efficiency and scalability of the parallel Barnes-Hut tree code PEPC. In: B. Chapman, F. Desprez, G.R. Joubert, A. Lichnewsky, F.J. Peters, T. Priol (eds.) Parallel Computing: From Multicores and GPU’s to Petascale, Advances in Parallel Computing, vol. 19, pp. 35–42. IOS Press (2010)
41.
Stone, J.E., Gohara, D., Shi, G.: Opencl: a parallel programming standard for heterogeneous computing systems. IEEE Des. Test 12(3), 66–73 (2010). doi:10.​1109/​MCSE.​2010.​69
42.
Wendland, H.: Fast evaluation of radial basis functions: methods based on partition of unity. In: C.K. Chui, L.L. Schumaker, J. Stöckler (eds.) Approximation Theory X: Wavelets, Splines, and Applications, pp. 473–483. Vanderbilt University Press (2002)
43.
Wendland, H.: Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17. Cambridge University Press, Cambridge (2005)
44.
Wong, R., Luk, W., Heng, P.: Sampling with Hammersley and Halton points. J. Graphics Tools 2, 9–24 (1997)CrossRef
Metadaten
Titel
OpenCL Based Parallel Algorithm for RBF-PUM Interpolation
verfasst von
Roberto Cavoretto
Teseo Schneider
Patrick Zulian
Publikationsdatum
21.04.2017
Verlag
Springer US
Erschienen in
Journal of Scientific Computing / Ausgabe 1/2018
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-017-0431-x

Weitere Artikel der Ausgabe 1/2018

Journal of Scientific Computing 1/2018 Zur Ausgabe

Author Correction

Correction to: Superconvergence of Immersed Finite Volume Methods for One-Dimensional Interface Problems

OriginalPaper

Tensor Methods for Solving Symmetric -tensor Systems

OriginalPaper

High Order -Continuous Galerkin Schemes for High Order PDEs, Conservation of Quadratic Invariants and Application to the Korteweg-de Vries Model

OriginalPaper

Fast Laplace Transform Methods for Free-Boundary Problems of Fractional Diffusion Equations

OriginalPaper

An Adaptive Moving Mesh Finite Element Solution of the Regularized Long Wave Equation

OriginalPaper

High Order Accurate Finite Difference Modeling of Seismo-Acoustic Wave Propagation in a Moving Atmosphere and a Heterogeneous Earth Model Coupled Across a Realistic Topography