Making Complex Computations More Efficient

Researchers at the Karlsruhe Institute of Technology have developed open-source software capable of significantly speeding up complex computations.

Graphs are used by many computer applications to model relationships between objects and 'graph partitioning' is an important method used to manage complex computations on steadily growing networks.

The Karlsruhe High Quality Partitioner (KaHIP) was developed by Peter Sanders and Christian Schulz. It enables modeled objects (nodes of the graph) to be divided into blocks of about the same size, while the number of edges between the blocks is minimized.

In this way, route planners, for instance, can be accelerated: The transport network stored in the route planner is partitioned. When planning a specific route, e.g. from Berlin to Hamburg, large parts of the transport network can be neglected, as they are of no relevance. In this way, a partitioning tool like KaHIP can accelerate the computation of a route by several factors.

“Computation speed increases with a decreasing number of edges that have to be cut,” says Schulz. “Our system solves the graph partitioning problem by cutting about three times less edges than comparable tools on the market.” 

The above graph shows how the software can be used to model air flow around an airplane wing. The four colors reflect the partitioning of the graph and, hence, the distribution of computation among four computers. -- Source: KIT, i SGTW