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:
Nicole Casal Moore | alfa
Study suggests buried Internet infrastructure at risk as sea levels rise
18.07.2018 | University of Wisconsin-Madison
Microscopic trampoline may help create networks of quantum computers
17.07.2018 | University of Colorado at Boulder
For the first time ever, scientists have determined the cosmic origin of highest-energy neutrinos. A research group led by IceCube scientist Elisa Resconi, spokesperson of the Collaborative Research Center SFB1258 at the Technical University of Munich (TUM), provides an important piece of evidence that the particles detected by the IceCube neutrino telescope at the South Pole originate from a galaxy four billion light-years away from Earth.
To rule out other origins with certainty, the team led by neutrino physicist Elisa Resconi from the Technical University of Munich and multi-wavelength...
For the first time a team of researchers have discovered two different phases of magnetic skyrmions in a single material. Physicists of the Technical Universities of Munich and Dresden and the University of Cologne can now better study and understand the properties of these magnetic structures, which are important for both basic research and applications.
Whirlpools are an everyday experience in a bath tub: When the water is drained a circular vortex is formed. Typically, such whirls are rather stable. Similar...
Physicists working with Roland Wester at the University of Innsbruck have investigated if and how chemical reactions can be influenced by targeted vibrational excitation of the reactants. They were able to demonstrate that excitation with a laser beam does not affect the efficiency of a chemical exchange reaction and that the excited molecular group acts only as a spectator in the reaction.
A frequently used reaction in organic chemistry is nucleophilic substitution. It plays, for example, an important role in in the synthesis of new chemical...
Optical spectroscopy allows investigating the energy structure and dynamic properties of complex quantum systems. Researchers from the University of Würzburg present two new approaches of coherent two-dimensional spectroscopy.
"Put an excitation into the system and observe how it evolves." According to physicist Professor Tobias Brixner, this is the credo of optical spectroscopy....
Ultra-short, high-intensity X-ray flashes open the door to the foundations of chemical reactions. Free-electron lasers generate these kinds of pulses, but there is a catch: the pulses vary in duration and energy. An international research team has now presented a solution: Using a ring of 16 detectors and a circularly polarized laser beam, they can determine both factors with attosecond accuracy.
Free-electron lasers (FELs) generate extremely short and intense X-ray flashes. Researchers can use these flashes to resolve structures with diameters on the...
13.07.2018 | Event News
12.07.2018 | Event News
03.07.2018 | Event News
18.07.2018 | Materials Sciences
18.07.2018 | Life Sciences
18.07.2018 | Health and Medicine