2019 THE 3RD INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPILATION, COMPUTING AND COMMUNICATIONS (HP3C 2019)
© 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.
Submitted to ORA: