Home | deutsch | Legals | Sitemap | Intranet | KIT
Portrait Monika Landgraf
Contact:
Monika Landgraf
Chief Press Officer, Head of Press Office

Phone: +49 721 608-47414
Fax: +49 721 608-43658
e-mail

Subscription of Press Releases

RSS-Feed

Press Release 155/2013

Enhancing the Efficiency of Complex Computations

The Karlsruhe Graph Partitioner KaHIP Wins over International Competitors
2013_155_Mehr_Effizienz_fuer_komplexes_Rechnen_72dpi
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. (Graphics: 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 graph) 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 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.

 

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 open source 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.

 

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

 

Karlsruhe Institute of Technology (KIT) is a public corporation according to the legislation of the state of Baden-Württemberg. It fulfills the mission of a university and the mission of a national research center of the Helmholtz Association. Research activities focus on energy, the natural and built environment as well as on society and technology and cover the whole range extending from fundamental aspects to application. With about 9400 employees, including more than 6000 staff members in the science and education sector, and 24500 students, KIT is one of the biggest research and education institutions in Europe. Work of KIT is based on the knowledge triangle of research, teaching, and innovation.

le, 29.11.2013

For further information, please contact:

Sebastian Schäfer
Fakultät für Informatik, Öffentlichkeitsarbeit
Tel.: +49 721 608-44344
Fax: +49 721 608-4177
E-Mail: sebastian schaeferLfg9∂kit edu
The photo of printing quality may be requested by presseCfa7∂kit edu or phone: +49 721 608-47414. The press release is available as a PDF file.