Faster graph matching by parallel approximation algorithms

Parallel computers are everywhere: from desktop to supercomputer, we can speed up computations by performing them in parallel, using several processors simultaneously to solve a single problem. To achieve this speedup, however, we need to parallelise our algorithms, taking care to distribute the work evenly across the processors and to minimise communication between them. As an introductory example, we will briefly discuss how the three-dimensional Fast Fourier transform is done in parallel by our recent software package FFTU, based on using a 3D cyclic data distribution. In the main part of the talk, we present a parallel algorithm for matching pairs of nodes in a graph based on choosing dominant edges. The algorithm is suitable for huge graphs such as those that arise in social networks. Social networks are characterised by having many triangles, which happens because your friends have a high probably also to be friends of each other. This is exploited by recommender systems that try to close triangles in a network. A related problem from network science is how to count triangles quickly, and how to do this in parallel.