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

Zhu, S
Wathen, A
Machinery, A

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

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.

994972

Not Submitted

Conference Paper

9781450366380