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 Supercomputing the emergence of material behavior
18.05.2018 | University of Texas at Austin, Texas Advanced Computing Center

nachricht Keeping a Close Eye on Ice Loss
18.05.2018 | Alfred-Wegener-Institut, Helmholtz-Zentrum für Polar- und Meeresforschung

All articles from Information Technology >>>

The most recent press releases about innovation >>>

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

Im Focus: LZH showcases laser material processing of tomorrow at the LASYS 2018

At the LASYS 2018, from June 5th to 7th, the Laser Zentrum Hannover e.V. (LZH) will be showcasing processes for the laser material processing of tomorrow in hall 4 at stand 4E75. With blown bomb shells the LZH will present first results of a research project on civil security.

At this year's LASYS, the LZH will exhibit light-based processes such as cutting, welding, ablation and structuring as well as additive manufacturing for...

Im Focus: Self-illuminating pixels for a new display generation

There are videos on the internet that can make one marvel at technology. For example, a smartphone is casually bent around the arm or a thin-film display is rolled in all directions and with almost every diameter. From the user's point of view, this looks fantastic. From a professional point of view, however, the question arises: Is that already possible?

At Display Week 2018, scientists from the Fraunhofer Institute for Applied Polymer Research IAP will be demonstrating today’s technological possibilities and...

Im Focus: Explanation for puzzling quantum oscillations has been found

So-called quantum many-body scars allow quantum systems to stay out of equilibrium much longer, explaining experiment | Study published in Nature Physics

Recently, researchers from Harvard and MIT succeeded in trapping a record 53 atoms and individually controlling their quantum state, realizing what is called a...

Im Focus: Dozens of binaries from Milky Way's globular clusters could be detectable by LISA

Next-generation gravitational wave detector in space will complement LIGO on Earth

The historic first detection of gravitational waves from colliding black holes far outside our galaxy opened a new window to understanding the universe. A...

Im Focus: Entangled atoms shine in unison

A team led by Austrian experimental physicist Rainer Blatt has succeeded in characterizing the quantum entanglement of two spatially separated atoms by observing their light emission. This fundamental demonstration could lead to the development of highly sensitive optical gradiometers for the precise measurement of the gravitational field or the earth's magnetic field.

The age of quantum technology has long been heralded. Decades of research into the quantum world have led to the development of methods that make it possible...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

Save the date: Forum European Neuroscience – 07-11 July 2018 in Berlin, Germany

02.05.2018 | Event News

Invitation to the upcoming "Current Topics in Bioinformatics: Big Data in Genomics and Medicine"

13.04.2018 | Event News

Unique scope of UV LED technologies and applications presented in Berlin: ICULTA-2018

12.04.2018 | Event News

 
Latest News

Designer cells: artificial enzyme can activate a gene switch

22.05.2018 | Life Sciences

PR of MCC: Carbon removal from atmosphere unavoidable for 1.5 degree target

22.05.2018 | Earth Sciences

Achema 2018: New camera system monitors distillation and helps save energy

22.05.2018 | Trade Fair News

VideoLinks
Science & Research
Overview of more VideoLinks >>>