'Saucy' software finds symmetries in complicated equations within seconds

Washington, June 11 : Computer scientists at the University of Michigan say that they have updated software called 'saucy' to enable it to find symmetries in complicated equations within seconds in some cases.

The researchers point out that finding symmetries is a way to highlight shortcuts to answers that verify the safety of train schedules, identify bugs in software and hardware designs, speed up common search tasks, and so forth.

Igor Markov, associate professor in the Department of Electrical Engineering and Computer Science, said that the software's applications extended to artificial intelligence and logistics.

He also said that the software could speed up solutions to fundamental computer science problems, and quickly solve what is 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," he said.

According to him, symmetries are interchangeable options that lead to the same outcome, and that in complicated equations, they point to repeated branches of the search for solutions that only need to be figured out once.

Paul Darga, a graduate student in the Department of Electrical Engineering and Computer Science, said that current programs that look for symmetries could take days to give results even when they found no instances.

However, the new method could finish the task in seconds even when there were millions of variables, he added.

Markov explained how finding symmetries could simplify equations with the help of the pigeonhole principle, saying that one could not fit 10 birds in nine pigeonholes.

He said that the particular problem had a nine-fold symmetry because it did not matter which hole each bird would occupy, and that one would always end up homeless.

It also has a 10-fold symmetry because the birds are considered interchangeable, he added.

"If you ask a computer to put 20 trains on 19 tracks, this computation may take forever. But if you use an approach with symmetry breaking, these cases can be solved in seconds," Markov said.

The researchers say that symmetry breaking in train scheduling and logistics could help figure the shortest itineraries, and in artificial intelligence, the ability to recognize symmetries quickly could help a computer generate a plan or an optimal schedule.

A presentation on the algorithm was made on June 10 at the Design Automation Conference in Anaheim, California.

ANI