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 (.pdf). Information about how to obtain the software is at
http://vlsicad.eecs.umich.edu/BK/SAUCY/ .
Source: University of Michigan
Related stories:
Study Finds New Properties in Non-Magnetic Materials
A team of Penn State researchers has shown for the first time that the entire class of non-magnetic materials, such as those used in some computer components, could have considerably more uses than scientists had thought. The findings are important because they reveal previously unknown information about the structure of these materials, expanding the number of properties that they potentially could have. A material's properties, such as electrical conductivity and mechanical strength, are what determine its usefulness. The research will be published in the journal
Physical Review Letters.
Mathematicians Reveal Secrets of the Ancient and Universal Art of Symmetry
Humans have used symmetrical patterns for thousands of years in both functional and decorative ways. Now, a new book by three mathematicians offers both math experts and enthusiasts a new way to understand symmetry and a fresh way to see the world.
The new shape of music: Music has its own geometry, researchers find
The connection between music and mathematics has fascinated scholars for centuries. More than 200 years ago Pythagoras reportedly discovered that pleasing musical intervals could be described using simple ratios.
Perfect symmetry -- explaining the patterns in everyday life
The secrets of symmetry found in nature, art, music and architecture were the focus of a special lecture at Imperial College London this week, delivered by renowned Oxford mathematician, Dr Marcus du Sautoy.
Scientists discover possible cosmic defect, remnant from Big Bang
Scientists from the Institute of Physics of Cantabria (IFCA) and the University of Cambridge may have discovered an example of a cosmic defect, a remnant from the Big Bang called a texture. If confirmed, their discovery, reported today in
Science, will provide dramatic new insight into how the universe evolved following the Big Bang.
A Two-Time Universe? Physicist Explores How Second Dimension of Time Could Unify Physics Laws
For a long time, Itzhak Bars has been studying time. More than a decade ago, the USC College physicist began pondering the role time plays in the basic laws of physics — the equations describing matter, gravity and the other forces of nature.
Congress Commends UM-Led Math Team's Breakthrough E8 Calculation
A major mathematical breakthrough by a team of 18 scientists, led by University of Maryland mathematician Jeffrey Adams, has been commended by Congress, one week after the work
made international headlines when it was announced by the American Institute of Mathematics (AIM), one of the leading math institutes in the U.S.
Mathematicians solve E8 structure (Update)
A transatlantic team of number-crunchers announced they had built a theoretical structure in 248 dimensions, resolving a 120-year puzzle that could be used to test theories about the structure of the cosmos.