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

Dish Network denies wrongdoing in $2M settlement

9 hours ago

The state attorney general's office says Dish Network Corp. will reimburse Washington state customers about $2 million for what it calls a deceptive surcharge, but the satellite TV provider denies any wrongdoing.

Yahoo sees signs of growth in 'core' (Update)

9 hours ago

Yahoo reported a stronger-than-expected first-quarter profit Tuesday, results hailed by chief executive Marissa Mayer as showing growth in the Web giant's "core" business.

Intel reports lower 1Q net income, higher revenue

9 hours ago

Intel's earnings fell in the first three months of the year amid a continued slump in the worldwide PC market, but revenue grew slightly because of solid demand for tablet processors and its data center services.

Earthquake simulation tops one quadrillion flops

11 hours ago

A team of computer scientists, mathematicians and geophysicists at Technische Universitaet Muenchen (TUM) and Ludwig-Maximillians Universitaet Muenchen (LMU) have – with the support of the Leibniz Supercomputing ...

Twitter buys data analytics partner Gnip

12 hours ago

Twitter says it has bought its data partner Gnip, which provides analysis of the more than 500 million tweets its users share each day—to advertisers, academic institutions, politicians and other customers.

User comments : 0

More news stories

Intel reports lower 1Q net income, higher revenue

Intel's earnings fell in the first three months of the year amid a continued slump in the worldwide PC market, but revenue grew slightly because of solid demand for tablet processors and its data center services.

Low Vitamin D may not be a culprit in menopause symptoms

A new study from the Women's Health Initiative (WHI) shows no significant connection between vitamin D levels and menopause symptoms. The study was published online today in Menopause, the journal of The North American Menopa ...

Astronomers: 'Tilt-a-worlds' could harbor life

A fluctuating tilt in a planet's orbit does not preclude the possibility of life, according to new research by astronomers at the University of Washington, Utah's Weber State University and NASA. In fact, ...