Engineering the Fast-Multipole-Multilevel Method for multicore and SIMD architectures

In this thesis, we present a new variant of the Fast-Mulitpole-Multilevel Method, which is used to draw large graphs. Based on the original approach by Stefan Hachul, a new algo- rithm is presented, which is optimized primarily for practical speed. In order to achieve this, special processor instructions are used to accelerate computations with complex num- bers. In addition, parts of the algorithm are executed in parallel to benefit from the widely spread multicore architectures. Besides these two rather technical improvements, we de- scribe a new construction method for a spatial space decomposition data structure, called the quadtree. The algorithm exploits the binary representation of the coordinates and shifts most of the work to the sorting of the input. Furthermore, we introduce another problem from computational geometry, the well-separated pair decomposition, and success- fully apply it in order to simplify parts of the algorithm. The resulting algorithm is able to compete in speed and layout quality even with a recently published graphics processor accelerated implementation