Fast Sparse Kernel Summation on Cartesian Grids: an on-chip algorithm for 3D implicit surface visualization

Author: 

Zhu, S
Wathen, A
Machinery, A

Publication Date: 

2019

Journal: 

2019 THE 3RD INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPILATION, COMPUTING AND COMMUNICATIONS (HP3C 2019)

Last Updated: 

2019-08-18T21:50:13.657+01:00

DOI: 

10.1145/3318265.3318278

page: 

20-24

abstract: 

© 2019 Association for Computing Machinery. This paper proposes a fast algorithm for evaluating sum-mations of heterogenous sparse kernels P of the form s(x) = Σ Mi=1 α i φ(ϵ i ∥x-x i ∥) on N points on an arbitrary fine Carte-sian grid in R d . The algorithm takes the advantage of s-parsity 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.

Symplectic id: 

994972

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Conference Paper

ISBN-13: 

9781450366380