SC Conference - Activity Details
Efficient Band Approximation of Gram Matrices for Large Scale Kernel Methods on GPUs
Authors:| Mohamed Hussein (University of Maryland) |
| Wael Abd-Almageed (University of Maryland) |
| Particle Methods |
| Tuesday, 04:00PM - 04:30PM |
| Room PB255 |
Kernel-based methods require O(N^2) time and space complexities
to compute and store non-sparse Gram matrices, which is prohibitively expensive for large scale problems. We introduce a novel method to approximate a Gram matrix with a band matrix. Our method relies on the locality preserving
properties of space filling curves, and the special structure of Gram matrices. Our approach has several important merits. First, it computes only those elements of the Gram matrix that lie within the projected band. Second, it is simple to parallelize. Third, using the special band matrix structure makes it space efficient and GPU-friendly. We developed GPU implementations for the Affinity Propagation (AP) clustering algorithm using both our method and the COO sparse representation. Our band approximation is about 5 times more space efficient and faster to construct than COO. AP gains up to 6x speedup using our method without any degradation in its clustering performance.
The full paper can be found in the
ACM Digital Library and IEEE Computer Society
   |