Alex Pothen

Professor of Computer Science

Joined department: Fall 2008
Education
Ph.D., Cornell, Appl. Math. and Computer Science (1984)


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 combinatorial problems from the sciences and engineering. CSC links scientific computing with algorithmic computer science.

Alex Pothen, with his colleagues, led the effort to organize the CSC research community in the early 2000's. He was Co-Chair of the first three international workshops in CSC, and serves as the Chair of the CSC Steering Committee.

Alex has contributed to several areas in CSC.
In Combinatorial Scientific Computing, he has worked on graph matching and matroid theory (sparse bases for the null space, block triangular forms, Dulmage-Mendelsohn decomposition, approximation algorithms for weighted matching, etc.); spectral graph partitioning and locality inducing orderings; reordering chordal graphs for parallel matrix factorizations; partitioning chordal graphs into transitively closed subgraphs to obtain Product Form Inverse representations of triangular matrix factors; etc. In current work, he and his colleagues are developing fast updating algorithms for visualizations in computational surgery and contingency analysis in modeling the electrical power grid, through an augmented matrix approach.

In Automatic Differentiation, Alex and his colleagues have developed new formulations and algorithms to color graphs (distance-2 coloring, acyclic coloring, star coloring, and variants). 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. The ColPack software makes this work available for users in optimization and other areas. Recently they are developing fast algorithms for Hessian and higher order derivatives via a Live Variables Approach to the Reverse Mode of AD.

In Bioinformatics, Alex is developing algorithms for registering and classifying cell populations in Flow Cytometry data to understand the immune system. He has also developed algorithms for identifying functional modules in protein interaction networks, and for identifying biomarkers for lung and prostate cancer from mass spectral data.

Alex has mentored sixteen PhD students, six post-doctoral scientists, more than sixty Master's students, and several undergraduate researchers. His advisees hold (or have held) appointments at Washington State University, Penn State, Waterloo, Australian National University, and Drexel; Microsoft, IBM, Oracle, and Conviva Corporation; and Lawrence Berkeley Lab, Lawrence Livermore National Lab, Pacific Northwest National Lab, Argonne 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, Old Dominion University, Sandia National Labs, Argonne National Lab, Ohio State, and Colorado State. CSCAPES researchers developed computational tools in CSC that enable large-scale computational models in science and engineering on Peta-scale computers. These tools included parallelization and load-balancing software, Automatic Differentiation technology, parallel graph and sparse matrix algorithms, and transformations to improve the memory system performance of sparse computations.

Alex is an editor of the Journal of the A.C.M., and various book series and journals of the Society for Industrial and Applied Mathematics: SIAM Books, SIAM Spotlights, SIAM Review, SIAM Journal on Scientific Computing, and SIAM Monographs in Computational Science and Engineering.

Selected Publications
Mahantesh Halappanavar, Alex Pothen, Ariful Azad, Fredrik Manne, Johannes Langguth, and Arif M. Khan, Codesign Lessons Learned from Implementing Graph Matching on Multithreaded Architectures, IEEE Computer 48(8): 46--55 (2015)
Assefaw Hadish Gebremedhin, Duc C. Nguyen, Md. Mostofa Ali Patwary, and Alex Pothen, ColPack: Software for graph coloring and related problems in scientific computing, ACM Trans. Math. Softw. 40(1): 1 (2013)
Bruce Hendrickson and Alex Pothen, Combinatorial Scientific Computing: past successes, current challenges, and future opportunities, Chapter 1 in Combinatorial Scientific Computing, Uwe Naumann and Oalf Schenk (eds.), CRC Press and Chapman and Hall, 2011.