Jared L. Aurentz, Thomas Mach, Raf Vandebril, and David S. Watkins received the SIAM Outstanding Paper Prize at the 2017 SIAM Annual Meeting. They were recognized for their paper, “Fast and Backward Stable Computation of Roots of Polynomials,” published in SIAM Journal on Matrix Analysis and Applications, Volume 36, Issue 3 (2015).
The SIAM Outstanding Paper Prizes are awarded annually to the authors of the three most outstanding papers, in the opinion of the selection committee, published in SIAM journals in the three calendar years preceding the year before the award year. Priority is given to papers that bring a fresh look at an existing field or that open up new areas of applied mathematics.
Jared Aurentz completed his PhD with David Watkins at Washington State University in 2014. By then, the collaboration with Raf Vandebril and Thomas Mach was already well underway. He is currently a postdoctoral fellow at the Instituto de Ciencias Matemáticas in Madrid.
Thomas Mach is currently an assistant professor of mathematics at Nazarbayev University in Astana, Kazakhstan. At the time the paper was written, he was a postdoctoral fellow at Katholieke Universiteit Leuven. He completed his PhD in 2012 at Technische Universitaet Chemnitz.
Raf Vandebril is a professor in the Department of Computer Science at Katholieke Universiteit Leuven. In 2012, he began collaborating with David Watkins on core chasing algorithms.
David Watkins has been publishing papers, mostly about eigenvalue computation, in SIAM journals for more than 40 years. He is a professor emeritus of mathematics at Washington State University.
Q: Why are you excited about winning the prize?
A: The paper and the algorithms that it describes had a long gestation period. After its shaky beginnings in experimental MATLAB code, it was gradually made better by a sequence of improvements. There were times when we felt like giving up, but each new problem was eventually solved by one or another of us. This was truly a team effort. In the end we had a powerful algorithm that performed better than we could have hoped. Once we had such a good algorithm, another challenge was to explain why it works so well, and this also turned out to be a team effort.
By the time we submitted the paper for publication, each of us felt that this was some of the best work we had ever done. It was therefore highly gratifying to learn that other people thought so too, as indicated by this prize.
Q: Could you tell us a bit about the research that won you the prize?
A: Many years ago Cleve Moler installed in MATLAB a command called roots that computes the zeros of a polynomial by finding the eigenvalues of its companion matrix. Cleve remarked at that time that his method might not be the most efficient algorithm for the problem as it required O(n2) storage space and O(n3) computations for an nth degree polynomial. It ought to be possible to bring the storage down to O(n) and the computations down to O(n2). Our research solved that problem. We weren’t the first to do it, but our algorithm was the first to be shown to be backward stable. It is also significantly faster than the other fast companion eigenvalue methods that have been proposed.
Algorithms for structured matrices have to preserve the structure. Previous attempts at a structured algorithm for the companion eigenvalue problem projected the iterates back to the desired structure, thereby introducing small, but noticeable, additional errors. We succeeded in encoding the structure differently, using only unitary matrices. Thus we were able to create an algorithm that preserves the structure without any projections.
Our work is not yet finished. Recently we (with an additional collaborator, Leonardo Robol) have been able to strengthen our stability analysis. We now know that our algorithm is backward stable in an even stronger sense than MATLAB’s roots command. Thus our method is not only faster, it is also more accurate. This work has been submitted for publication.
We are in the final stages of writing a monograph, Core Chasing Algorithms for the Eigenvalue Problem, that will present a unified treatment of our prize-winning paper and related work that we have done in the past few years. We expect it to be published in 2018.
Q: What does your research mean to the public?
A: This is a contribution to the infrastructure of science. If, as we hope, our new algorithm is incorporated into popular software packages, scientists and engineers will benefit from our faster and more accurate algorithm, and most of them won’t even know it.
Q: What does being a SIAM member mean to you?
Jared: I’ve met many of my collaborators, most of whom are now good friends, at SIAM meetings. The majority of my publications are in SIAM journals, and many of the books I own were published by SIAM. Needless to say, SIAM has been a major factor in developing my career.
Raf: The first conference I attended was the 2001 SIAM Annual Meeting; It was an overwhelming experience. I was and I still am impressed by the diversity of applications and numerical problems that are investigated by SIAM members. Without the incentives of SIAM I would never have been able to connect to so many people, offering me so many opportunities: research visits, collaborations, industry contacts, and not to forget the many friends I have made.
David: I belong to several professional societies, but SIAM is by far the most important to me. I benefit regularly from the networking opportunities provided by SIAM meetings, and a good fraction of my publications have been in SIAM journals. I have also published one SIAM book.