Researchers develop mathematical solver for analog computers

December 12, 2018

Your computer performs most tasks well. For word processing, certain computations, graphic arts and web surfing, the digital box on your desk is the best tool for the job. But the way your computer works, with its style of mathematics that relies on the binary code system of "on" and "off" 1s and 0s, isn't ideal for solving every problem.

That's why researchers such as Zoltán Toroczkai, professor in the Department of Physics and concurrent professor in the Department of Computer Science and Engineering at the University of Notre Dame, are interested in reviving analog computing at a time when digital computing has reached its maximum potential.

Toroczkai and collaborators have been working toward developing a novel mathematical approach that will help advance computation beyond the digital framework. His most recent paper, published in Nature Communications, describes a new mathematical, analog "solver" that can potentially find the best solution to NP-hard problems.

NP-hardness is a theory of computational complexity, with problems that are famous for their difficulty. When the number of variables is large, problems associated with scheduling, protein folding, bioinformatics, medical imaging and many other areas are nearly unsolvable with known methods. After testing their new method on a variety of NP-hard problems, the researchers concluded their solver has the potential to lead to better, and possibly faster, solutions than can be computed digitally.

Analog computers were used to predict tides from the early to mid-20th century, guide weapons on battleships and launch NASA's first rockets into space. They first used gears and vacuum tubes, and later, transistors, that could be configured to solve problems with a range of variables. They perform mathematical functions directly. For instance, to add 5 and 9, analog computers add voltages that correspond to those numbers, and then instantly obtain the correct answer. However, analog computers were cumbersome and prone to "noise" -- disturbances in the signals -- and were difficult to re-configure to solve different problems, so they fell out of favor.

Digital computers emerged after transistors and integrated circuits were reliably mass produced, and for many tasks they are accurate and sufficiently flexible. Computer algorithms, in the form of software, are sets of instructions that tell the computer hardware how to perform. Because the process is restricted to the use of 0s and 1s, this also makes their programming simpler, and allowed digital computing to dominate for nearly 70 years.

However, their restrictions may prevent digital computers from solving NP-hard problems with many variables. One such problem is the "Traveling Salesman" problem, in which a salesperson must start in one city and return to that city at the end of a trip, but in between, must travel to all the different cities on a list. What's the most efficient route among all the points? The problem becomes exponentially more challenging with the addition of more cities. The difficulty with such optimization problems, Toroczkai noted, is "while you can always come up with some answer, you cannot determine if it's optimal. Determining that there isn't a better solution is just as hard as the problem itself."

A challenge for analog computing rests with the design of continuous algorithms. Unlike digital computing, which has a long history in algorithm development, algorithms for analog computers lack a similar knowledge base and thus are very difficult to design. Toroczkai's approach is different from the types of algorithms for digital computers, in all aspects.

The next step is to design and build devices based on this approach, a process that will be tackled within Notre Dame's College of Engineering. The analog computers would be built for specific tasks, and not for everyday computing needs. This work is part of a larger-scale, multi-institutional effort, called Extremely Energy Efficient Collective Electronics (EXCEL), led by Notre Dame's Suman Datta, Freimann Chair of Engineering and professor of electrical engineering, in collaboration with Sharon Hu, professor of computer science and engineering.

"There are mostly engineering problems that need to be solved at this point, such as spurious capacities and better noise control, but it's going to get there," Toroczkai said. "Ideally I would like to see that you have this box on your desk that is your scheduler. And it is going to do much better of a job than your regular computer."
For this research, Toroczkai collaborated with Maria Ercsey-Ravasz from Babes-Bolyai University in Romania and their teams. Toroczkai's work was funded by the National Science Foundation and by the Nanoelectronics Research Corporation. The EXCEL effort is funded by the NSF and industry partners.

University of Notre Dame

Related Engineering Articles from Brightsurf:

Re-engineering antibodies for COVID-19
Catholic University of America researcher uses 'in silico' analysis to fast-track passive immunity

Next frontier in bacterial engineering
A new technique overcomes a serious hurdle in the field of bacterial design and engineering.

COVID-19 and the role of tissue engineering
Tissue engineering has a unique set of tools and technologies for developing preventive strategies, diagnostics, and treatments that can play an important role during the ongoing COVID-19 pandemic.

Engineering the meniscus
Damage to the meniscus is common, but there remains an unmet need for improved restorative therapies that can overcome poor healing in the avascular regions.

Artificially engineering the intestine
Short bowel syndrome is a debilitating condition with few treatment options, and these treatments have limited efficacy.

Reverse engineering the fireworks of life
An interdisciplinary team of Princeton researchers has successfully reverse engineered the components and sequence of events that lead to microtubule branching.

New method for engineering metabolic pathways
Two approaches provide a faster way to create enzymes and analyze their reactions, leading to the design of more complex molecules.

Engineering for high-speed devices
A research team from the University of Delaware has developed cutting-edge technology for photonics devices that could enable faster communications between phones and computers.

Breakthrough in blood vessel engineering
Growing functional blood vessel networks is no easy task. Previously, other groups have made networks that span millimeters in size.

Next-gen batteries possible with new engineering approach
Dramatically longer-lasting, faster-charging and safer lithium metal batteries may be possible, according to Penn State research, recently published in Nature Energy.

Read More: Engineering News and Engineering Current Events is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to