CUDA Papers

A collection of research papers and projects utilizing CUDA technology

Rapid Multipole Graph Drawing on the GPU


As graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX.


Apeksha Godiyal, Jared Hoberock, University of Illinois

Michael Garland, NVIDIA Corporation

John C Hart, University of Illinois

Leave a Reply