'Saucy' software update finds symmetries dramatically faster

June 10, 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.um … ac08-sym.pdf (.pdf). Information about how to obtain the software is at http://vlsicad.eecs.umich.edu/BK/SAUCY/ .

Source: University of Michigan

4.8 /5 (20 votes)  

Rank 4.8 /5 (20 votes)
Tags

Relevant PhysicsForums posts

More news stories

US video game sales fall 34 percent in January

(AP) -- U.S. retail sales of video game hardware, software and accessories fell 34 percent in January from a year earlier to $751 million due to the lack of new game titles, according to market researcher NPD Group.

Technology / Business

created 16 minutes ago | popularity not rated yet | comments 0

Soraa LED light may dim 50-watt halogen rivals

(PhysOrg.com) -- Soraa, a Fremont, California company founded in 2008, this week launched its first product, a light that uses LEDS (light emitting diodes). The "Soraa LED MR16 lamp" is the "perfect" replacement ...

Technology / Semiconductors

created 23 hours ago | popularity 4.3 / 5 (18) | comments 18 | with audio podcast report

Samsung can continue selling Galaxy tabs in Germany: court

South Korea's Samsung Electronics can continue to sell its Galaxy Tab 10.1N tablet computer in Germany, a German court ruled Thursday, rejecting a bid by arch-rival Apple to have them banned.

Technology / Business

created 21 hours ago | popularity 4 / 5 (4) | comments 3

Digital photos could put kids at risk

A study published in the International Journal of Electronic Security and Digital Forensics this month suggests that parents and carers could be putting children at risk if they upload digital photos that are automatically "geota ...

Technology / Internet

created 17 hours ago | popularity 5 / 5 (1) | comments 3

Google launches Chrome browser for Android smartphones

With more and more people connecting to the Internet through a phone or a tablet instead of a PC, Google Inc. is bringing its fast-growing browser, Chrome, to the newest Android-powered mobile devices.

Technology / Software

created 20 hours ago | popularity 5 / 5 (5) | comments 0


Japan scientist makes 'Avatar' robot

A Japanese-developed robot that mimics the movements of its human controller is bringing the Hollywood blockbuster "Avatar" one step closer to reality.

Fighting crimes against biodiversity: How to catch a killer weed

Invasive species which have the potential to destroy biodiversity and influence global change could be tracked and controlled in the same way as wanted criminals, according to new research from Queen Mary, University of London.

Metastatic breast cancer hitches a free ride from the immune system

Inflammatory breast cancer (IBC) is the most lethal form of breast cancer . It spreads easily through the lymphatic and blood vessels, forming metastasis which can lead to multi-organ failure. New research published in BioMed ...

A novel method for simultaneously measuring blood pressure and arterial stiffness

Arterial stiffness due to is a major contributor to cardiovascular disease but is very difficult to measure. It also can influence blood pressure readings since these rely on the time taken for arteries to return to normal ...

India's global pharmacy role threatened by EU pact

(AP) -- Efforts by India and the European Union to strengthen trade are threatening India's ability to deliver lifesaving medicines to the world's poorest, analysts say as the two sides push through protracted ...

Study finds that red blood cell transfusion decreases fatigue in women with acute postpartum anemia

In a study to be presented today at the Society for Maternal-Fetal Medicine's annual meeting, The Pregnancy Meeting ™, in Dallas, Texas, researchers will report findings that show that in women with acute postpartum ...