Making complex computations more efficient

Image courtesy Christian Schulz, KIT.

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.

“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.