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 Japanese researchers develop ultrathin, highly elastic skin display
19.02.2018 | University of Tokyo

nachricht Why bees soared and slime flopped as inspirations for systems engineering
19.02.2018 | Georgia Institute of Technology

All articles from Information Technology >>>

The most recent press releases about innovation >>>

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

Im Focus: In best circles: First integrated circuit from self-assembled polymer

For the first time, a team of researchers at the Max-Planck Institute (MPI) for Polymer Research in Mainz, Germany, has succeeded in making an integrated circuit (IC) from just a monolayer of a semiconducting polymer via a bottom-up, self-assembly approach.

In the self-assembly process, the semiconducting polymer arranges itself into an ordered monolayer in a transistor. The transistors are binary switches used...

Im Focus: Demonstration of a single molecule piezoelectric effect

Breakthrough provides a new concept of the design of molecular motors, sensors and electricity generators at nanoscale

Researchers from the Institute of Organic Chemistry and Biochemistry of the CAS (IOCB Prague), Institute of Physics of the CAS (IP CAS) and Palacký University...

Im Focus: Hybrid optics bring color imaging using ultrathin metalenses into focus

For photographers and scientists, lenses are lifesavers. They reflect and refract light, making possible the imaging systems that drive discovery through the microscope and preserve history through cameras.

But today's glass-based lenses are bulky and resist miniaturization. Next-generation technologies, such as ultrathin cameras or tiny microscopes, require...

Im Focus: Stem cell divisions in the adult brain seen for the first time

Scientists from the University of Zurich have succeeded for the first time in tracking individual stem cells and their neuronal progeny over months within the intact adult brain. This study sheds light on how new neurons are produced throughout life.

The generation of new nerve cells was once thought to taper off at the end of embryonic development. However, recent research has shown that the adult brain...

Im Focus: Interference as a new method for cooling quantum devices

Theoretical physicists propose to use negative interference to control heat flow in quantum devices. Study published in Physical Review Letters

Quantum computer parts are sensitive and need to be cooled to very low temperatures. Their tiny size makes them particularly susceptible to a temperature...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

2nd International Conference on High Temperature Shape Memory Alloys (HTSMAs)

15.02.2018 | Event News

Aachen DC Grid Summit 2018

13.02.2018 | Event News

How Global Climate Policy Can Learn from the Energy Transition

12.02.2018 | Event News

 
Latest News

Researchers invent tiny, light-powered wires to modulate brain's electrical signals

21.02.2018 | Life Sciences

The “Holy Grail” of peptide chemistry: Making peptide active agents available orally

21.02.2018 | Life Sciences

Atomic structure of ultrasound material not what anyone expected

21.02.2018 | Materials Sciences

VideoLinks
Science & Research
Overview of more VideoLinks >>>