Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Enhancing the Efficiency of Complex Computations

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


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)

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/

Monika Landgraf | idw
Further information:
http://www.kit.edu
http://algo2.iti.kit.edu/documents/kahip/

More articles from Information Technology:

nachricht Researchers create new technique for manipulating polarization of terahertz radiation
20.07.2017 | Brown University

nachricht Holograms taken to new dimension
19.07.2017 | University of Utah

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Manipulating Electron Spins Without Loss of Information

Physicists have developed a new technique that uses electrical voltages to control the electron spin on a chip. The newly-developed method provides protection from spin decay, meaning that the contained information can be maintained and transmitted over comparatively large distances, as has been demonstrated by a team from the University of Basel’s Department of Physics and the Swiss Nanoscience Institute. The results have been published in Physical Review X.

For several years, researchers have been trying to use the spin of an electron to store and transmit information. The spin of each electron is always coupled...

Im Focus: The proton precisely weighted

What is the mass of a proton? Scientists from Germany and Japan successfully did an important step towards the most exact knowledge of this fundamental constant. By means of precision measurements on a single proton, they could improve the precision by a factor of three and also correct the existing value.

To determine the mass of a single proton still more accurate – a group of physicists led by Klaus Blaum and Sven Sturm of the Max Planck Institute for Nuclear...

Im Focus: On the way to a biological alternative

A bacterial enzyme enables reactions that open up alternatives to key industrial chemical processes

The research team of Prof. Dr. Oliver Einsle at the University of Freiburg's Institute of Biochemistry has long been exploring the functioning of nitrogenase....

Im Focus: The 1 trillion tonne iceberg

Larsen C Ice Shelf rift finally breaks through

A one trillion tonne iceberg - one of the biggest ever recorded -- has calved away from the Larsen C Ice Shelf in Antarctica, after a rift in the ice,...

Im Focus: Laser-cooled ions contribute to better understanding of friction

Physics supports biology: Researchers from PTB have developed a model system to investigate friction phenomena with atomic precision

Friction: what you want from car brakes, otherwise rather a nuisance. In any case, it is useful to know as precisely as possible how friction phenomena arise –...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

»We are bringing Additive Manufacturing to SMEs«

19.07.2017 | Event News

The technology with a feel for feelings

12.07.2017 | Event News

Leipzig HTP-Forum discusses "hydrothermal processes" as a key technology for a biobased economy

12.07.2017 | Event News

 
Latest News

Researchers create new technique for manipulating polarization of terahertz radiation

20.07.2017 | Information Technology

High-tech sensing illuminates concrete stress testing

20.07.2017 | Materials Sciences

First direct observation and measurement of ultra-fast moving vortices in superconductors

20.07.2017 | Physics and Astronomy

VideoLinks
B2B-VideoLinks
More VideoLinks >>>