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 ETRI exchanged quantum information on daylight in a free-space quantum key distribution
10.12.2018 | National Research Council of Science & Technology

nachricht Three components on one chip
06.12.2018 | Universität Stuttgart

All articles from Information Technology >>>

The most recent press releases about innovation >>>

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

Im Focus: Researchers develop method to transfer entire 2D circuits to any smooth surface

What if a sensor sensing a thing could be part of the thing itself? Rice University engineers believe they have a two-dimensional solution to do just that.

Rice engineers led by materials scientists Pulickel Ajayan and Jun Lou have developed a method to make atom-flat sensors that seamlessly integrate with devices...

Im Focus: Three components on one chip

Scientists at the University of Stuttgart and the Karlsruhe Institute of Technology (KIT) succeed in important further development on the way to quantum Computers.

Quantum computers one day should be able to solve certain computing problems much faster than a classical computer. One of the most promising approaches is...

Im Focus: Substitute for rare earth metal oxides

New Project SNAPSTER: Novel luminescent materials by encapsulating phosphorescent metal clusters with organic liquid crystals

Nowadays energy conversion in lighting and optoelectronic devices requires the use of rare earth oxides.

Im Focus: A bit of a stretch... material that thickens as it's pulled

Scientists have discovered the first synthetic material that becomes thicker - at the molecular level - as it is stretched.

Researchers led by Dr Devesh Mistry from the University of Leeds discovered a new non-porous material that has unique and inherent "auxetic" stretching...

Im Focus: The force of the vacuum

Scientists from the Theory Department of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science (CFEL) in Hamburg have shown through theoretical calculations and computer simulations that the force between electrons and lattice distortions in an atomically thin two-dimensional superconductor can be controlled with virtual photons. This could aid the development of new superconductors for energy-saving devices and many other technical applications.

The vacuum is not empty. It may sound like magic to laypeople but it has occupied physicists since the birth of quantum mechanics.

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

New Plastics Economy Investor Forum - Meeting Point for Innovations

10.12.2018 | Event News

EGU 2019 meeting: Media registration now open

06.12.2018 | Event News

Expert Panel on the Future of HPC in Engineering

03.12.2018 | Event News

 
Latest News

Small but ver­sat­ile; key play­ers in the mar­ine ni­tro­gen cycle can util­ize cy­anate and urea

10.12.2018 | Life Sciences

New method gives microscope a boost in resolution

10.12.2018 | Physics and Astronomy

Carnegie Mellon researchers probe hydrogen bonds using new technique

10.12.2018 | Life Sciences

VideoLinks
Science & Research
Overview of more VideoLinks >>>