Professor of Computer Science
Joined department: Fall 2008
Alex Pothen's research interests are in combinatorial scientific computing (CSC), parallel algorithms, graph algorithms, and bioinformatics. CSC is an interdisciplinary research area where discrete mathematics and algorithms are applied to solve combinatorial problems in the sciences and engineering.
Alex is a Fellow of: the Society for Industrial and Applied Mathematics (SIAM, 2018), the Association for Computing Machinery (ACM, 2022), and the American Mathematical Society (AMS, 2024). He received the George Polya prize in Applied Combinatorics in 2021 from SIAM for work on graph coloring models, algorithms, and software for computing derivatives to solve nonlinear optimization problems and differential equations.
Alex Pothen, with his colleagues, led the effort to organize the applied and computational discrete algorithms (ACDA) Activity Group within SIAM, and served as the AG's Founding Chair from 2019-2020. The ACDA community was formed out of several research subcommunities in computing, and includes the CSC research community that was organized in the early 2000's. He was Co-Chair of the first three international workshops in CSC, and served as the Chair of the CSC Steering Committee.
Alex has contributed to several research areas in ACDA:
In CSC, he has worked on approximation algorithms for graph matching and edge covers. His work on spectral algorithms for graph partitioning pioneered the development of several classes of algorithms for mapping parallel computations on supercomputers. In recent work, he and his colleagues have developed fast updating algorithms for visualizations in computational surgery and contingency analysis in modeling the electrical power grid, through an augmented matrix approach.
In Algorithmic Differentiation (AD), Alex and colleagues have developed new formulations and algorithms for several graph coloring problems. These algorithms make feasible the computation of large, sparse Jacobian and Hessian matrices at a small overhead cost over the computation of the functions involved to solve nonlinear optimization problems and differential equations. The ColPack software makes this work available for users in optimization, and has been used to solve problems in more than fifty scientific domains, ranging from studies of the universe to the design of mobility assisting robots. They have also developed fast algorithms for Hessian and higher order derivatives using a generalized chain rule and the Reverse Mode of AD.
Alex has mentored nineteen PhD students, seven post-doctoral scientists, more than sixty Master's students, and several undergraduate researchers. His mentees hold (or have held) appointments at Washington State University, Vanderbilt, Penn State, Drexel and Indiana University; Google, Meta, Microsoft, IBM, Oracle, and Conviva Corporations; and Lawrence Berkeley Lab, Lawrence Livermore National Lab, Pacific Northwest National Lab, etc.
Alex served as the Director of the Combinatorial Scientific Computing and Petascale Simulations (CSCAPES) Institute, a pioneering research project in CSC funded by the U.S. Department of Energy's Office of Science from 2006-2012. The CSCAPES Institute involved thirty researchers from Purdue and several National Labs, who developed computational tools in CSC that enable large-scale computational models in science and engineering on Peta-scale computers. Alex was also a member of the ExaGraph center, funded by the Exascale Computing Project of the DOE and NNSA.
Alex is an editor of the Journal of the A.C.M., SIAM Journal on Scientific Computing, SIAM Fundamentals of Algorithms (books), SIAM Classics (books), and Optimization Methods and Software.
S M Ferdous, Alex Pothen, Arif Khan, Ajay Panyala and Mahantesh Halappanavar, A parallel approximation algorithm for maximizing submodular b-matching, Proceedings of the First SIAM Conference on Applied and Computational Discrete Algorithms, pp. 45-56, 2021. https://epubs.siam.org/doi/epdf/10.1137/1.9781611976830.5
Alex Pothen, SM Ferdous and Fredrik Manne, Approximation algorithms in combinatorial scientific computing, Acta Numerica, 28, pp. 541-633, 2021. https://www.cambridge.org/core/journals/acta-numerica/article/abs/approximation-algorithms-in-combinatorial-scientific-computing/8B1B0396F6DF012CFBDF52E686197DFC
Yu-Hong Yeung, Alex Pothen, Mahantesh Halappanavar and Zhenyu Huang, AMPS: An augmented matrix formulation for principal submatrix updates with application to power grids, SIAM J. Scientific Computing, 39(5) S809-827, 2017. https://www.cs.purdue.edu/homes/apothen/Papers/AMPS.pdf
Mu Wang, Assefaw Gebremdhin and Alex Pothen, Capitalizing on live variables: Efficient Hessian Computations for Automatic Differentiation, Mathematical Programming Computation, 8(4) pp. 393-433, 2016.