Featured Research

from universities, journals, and other organizations

Enhancing efficiency of complex computations

Date:
November 29, 2013
Source:
Karlsruhe Institute of Technology
Summary:
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. Computer scientists have now released the Karlsruhe High Quality Partitioner (KaHIP). The solutions produced by this tool presently are the best worldwide.

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.

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.


Story Source:

The above story is based on materials provided by Karlsruhe Institute of Technology. Note: Materials may be edited for content and length.


Cite This Page:

Karlsruhe Institute of Technology. "Enhancing efficiency of complex computations." ScienceDaily. ScienceDaily, 29 November 2013. <www.sciencedaily.com/releases/2013/11/131129101805.htm>.
Karlsruhe Institute of Technology. (2013, November 29). Enhancing efficiency of complex computations. ScienceDaily. Retrieved April 16, 2014 from www.sciencedaily.com/releases/2013/11/131129101805.htm
Karlsruhe Institute of Technology. "Enhancing efficiency of complex computations." ScienceDaily. www.sciencedaily.com/releases/2013/11/131129101805.htm (accessed April 16, 2014).

Share This



More Computers & Math News

Wednesday, April 16, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Google Patents Contact Lens Cameras; Internet Is Wary

Google Patents Contact Lens Cameras; Internet Is Wary

Newsy (Apr. 15, 2014) Google has filed for a patent to develop contact lenses capable of taking photos. The company describes possible benefits to blind people. Video provided by Newsy
Powered by NewsLook.com
NYPD Ends Muslim Surveillance Program

NYPD Ends Muslim Surveillance Program

AP (Apr. 15, 2014) The New York City Police Department has ended a program that once kept tabs on the city's muslim population. (April 15) Video provided by AP
Powered by NewsLook.com
Images Of Rumored Amazon Smartphone Leaked

Images Of Rumored Amazon Smartphone Leaked

Newsy (Apr. 15, 2014) BGR has leaked images of what could be Amazon's smartphone. The outlet's been right about Amazon leaks before. Sources expect an announcement in June. Video provided by Newsy
Powered by NewsLook.com
The Walking, Talking Oil-Drigging Rig

The Walking, Talking Oil-Drigging Rig

Reuters - Business Video Online (Apr. 15, 2014) Pennsylvania-based Schramm is incorporating modern technology in its next generation oil-drigging rigs, making them smaller, safer and smarter. Ernest Scheyder reports. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins