The University of MichiganNews Services
The University Record Online
search
Updated 11:00 AM June 30, 2008
 

front

accolades

briefs

view events

submit events

UM employment


obituaries
police beat
regents round-up
research reporter
letters


archives

Advertise with Record

contact us
meet the staff
contact us
contact us

 
'Saucy' software update finds symmetries dramatically faster

Computer scientists have 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, presented the algorithm 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 says.

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 says. The new method finishes in seconds even when there are millions of variables.

Symmetry breaking in train scheduling and logistics can 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 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 says. "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."

The paper is called "Faster Symmetry Discovery Using Sparsity of Symmetries."

More Stories