Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

'Saucy' Software Update Finds Symmetries Dramatically Faster

13.06.2008
Computer scientists at the University of Michigan developed open-source software that cuts the time to find symmetries in complicated equations from days to seconds in some cases.

Finding symmetries is a way to highlight shortcuts to answers that, for example, verify the safety of train schedules, identify bugs in software and hardware designs, or speed up common search tasks.

The algorithm is an update to software called "saucy" that the researchers developed in 2004 and shared with colleagues. Paul Darga, a graduate student in the Department of Electrical Engineering and Computer Science, will present the algorithm on June 10 at the Design Automation Conference in Anaheim, Calif. Darga's co-authors are Igor Markov, associate professor in the Department of Electrical Engineering and Computer Science, and Karem Sakallah, a professor in the same department.

The software's applications extend to artificial intelligence and logistics.It speeds up solutions to fundamental computer science problems and quickly solves what's called the graph automorphism problem. "Our new algorithm solves the graph automorphism problem so quickly in real-life applications that the problem is starting to look easy," Markov said.

Symmetries are, in a sense, interchangeable options that lead to the same outcome. In complicated equations, symmetries point to repeated branches of the search for solutions that only need to be figured out once. Current programs that look for symmetries can take days to give results even when they find no instances, Darga said. The new method finishes in seconds even when there are millions of variables.

To illustrate how finding symmetries can simplify equations, Markov pointed to the pigeonhole principle. This says you can't, for example, fit 10 birds in nine pigeonholes (unless they share.) The particular problem has a nine-fold symmetry because it doesn't matter which hole each bird occupies. One will always end up homeless. It also has a 10-fold symmetry because the birds are considered interchangeable.

"If you ask a computer to put 20 trains on 19 tracks, this computation may take forever," Markov said. "But if you use an approach with symmetry breaking, these cases can be solved in seconds."

Symmetry breaking in train scheduling and logistics can also help figure the shortest itineraries. In artificial intelligence, the ability to recognize symmetries quickly could help a computer generate a plan or an optimal schedule. The computer would know when the order of tasks was interchangeable.

The new algorithm starts working in the same way as existing symmetry breaking software. It converts the complicated equation into a graph and looks for similarities in the arrangement of the vertices. Like the original version of saucy, it narrows the search while exploiting what Darga calls "sparsity"---the fact that almost every node on the graph is only connected to a few other nodes.

The saucy update recognizes that it's not just the node connections that are sparse. It turns out that most important symmetries themselves are sparse too, in that they involve only several nodes at a time. Other symmetries can be derived from sparse symmetries, and the number of distinct symmetries can grow exponentially with the size of the system.

"Just like snowflakes, many interconnected systems in technology and nature are sparse and exhibit structural symmetries," Sakallah said. "The internet connectivity graph we worked with reminds me of a giant snowflake. It has a quarter million vertices and half a million edges, but it exhibits more symmetries than there are electrons in the universe."

In less than a half-second, the new software captured 1083,687 different symmetries in an Internet connectivity graph of routers around the world. A symmetry in this graph signifies a way the routers could be shuffled that wouldn't change the operation.

Previous methods timed out in the 30 minutes they were given to generate results in these experiments. Darga said it would take these older programs days to solve such a complicated problem. In searching for symmetries in the road networks between cities and towns in Illinois, the new algorithm captured the 104,843 symmetries in less than a half-second, whereas the most robust previous algorithm took 16 minutes.

The paper is called "Faster Symmetry Discovery Using Sparsity of Symmetries." It is available at http://www.eecs.umich.edu/~imarkov/pubs/conf/dac08-sym.pdf. Information about how to obtain the software is at http://vlsicad.eecs.umich.edu/BK/SAUCY/.

For more information:
Paul Darga: http://www.eecs.umich.edu/~pdarga
Igor Markov: http://www.eecs.umich.edu/~imarkov
Karem Sakallah: http://www.eecs.umich.edu/~karem
Design Automation Conference: http://www.dac.com/45th/index.aspx
Michigan Engineering:
The University of Michigan College of Engineering is ranked among the top engineering schools in the country. At more than $130 million annually, its engineering research budget is one of largest of any public university. Michigan Engineering is home to 11 academic departments and a National Science Foundation Engineering Research Center. The college plays a leading role in the Michigan Memorial Phoenix Energy Institute and hosts the world class Lurie Nanofabrication Facility. Michigan Engineering's premier scholarship, multidisciplinary scope and international scale combine to create The Michigan Difference.

Nicole Casal Moore | alfa
Further information:
http://www.engin.umich.edu

More articles from Information Technology:

nachricht NASA CubeSat to test miniaturized weather satellite technology
10.11.2017 | NASA/Goddard Space Flight Center

nachricht New approach uses light instead of robots to assemble electronic components
08.11.2017 | The Optical Society

All articles from Information Technology >>>

The most recent press releases about innovation >>>

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

Im Focus: Nanoparticles help with malaria diagnosis – new rapid test in development

The WHO reports an estimated 429,000 malaria deaths each year. The disease mostly affects tropical and subtropical regions and in particular the African continent. The Fraunhofer Institute for Silicate Research ISC teamed up with the Fraunhofer Institute for Molecular Biology and Applied Ecology IME and the Institute of Tropical Medicine at the University of Tübingen for a new test method to detect malaria parasites in blood. The idea of the research project “NanoFRET” is to develop a highly sensitive and reliable rapid diagnostic test so that patient treatment can begin as early as possible.

Malaria is caused by parasites transmitted by mosquito bite. The most dangerous form of malaria is malaria tropica. Left untreated, it is fatal in most cases....

Im Focus: A “cosmic snake” reveals the structure of remote galaxies

The formation of stars in distant galaxies is still largely unexplored. For the first time, astron-omers at the University of Geneva have now been able to closely observe a star system six billion light-years away. In doing so, they are confirming earlier simulations made by the University of Zurich. One special effect is made possible by the multiple reflections of images that run through the cosmos like a snake.

Today, astronomers have a pretty accurate idea of how stars were formed in the recent cosmic past. But do these laws also apply to older galaxies? For around a...

Im Focus: Visual intelligence is not the same as IQ

Just because someone is smart and well-motivated doesn't mean he or she can learn the visual skills needed to excel at tasks like matching fingerprints, interpreting medical X-rays, keeping track of aircraft on radar displays or forensic face matching.

That is the implication of a new study which shows for the first time that there is a broad range of differences in people's visual ability and that these...

Im Focus: Novel Nano-CT device creates high-resolution 3D-X-rays of tiny velvet worm legs

Computer Tomography (CT) is a standard procedure in hospitals, but so far, the technology has not been suitable for imaging extremely small objects. In PNAS, a team from the Technical University of Munich (TUM) describes a Nano-CT device that creates three-dimensional x-ray images at resolutions up to 100 nanometers. The first test application: Together with colleagues from the University of Kassel and Helmholtz-Zentrum Geesthacht the researchers analyzed the locomotory system of a velvet worm.

During a CT analysis, the object under investigation is x-rayed and a detector measures the respective amount of radiation absorbed from various angles....

Im Focus: Researchers Develop Data Bus for Quantum Computer

The quantum world is fragile; error correction codes are needed to protect the information stored in a quantum object from the deteriorating effects of noise. Quantum physicists in Innsbruck have developed a protocol to pass quantum information between differently encoded building blocks of a future quantum computer, such as processors and memories. Scientists may use this protocol in the future to build a data bus for quantum computers. The researchers have published their work in the journal Nature Communications.

Future quantum computers will be able to solve problems where conventional computers fail today. We are still far away from any large-scale implementation,...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

Ecology Across Borders: International conference brings together 1,500 ecologists

15.11.2017 | Event News

Road into laboratory: Users discuss biaxial fatigue-testing for car and truck wheel

15.11.2017 | Event News

#Berlin5GWeek: The right network for Industry 4.0

30.10.2017 | Event News

 
Latest News

Corporate coworking as a driver of innovation

22.11.2017 | Business and Finance

PPPL scientists deliver new high-resolution diagnostic to national laser facility

22.11.2017 | Physics and Astronomy

Quantum optics allows us to abandon expensive lasers in spectroscopy

22.11.2017 | Physics and Astronomy

VideoLinks
B2B-VideoLinks
More VideoLinks >>>