Enhancing the efficiency of complex computations

Nov 29, 2013
Graph to compute the air flow around an airplane wing: The four colors reflect the partitioning of the graph and, hence, the distribution of computation among four computers. Credit: Christian Schulz, KIT

Planning a trip from Berlin to Hamburg, simulating air flows around a new passenger airplane, or friendships on Facebook – many computer applications model relationships between objects by graphs (networks) in the sense of discrete mathematics. An important method to manage complex computations on steadily growing networks is graph partitioning. The KIT computer scientists Professor Peter Sanders and Dr. Christian Schulz have now released the Karlsruhe High Quality Partitioner (KaHIP). The solutions produced by this tool presently are the best worldwide.

By means of KaHIP, the modeled objects (nodes of the ) are divided into blocks of about the same size, while the number of edges between the blocks are 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 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.

Complex computations with very detailed graphs, such as the computation of flow properties of an airplane, frequently require more than one computer. In such a case, KaHIP can distribute computations in a reasonable manner and ensures efficient, simultaneous computations on several computers. The determining factor is the number of edges that have to be cut in a graph. "Computation speed increases with a decreasing number of edges that have to be cut. Our system solves the graph partitioning problem by cutting about three times less edges than comparable tools on the market," Dr. Christian Schulz, scientist at the KIT Institute of Theoretical Informatics, explains.

KaHIP – Open Source

Within the framework of his PhD thesis at KIT, Christian Schulz developed KaHIP together with Professor Peter Sanders. Already during the development phase the tool received high interest in science and industry. KaHIP is now available as program. In international comparison, KaHIP has already proven to be competitive. It scored most of the points in the 10th DIMACS Implementation Challenge as well as the Walshaw Benchmark, in which graph partitioners from all over the world compete with each other.

"Based on our long-standing experience in the area of graph processing, we are now able to offer KaHIP, a tool that supplies the best solution quality worldwide for a number of applications," says Professor Peter Sanders of the KIT Institute of Theoretical Informatics.

Professor Sanders was granted several prizes for his work on algorithms for graph processing. Among them were the State Research Award and the Google Focused Research Award in 2012 as well as the Gottfried Wilhelm Leibniz Prize in 2011.

Explore further: Machine learning branches out

More information: For more information on KaHIP, click: algo2.iti.kit.edu/documents/kahip/

add to favorites email to friend print save as pdf

Related Stories

Short algorithm, long-range consequences

Mar 01, 2013

In the last decade, theoretical computer science has seen remarkable progress on the problem of solving graph Laplacians—the esoteric name for a calculation with hordes of familiar applications in scheduling, image processing, ...

Machine learning branches out

Nov 14, 2013

Much artificial-intelligence research is concerned with finding statistical correlations between variables: What combinations of visible features indicate the presence of a particular object in a digital ...

Explained: Graphs

Dec 17, 2012

When most people hear the word "graph," an image springs to mind: a pair of perpendicular lines overlaid with a line, a curve, or bars of different heights.

How quickly things spread

Feb 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information ...

Recommended for you

Oculus unveils new prototype VR headset

Sep 20, 2014

Oculus has unveiled a new prototype of its virtual reality headset. However, the VR company still isn't ready to release a consumer edition.

Who drives Alibaba's Taobao traffic—buyers or sellers?

Sep 18, 2014

As Chinese e-commerce firm Alibaba prepares for what could be the biggest IPO in history, University of Michigan professor Puneet Manchanda dug into its Taobao website data to help solve a lingering chicken-and-egg question.

Computerized emotion detector

Sep 16, 2014

Face recognition software measures various parameters in a mug shot, such as the distance between the person's eyes, the height from lip to top of their nose and various other metrics and then compares it with photos of people ...

User comments : 0