Cited By
View all- Feng YZhu SOu Y(2022)Accelerating DIN Model for Online CTR Prediction with Data Compression2022 7th International Conference on Big Data Analytics (ICBDA)10.1109/ICBDA55095.2022.9760313(84-89)Online publication date: 4-Mar-2022
Fast sparse kernel summation on cartesian grids: an on-chip algorithm for 3D implicit surface visualization
Pages 20 - 24
Abstract
This paper proposes a fast algorithm for evaluating summations of heterogenous sparse kernels of the form [EQUATION] points on an arbitrary fine Cartesian grid in Rd. The algorithm takes the advantage of sparsity and the structure of Cartesian grids. The sparsity admits operations only be done in some active subsets of the Cartesian grids; the structure of Cartesian grids reduce the storage for N points from O(dN) to O(1), a constant, and thus transforms costly memory intensive operations to cheap computationally intensive operations. This results in scalable algorithm with a complexity of O(N) and makes the postprocessing of large 3D implicit surface feasible on a PC or laptop. Numerical examples for 3D surface reconstruction are presented to illustrate the efficiency of the algorithm.
References
[1]
R.K. Beatson, M.D. Powell, and A.M. Tan. 2006. Fast evaluation of polyharmonic splines in three dimensions. IMA J. Numer. Anal. 27, 3 (11 2006), 427--450.
[2]
J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. 2001. Reconstruction and Representation of 3D Objects with Radial Basis Functions. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '01). 67--76.
[3]
J. Chen, L. Wang, and M. Anitescu. 2014. A Fast Summation Tree Code for Matrn Kernel. SIAM J. Sci. Comput. 36, 1 (2014), A289--A309.
[4]
T. Gu, X. Liu, Z. Mo, X. Xu, and S. Zhu. 2015. On the Memory Wall and Performance of Symmetric Sparse Matrix Vector Multiplications In Different Data Structures on Shared Memory Machines. In 2015 IEEE UIC-ATC-ScalCom. IEEE, Beijing, China, 1439--1444.
[5]
R. Krasny and L. Wang. 2011. Fast Evaluation of Multiquadric RBF Sums by a Cartesian Treecode. SIAM J. Sci. Comput. 33, 5 (2011), 2341--2355.
[6]
Ying L. 2006. A kernel independent fast multipole algorithm for radial basis functions. J. Comput. Phy. 213, 2 (2006), 451 -- 457.
[7]
L. Wasserman. 2004. All of statistics. Springer.
[8]
H. Wendland. 2004. Scattered Data Approximation. Cambridge University Press.
[9]
X. Xu and S. Zhu. 2018. Symmetric Sweeping Algorithms for Overlaps of Quadrilateral Meshes of the Same Connectivity. In Computational Science - ICCS 2018 - 18th International Conference, Wuxi, China, June 11-13, 2018 Proceedings, Part III. 61--75.
[10]
R. Yokota, L.A. Barba, and M.G. Knepley. 2010. PetRBF A parallel O(N) algorithm for radial basis function interpolation with Gaussians. Comput. Methods. Appl. Mech. Eng. 199, 25 (2010), 1793--1804.
[11]
S. Zhu. 2012. Compactly Supported Radial Basis Functions How and Why? Technical Report. University of Oxford, Oxford. http://eprints.maths.ox.ac.uk/1561/
[12]
S. Zhu, T. Gu, and X. Liu. 2014. Minimizing synchronizations in sparse iterative solvers for distributed supercomputers. Comput. Math. Appl. 67, 1 (2014), 199 -- 209.
[13]
S. Zhu, T. Gu, Xu. X., and Z. Mo. 2016. Information Splitting for Big Data Analytics. In 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC). Chengdu, China, 294--302.
[14]
S. Zhu and A.J. Wathen. 2014. Fast sparse kernel summation on Cartesian grids. Technical Report NA-14-06. University of Oxford, Oxford, http://eprints.maths.ox.ac.uk/1820/
[15]
S. Zhu and A.J. Wathen. 2015. Convexity and Solvability for Compactly Supported Radial Basis Functions with Different Shapes. J. Sci. Comput. 63, 3 (01 Jun 2015), 862--884.
Index Terms
- Fast sparse kernel summation on cartesian grids: an on-chip algorithm for 3D implicit surface visualization
Recommendations
Kernel Matching Pursuit
Matching Pursuit algorithms learn a function that is a weighted sum of basis functions, by sequentially appending functions to an initially empty basis, to approximate a target function in the least-squares sense. We show how matching pursuit can be ...
Fast Kernel Sparse Representation
DICTA '11: Proceedings of the 2011 International Conference on Digital Image Computing: Techniques and ApplicationsTwo efficient algorithms are proposed to seek the sparse representation on high-dimensional Hilbert space. By proving that all the calculations in Orthogonal Match Pursuit (OMP) are essentially inner-product combinations, we modify the OMP algorithm to ...
Multi-resolutive sparse approximations of d-dimensional data
This paper proposes an iterative computation of sparse representations of functions defined on R^d, which exploits a formulation of the sparsification problem equivalent to Support Vector Machine and based on Tikhonov regularization. Through this ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 March 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Xi'an Jiatong-Liverpool University
- Natural Science Foundation of Jiangsu Province
- National Natural Science Foundation of China
Conference
HP3C '19
HP3C '19: 2019 the 3rd International Conference on High Performance Compilation, Computing and Communications
March 8 - 10, 2019
Xi'an, China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 58Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Feb 2025
Other Metrics
Citations
Cited By
View all- Feng YZhu SOu Y(2022)Accelerating DIN Model for Online CTR Prediction with Data Compression2022 7th International Conference on Big Data Analytics (ICBDA)10.1109/ICBDA55095.2022.9760313(84-89)Online publication date: 4-Mar-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in