The Algebraic Revolution: Solving for Chocolate

Nigel Boston
Nigel Boston

Change is often the force that drives science forward, enabling big leaps and discoveries. There is a change happening right now in how some scientists are finding solutions to problems with UW-Madison and WID right at the center. Nigel Boston, Professor of Mathematics and of Electrical and Computer Engineering and collaborator in the Optimization theme at WID, is helping to bring applied algebra to a broad range of disciplines with help from a Research Training Grant from the National Science Foundation.

Robert Nowak
Rob Nowak

Algebra isn’t new, but finding new ways to apply it could result in big gains for all kinds of researchers. “Algebraic methods have played an important role in certain areas of engineering and computer science, particularly in what’s called coding theory,” says Rob Nowak, a faculty member in the Optimization theme. “That’s a place where there’s always been a lot of points of contact between pure algebra, mathematics, and applied engineering and computer science. Outside of that, there’s been less contact between algebra and other areas.” But the relationship between algebra and other disciplines may be on the brink of dramatic change.

Applying algebra in engineering and computer science has a number of advantages and can help solve a great host of problems, from helping Netflix give you better recommendations for what to watch tonight to keeping an airplane in the air. Expanding the use of algebra is a relatively new movement with promising implications.

The Netflix Problem is just one example of where algebra plays a key role. “The idea is you have some sparse data — like with Netflix you have ‘These people recommend these movies,’ but obviously not everyone recommends every movie, so you want to try and fill in the gaps in the table,” says Boston. Filling in those gaps requires advanced algebraic methods.

The problem isn’t unique to Netflix, or even to a single discipline. “Bringing algebra to bear on problems in engineering and computer science has implications for all the sciences because all the sciences use data analysis methods,” says Nowak. “Whenever you are measuring things in the real world, whether it’s a biology experiment or you have a bunch of sensors monitoring the power grid, it’s almost always the case that you don’t get all of the data that you wished you could have gotten — data gets lost, sensors fail, experiments get contaminated.” Using algebra to fill in the gaps makes it possible to make meaningful progress even with limited data.

Boston has also had success applying algebra to problems in control theory, an area of engineering and mathematics that deals with dynamical systems, including their stability and controllability. An example of control theory in action is an airplane: a controller receives feedback from sensors to constantly make tiny adjustments to modulate movement of the throttle, flaps, and other systems to keep the plane in control and in the air.

Simple control loop
A simple representation of a control loop

A famous problem in control theory and optimization dubbed the Belgian Chocolate Problem – so named by Belgian mathematician Vincent Blondel, who proposed the problem and offered a kilogram of chocolate to whoever could solve it – has been a subject of Boston’s fascination for years. The problem involves finding the largest parameter value (known as δ) for which simultaneous stabilization of three plants, or components of a control system, is possible. This problem is especially challenging because the plants operate in conjunction and as you stabilize one plant, the others become destabilized.

A series of researchers have provided progressively larger solutions, but Boston and his graduate student, Zach Charles, have defined a new algebraic approach. Says Boston, “traditionally, engineers use complex analysis and probability theory — they haven’t really used algebra so much. What happens in the engineering approach is you can keep nudging up this parameter. In our method, we figure out that what this parameter is tending towards is not just a random thing, it is something with very nice properties. You can characterize it algebraically and solve for it that way.” So instead of moving incrementally toward the best solution, Boston and Charles can use algebra to describe the optimal solution. Indeed, the researchers now hold the world record δ. As Boston describes, “we spoil the fun and we find out what you’re heading towards. This one paper replaces lots of papers.”

The grant from NSF will allow researchers to continue enlisting algebra to solve a variety of problems in a wider array of disciplines. Boston is the Principal Investigator, but the grant includes several other faculty, providing $2 million over the next five years to fund new research positions and applied algebra conferences together with other activity in number theory and algebraic geometry. As algebraic approaches gain more traction, Boston hopes to use the grant to keep UW-Madison on the front lines of the growing domain.

“You have to get enough people on board to make change happen. I think they’ll see what we’re doing, they’ll see it working at Wisconsin, and it will spread.”

— Nigel Boston

“The idea of algebra is very clean. Communications, coding theory, and cryptography use a lot of algebra; more and more, computer scientists and engineers are having to learn some algebra. But there are so many other applications – we could be at the start of some movement” says Boston.

That movement is growing. Boston, together with collaborator Shamgar Gurevich, has already organized two applied algebra conferences hosted by WID and attended by researchers from top institutions, including Princeton, Berkeley, and MIT. As Boston says, “I think we can provide a model that we can export to other places as well. The top places are looking for something new and something powerful. These conferences should put UW front and center as regards this movement.” The NSF award will allow for formative conferences, influential visitors and the hiring of premier postdoctoral researchers.

When writing the grant application, Boston pointed to the interdisciplinary nature of UW-Madison, and WID in particular, as great incubators of innovation. “There are a lot of people doing very good math here, and the idea is we can improve on that and have more students and more faculty involved,” says Boston. Reviewers agreed that UW is the right place for the ambitious work laid out in the grant, and that Wisconsin could be a leader in applied algebra.

Boston is committed to fulfilling that role and continues to expand the influence of algebra across academia. As he says, “you have to get enough people on board to make change happen. I think they’ll see what we’re doing, they’ll see it working at Wisconsin, and it will spread.”

— Nolan Lendved