From Google Maps to planetary cartography, Dr. Tim Davis’ work on algorithms and software impacts our lives every single day. This research has such a vast impact on our technology-driven world, that you have likely seen the results of his work without even realizing it.
Davis, a professor in the Department of Computer Science and Engineering at Texas A&M University, has dedicated his career to creating algorithms and software that can be used to solve large sparse matrix problems. Large matrices arise in many real-world problems in science, engineering and mathematics, and they tend to be mostly zero, or sparse. Davis constructs algorithms and software for solving these types of matrix problems.
SuiteSparse is a package of sparse matrix algorithms Davis created. His solvers are widely used in industry, academia and government labs, including Google, The MathWorks, NVIDIA, Sandia National Labs, the US Geological Survey, IBM, Mentor Graphics, Cadence, and in many open-source projects.
For example, every time you use Google Maps and zoom down to the street-level view, you are seeing the results of Davis’ work. The photos taken by Google have GPS coordinates, but they aren't in the right place. By passing through Davis' solvers, every photo on the planet in Google StreetView is placed in its proper position.
Similarly, the United States Geological Survey uses Davis’ solvers to create maps of the moon, mars and other planetary bodies. By simply plugging in his solvers, they are able to cut the time this would take from days down to minutes.
Many commercial engineering software packages also use his solvers. Several companies use them to analyze the design of chips that go inside cell phones or laptops before they are sent to be manufactured. There is no margin for error in these situations, so using Davis’ solvers prevents potential mistakes.
Davis is currently applying his research on sparse matrix solvers to create new algorithms that rely on graphics processing units (GPUs) to accelerate the solution to these problems. GPUs are computer chips that calculate mathematical problems, primarily for rendering images. GPUs create the graphics in computer video games, but they can also be used to solve hard problems in math and science.
GPUs have many data processing cores that are very fast when they all work together doing similar work on different parts of the data. Applying sparse matrix computations on a GPU is a challenge, however, because the data layout of these matrices is irregular. With the persistent progression of high-performance computing systems comes the need for ever-increasing performance. This is where Davis aims to go beyond what is simply needed and pursue the formation of better-than-commercial-quality software.
Davis first began working on these types of problems when he was a graduate student at the University of Illinois at Urbana-Champaign studying electrical engineering. He began exploring the ways in which hardware could be created to get data from memory before the computer needed it.
“My ideas turned out to be well-suited to matrix computations, and sparse matrices in particular,” Davis said. “I then got involved in the algorithms, not the hardware, and haven't looked back since. This trajectory is reflected in my research history: all my degrees are in electrical engineering, I'm in a computer science department, and I do applied math.”
Davis has accomplished a rare feat – he is a Fellow of all three of the corresponding professional societies: the Institute of Electrical and Electronics Engineers (IEEE) for his work in electrical engineering, the Association for Computing Machinery (ACM) for his work in computer science and the Society for Industrial and Applied Mathematics (SIAM) for his work in applied math.
Davis works closely with many collaborators at Texas A&M, around the country and around the world. With his students, and postdoctoral student Wissam Sid-Lakhdar, he is creating new algorithms that exploit the GPU.
He is collaborating with Dr. Dezhen Song, a fellow computer science and engineering professor, on solving the sparse matrix problems that come from robotics. When a robot takes images with a camera and stitches them together to create a 3-D model of the world around it, it has to solve a sparse matrix problem. He has recently started collaborating with Simon Foucart in the Department of Mathematics on a genetics problem, and Erick Moreno-Centeno in the Department of Industrial and Systems Engineering on finding exact solutions to optimization problems.
He also works closely with researchers at the University of Tennessee, the University of Florida, Sandia National Labs, Rutherford Appleton Lab in the UK, NVIDIA, Microsoft, Yahoo! Labs, San Jose State University, and Harvard.
“I could never have predicted the impact of my work,” Davis said. “When I started creating these matrix solvers in graduate school, I saw a problem to be solved and had no idea my solutions would be so widely used. My code is out there ‘in the wild’, being used by so many people to solve so many problems that I'm only aware of a small fraction of the ways it's being used every day. Because the code is so robust, reliable and well documented, I get very few bug reports or requests for help on how to use it, so I don't always hear from my many users.”