American Scientist

Recognized internationally for his innovative algorithms and software, Tim Davis’s research has been applied in a vast range of real- world technological and social applications, from MATLAB to Google Street View, from aiding the FBI to creating original art. He is the recipient of the 2018 Sigma Xi Walston Chubb Award for Innovation, an annual award established in 2006. Previous awardees include engineer Akhlesh Lakhtakia, computer scientist Rosalind W. Picard, and materials scientist Stan Ovshinsky, among others. American Scientist’s digital managing editor, Robert Frederick, spoke with Davis about the software tools he creates, which he describes as “mathematical monkey wrenches,” some of which he has used to create artworks based on music.

What prompted you to make these mathematical tools in the first place? Was it a problem you were trying to solve, or something else?

I did all my degrees in electrical engineering and was also interested in computer architecture. But all along I was interested in software—just writing the code—all the way back to being a high school student. In 1978, maybe, I was a sophomore or a junior in high school. My brother was an undergraduate in mechanical engineering at Purdue University and said, “Oh, Tim, here, I’ll get you an account on the Purdue mainframe. Here’s a book on FORTRAN. Have at it.” And so I did. I went through all the problems in the book and typed up my punch cards and went to the mechanical engineering lab and stuck in my cards and computed pi or whatever from the projects in the book. I had fun. By the time I was done, I’d worked through the whole book, and that next summer I worked as a consultant in the computer room with all the other students. I was helping students with their Runge–Kutta differential equation solvers. I had no idea what Runge–Kutta was, but I could help them with their FORTRAN. And being really focused on finding programming bugs in other people’s code—it’s a fun puzzle—is a great way to learn how to find bugs in your own code.

So what was it that led to your work with matrix computations, now powering the “backslash” command in MATLAB, for example?

Going through my undergraduate at Purdue, I wasn’t doing linear algebra. I wasn’t doing a lot of matrix computation. But I was still writing some software. Then when I was in grad school at the University of Illinois, with an interest in computer architecture, I was looking at how to get the data to the processor faster and I came up with some ideas. Then I thought, “Well, it’s hard to think about that in isolation, so let’s look at an algorithm—why not?” I haven’t stopped looking, basically. I came up with some ideas of how to move the data around a little better for that algorithm. Eventually, my thesis turned into one minor section on architecture and just about all of it on a graph and a matrix algorithm. Then, for a postdoc, I had the opportunity to work with Iain Duff, who’s one of the top experts in the field of sparse matrix computations. He’s in southern France, so I spent a year in Toulouse, which was a lot of fun. That’s where I started working on the algorithm that, 10 years later, became “backslash” in MATLAB.

Was that when you first started explicitly making algorithms for other people, for problems that weren’t your own?

Well, already as a PhD student, I wrote an algorithm that then didn’t solve anybody else’s problems. It was a matrix solver. But it was as a postdoc that I started writing another solver when I didn’t have a matrix I wanted to solve. So yes, at that point, I was creating algorithms for other people, like Iain Duff does. He creates algorithms to solve matrix problems, not because he has matrices to solve, but because he’s a computational mathematician. So I’m doing like him, basically. I’m creating solvers that other people will be able to use. It’s viewed in my domain as an academic contribution just like writing a paper is, or discovering a new galaxy would be to an astrophysicist.

And all of it is about solving the matrix equation, AX=B?

Yes! Isn’t that crazy? It’s just all AX=B. I don’t care what X is, really. I don’t. You give me A and B, I don’t care where your A and B come from. But I want to give you the right X. I don’t have a personal attachment to X [laughs]. I just know I want to give you the right one. And that’s why we should care that code is written well, because if it’s written properly and elegantly and is easy to read and understand, then other people can understand and rely on these solvers to do things that are important to them.

People out there are using my work to build power networks and circuits, and fly drones, and even rescue girls from the sex-slave trade. Seeing the tool out there and getting used is really heartwarming. Google used my code for a year to place all the photos in Street View without even asking me how my code works and without even needing to tell me. They download it and use it and there it is. All these crazy things that I have no idea how it is that they’re doing that, except that it is AX=B somewhere.

Now, the more recent stuff I’m doing—that’s coming out of this group consortium, GraphBLAS.org—we’re not solving AX=B, surprisingly. It’s things such as matrix multiply. So it’s still linear algebra, and yet it’s beautiful, and it’s solving important problems, and, if you do it well and do it right and do it fast—asymptotically fast and fast in practice—then the world will use it, and then the world will solve problems with it. That’s fun.

Why do you say “It’s beautiful”?

For me, I see code—and people like me see code—as kind of like the proof of a mathematical theorem. And just like mathematicians might publish many versions of their proofs, there’s value in refinement. Turning a complicated, 10-page proof into an elegant, more understandable, more powerful 1-page proof that also proves the same theorem might open doors to other methods that could be used to solve other problems. Just like what mathematicians do for mathematical proofs, we do this for software.

Once you build one of these tools, do you later see further elegance—further improvements—and so go back to work on that tool? Or do you say, “That tool is good enough—done—I’m moving on to something else”?

People out there are using my work to build power networks and circuits, and fly drones, and even rescue girls from the sex-slave trade. Seeing the tool out there and getting used is really heartwarming.

• Facebook
• Twitter

There’s really multiple aspects to that question. When I write a piece of software and publish it, I get a paper out of it. I get people using it. It builds impact, which is good. But then it can’t stop there, can it? My code—all code—always has to be updated and maintained at some level. And then someone sends me an email and says, “Hey, I’m using your code to do this, and what about that?” “Oh, yeah,” I’ll say, “that would be easy, I’ll add that!” So I’ll add a new feature or do something different with it. I’ll make it easier to compile or run, and update the user guide. Yes, I could say, “Okay, I’m done. I’ll stop.” But there’s almost always more things to do. So I maintain the code, even though it’s published and done. I need to periodically bring the car into the shop and tinker with it, right?

What kind of support, if any, do you get as an academic to do this kind of software-maintenance work?

Even if I don’t get a paper out of it, it’s still worth my time doing the software maintenance, if you will, because I’ve got users to keep happy, basically. I don’t want to let them down. But, in general, building tools as an academic like this—and there are other computer scientists who are tool builders like me—we face a risk. That’s because writing really good software, software that is better than commercial or government quality, is crazy as an academic, because the payoff is only the impact: It’s a valuable contribution, from creating new algorithms and new methods, to making these methods fast—10,000, 5,000, 100 times faster than prior methods for some of these problems, although sometimes a factor of two is all I get, or sometimes it ties.

Of course, if you have that impact, that shows academic credibility to your algorithms and your methods and your work. But what if you build this great mathematical wrench, but it’s just not the very best wrench that’s out there? Or what if the world doesn’t actually need that kind of wrench and so people don’t use it? I think I have around 40 journal publications, which in some domains is minuscule. But one paper has 300 pages of bulletproof code behind it. That’s a hefty contribution. But if that code is not used, then it won’t have the impact and I’d only gotten one paper out of it, if that. So it’s risky, and I kind of barely squeaked through my earlier promotions. But now at Texas A&M University, my department head, who appreciates my work, she says, “Tim, you know you took a crazy risk to do all this?” Yeah, but I loved it, and I still do.

What about your artwork and using your code to turn music into visual art? Do you polish that artwork too?

The code itself to create that artwork is actually fairly rough. It’s what I would call my own “internal prototype.” I’m not distributing the code, though. I’m distributing the art. The software—that tool—is my paintbrush. So when I use it to render a visualization based on a new piece of music, sometimes I’ll decide, “Nah, I need something different. Let me think about these rules I’ve got and let me add to them.” I’ll modify my software to create different kinds of visualizations.

So there’s an aesthetic, meaning that you’re looking at these images that are generated across various parameter spaces and saying, “Okay, that one appeals to me aesthetically, I’ll chose that one.” Or you’ll tweak the code if you’re not happy with any of them?

Yes, exactly. It’s almost like a photographer. What’ll happen is I’ll do this image sweep and look across it and say, “Oh my goodness, I’ve never seen this before.” I just rendered Cat Stevens’s rendition of “Morning Has Broken,” which is a Celtic hymn, and I came up with a symbol, a graph, that looks like Celtic Trinity symbol. I was floored. It’s usually like seeing images in clouds. They’re not there, but your mind puts them there, and then that’s the image. Now, I have to create 1,000 clouds, and some of them are beautiful. Many of them are beautiful. But then I’ll say, “That’s a particularly beautiful cloud for that piece of music.”

The video below shows Davis's code rendering a visualization.