Paper Info
Title
An Algebraic Parallel Treecode in Arbitrary Dimensions
Abstract
We present a parallel tree code for fast kernel summation in high dimensions -- a common problem in data analysis and computational statistics. Fast kernel summations can be viewed as approximation schemes for dense kernel matrices. Tree code algorithms (or simply tree codes) construct low-rank approximations of certain off-diagonal blocks of the kernel matrix. These blocks are identified with the help of spatial data structures, typically trees. There is extensive work on tree codes and their parallelization for kernel summations in three dimensions, but there is little work on high-dimensional problems. Recently, we introduced a novel tree code, ASKIT, which resolves most of the shortcomings of existing methods. We introduce novel parallel algorithms for ASKIT, derive complexity estimates, and demonstrate scalability on synthetic, scientific, and image datasets. In particular, we introduce a local essential tree construction that extends to arbitrary dimensions in a scalable manner. We introduce data transformations for memory locality and use GPU acceleration. We report results on the "Maverick" and "Stampede" systems at the Texas Advanced Computing Centre. Our largest computations involve two billion points in 64 dimensions on 32, 768 x86 cores and 8 million points in 784 dimensions on 16, 384 x86 cores.
Year
DOI
Venue
2015
10.1109/IPDPS.2015.86
2015 IEEE International Parallel and Distributed Processing Symposium
Keywords
Field
DocType
treecodes,randomized linear algebra,GPUs,kernel summation
Kernel (linear algebra),Linear algebra,Locality,Parallel algorithm,Computer science,CUDA,Parallel computing,Tree kernel,Theoretical computer science,Computational statistics,Scalability,Distributed computing
Conference
ISSN
Citations 
PageRank 
1530-2075
9
0.51
References 
Authors
20
4
Name
Order
Citations
PageRank
William B. March11498.96
Bo Xiao2524.06
Chenhan D. Yu3626.25
George Biros493877.86