Penetrating the Fog, Lifting the Veil from Algorithms
Homer Walker Helps Developers Understand Why Their Algorithms Work or Don’t Work
In 2005, Homer Walker received the WPI Board of Trustees’ Award for Outstanding Research and Creative Scholarship. His research and teaching interests include, among other things, computational and applied mathematics. Walker is internationally known for his role in the analysis and development of algorithms for computing solutions of systems of linear and nonlinear equations. A longstanding interest of his has been Krylov subspace methods and Newton-Krylov methods for solving very large systems of linear and nonlinear equations. A large part of his work is aimed at helping algorithm developers understand how and why their algorithms work or don’t work. In his words, he tries to “penetrate the fog, to lift the veil.” His research often involves “proving theoretical results, and sometimes developing heuristics that lead to some refined sense of when things work.”
Over the years, mathematical and computational groups at NASA, Lockheed Electronics, Lawrence Livermore Laboratory, and Sandia Laboratories, as well as research-funding programs at the National Science Foundation (NSF) and the Department of Energy (DOE), have relied on Walker’s expertise in numerical algorithms. The algorithms he has developed and/or improved have been essential to a number of numerical software packages. He is particularly proud of the part his work has played in the development of the NOX software, an equation solving package at Sandia Labs, and the KINSOL software, a similar package at Lawrence Livermore Laboratory. These codes have been used for many challenging modeling applications, including combustion, various kinds of fluid flow, and the chemical vapor deposition process used to coat silicon microchips. Walker’s work has also been incorporated into PETSc, a software package developed at Argonne Laboratory that is used to do similar types of large-scale nonlinear modeling.
Walker considers himself “very much an applied mathematician.” He says, “I’ve always wanted to do things that were of some immediate interest to people outside of mathematics. Applied mathematics is what people outside of mathematics care about in some immediate sense because it’s important to their research, or whatever else they do.” That research, for example, may include modeling complex statistical phenomena like economic forecasts or complex physical phenomena like the dynamic properties of metamaterials (also known as ‘designer materials’). Such research may also include understanding the processes involved in weather forecasting, seismic data interpretation, medical imaging, information extraction from massive data sets, and the output of high energy physics and controlled fusion devices.
Anderson acceleration, a method for accelerating certain types of algorithmic processes, is the current focus of Walker’s talents. “These processes,” he says, “are called fixed-point iterations …. These algorithms come up a lot in many forms, but in particular in image processing. I’m trying to pique the interest of some people in medical image processing. I’ve been looking at this acceleration method for the last two or three years, and I’ve been applying it to some of the fixed-point iterations that I’ve known, which are mostly associated with the equations that come out of physical modeling …. I first became aware of this acceleration method when talking to some people from the Lawrence Berkeley Lab. They were using it to accelerate some very complicated procedures in electronic structure computations. The end goal of that activity is to be able to predict the properties of ‘designer materials’ by looking at things at the molecular level. And they said, ‘Sometimes it works, sometimes it doesn’t, and we don’t understand why.’ So after a year or two, I finally did some analysis that related it to a well-known numerical linear algebra algorithm for solving big linear equations. And because people know a good bit about that linear algebra algorithm, we can now transfer that knowledge to this acceleration procedure.”
Walker’s paper on Anderson acceleration was accepted in May 2011. He hopes that his work on Anderson acceleration will help speed up many fixed-point algorithms used in numerical applications, enabling the researchers to solve complex problems faster on their current computing architectures. As he notes, numerical algorithms sometimes lead to advances in computer hardware and software, and sometimes they follow them.
Beaumont, Texas, a modest-size city near the Louisiana border, is where Walker was born and raised. His philosophy about the field of mathematics and its significance to the world is summed up in a story from his childhood in Beaumont. As a kid growing up in the early 1950s, he was intrigued by all of the exciting developments in science, particularly nuclear physics. Walker fondly recalls a moment in 9th grade when asked what major he would pursue in college. He answered math or physics because his fascination with the breakthroughs in science had sparked an epiphany. “Somewhere along the line,” he says, “I got the idea that mathematics was kind of at the core of everything. If you didn’t understand mathematics, then you weren’t really understanding whatever else you were trying to do in science.”
Walker received his B.A. from Rice University in Houston in 1966, and four years later earned his Ph.D. from New York University’s Courant Institute of Mathematical Sciences. After receiving his doctorate, he went back to his home state and started his research and teaching career at Texas Tech University in Lubbock. Over the years, he moved to the University of Houston (1975-85) and from there to Utah State University (1986-97). Toward the end of his stay in Utah, Walker was looking for the freedom to grow creatively and professionally in his area of specialization, computational and applied mathematics. The WPI Department of Mathematical Sciences seemed like a good fit. “There were a lot of things I liked about it,” says Walker. “I liked the focus on applied science. I liked that fact that the Math Sciences Department was pretty strongly focused on computational mathematics. I liked the burgeoning industrial effort that was just getting started. I liked the fact that WPI was private. I had only been at large state schools before, and WPI was a small private school that was cozy. It looked like it would be easy to move around across disciplinary lines.”
The move to WPI proved fruitful for both Walker and the university. He was hired as the Head of the Department of Mathematical Sciences, serving from 1997 to 2002. Since coming to WPI, Walker has brought in over $5 million in grants and contracts from NSF, DOE, NIH, and industry. Although Walker misses hiking and skiing in the Rocky Mountains, access to Cape Cod and the cosmopolitan, urbane culture of New England has been a happy tradeoff.