'Saucy' Software Updates Finds Symmetries Dramatically Faster
University of Michigan News Service (06/10/08) Moore, Nicole Casal
University of Michigan computer scientists have developed open-source software that reduces the time it takes to find symmetries in complicated equations from days to a few seconds. Finding symmetries can reveal shortcuts to answers that, for example, verify the safety of train schedules, find bugs in software and hardware designs, or improve common search queries. The algorithm updates a program called "saucy" that the researchers developed in 2004. The software's applications include artificial intelligence and logistics. In complicated equations, symmetries reveal repeated branches of the search for solutions that only need to be solved once. Current programs that search for symmetries can take days to find results, even if no instances are found. The new method can finish in seconds even if there are millions of variables. An artificial intelligence capable of recognizing symmetries could quickly help a computer generate a plan or an optimal schedule, and the computer would know when the order of tasks was interchangeable. The algorithm converts a complicated equation into a graph and searches for similarities in the arrangement of the vertices. It narrows the search while exploiting "sparsity," or the fact that almost every node on the graph is connected to a few other nodes. Other symmetries can be derived from sparse symmetries, and the number of distinct symmetries can grow exponentially with the size of the system.
Click Here to View Full Article
No comments:
Post a Comment