The key focus of my work is the multidisciplinary area of research known as Combinatorial Scientific Computing (CSC), which brings together key ideas from combinatorial optimization and algorithmics to solve difficult problems in scientific computing. The design and implementation of efficient parallel algorithms is critical in CSC. Beginning with my PhD thesis, I have worked on several variants of the graph matching problem. My collaborative work has not only resulted in novel approximate algorithms but also in scalable implementations on state-of-the-art computer systems. Since joining PNNL, I have continued this work to develop new algorithms and scalable implementations for coloring, clustering, network alignment, stochastic coordinate descent, extraction of chordal subgraphs and influence maximization. Scalable implementations have targeted distributed-memory systems, traditional multicore and manycore (GPUs; Tilera) platforms and massively multithreaded (XMT) architectures. Establishment of the ECP Codesign Center on graph algorithms (ExaGraph) is a testament to the importance of this work in the context of scientific computing. It is also worth to note that the same set of algorithms are equally important in the emerging areas of graph analytics and graph-based semi-supervised learning.

I portion of my work has covered topics in game theory, numerical optimization, machine learning and uncertainty quantification. I have explored several application areas including the study of electric power grid, computational biology, fault tolerance and scientific workflows.

• Graph matching (linear assignment problem)
• Graph clustering (community detection)
• Generative modeling of power transmission networks
• Resilient cyber systems
• Computational biology

---

Projects

Externally funded projects (PI/Co-PI/Senior Personnel):

• Department of Energy-Advanced Scientific Computing Research (DOE-ASCR): Exascale Computing Projects. “ExaGraph: Combinatorial Methods for Enabling Exascale Applications Co-Design Center.” (FY2017–FY2021)
• Department of Energy-Advanced Scientific Computing Research (DOE-ASCR): “IPPD: Integrated End-to-End Performance Prediction and Diagnosis for Extreme Scientific Workflows.” (FY2015–FY2018) -- (Renewed: FY2019-FY2021)
  
• Department of Energy-Advanced Research Projects Agency-Energy (DOE-ARPAE): GRID DATA Program. Generating Realistic Information for the Development of Distribution and Transmission Algorithms. “Sustainable Data Evolution Technology for Power Grid Optimization.” (FY2017–FY2019)
  
• DARPA Hierarchical Identify Verify Exploit (HIVE) Program
• Department of Defense: “HPDA: High Performance Data Analytics.” (FY2016–FY2017)
• Department of Energy-Advanced Scientific Computing Research (DOE-ASCR): “M2ACS: Multifaceted Mathematics for Complex Energy Systems.” (FY2012–FY2017)
• Department of Defense: “CASS-MT: Center for Adaptive Supercomputing Software-Multithreaded.” (FY2009–FY2015)

Laboratory Directed Research and Development (LDRD) Projects, Pacific Northwest National Laboratory (PI/Co-PI/Senior Personnel):

• LDRD Seed: Towards Automated Vulnerability and Mitigation of Critical Infrastructure (FY2018)
• NSD LDRD: Cyber-based Contingency Analysis of Interdependent Infrastructure Networks under Uncertainty (FY2019–FY2020)
• MinT-Net: Novel and Scalable Network-enabled Comparative Tools for Stress Studies of Microbiomes in Transition (FY2017)
• Rendezvous: Optimization and Stochastic Algorithms for Asymmetric Resilient Infrastructure (FY2015–FY2017)
• Concurrent Design and Control of Complex Systems: Controllability, Observability and Performance Metrics (FY2017–FY2018)
• Resilience in Large-Scale Distributed Control Systems (FY2015–FY2018)
• Scaling Multisubject Cortical Parcellation (FY2016)
• M&Ms4Graphs: A Multi-scale, Multi-Dimensional Graph Analytics Framework for Cyber Security (FY2013–FY2016)
• Shyre: Streaming Hypothesis Reasoning (FY2014–FY2015)
• Theory of Resilience (FY2014–FY2015)
• Future Power Grid Control Paradigm (FY2012–FY2015)
• Linear Algebra Solvers and Associated Matrix-Vector Kernels for Power Grid Simulations (FY2010–FY2015)
• Comparing Performance on Different High Performance Computing Architectures (FY2010)
  

---

Synergistic Activities

• Co-organizing GrAPL 2019: Workshop on Graphs, Architectures, Programming, and Learning, Co-Located with IPDPS 2019. Rio De Janeiro, Brazil
  
• Co-organized GraML 2018: Second Workshop on the Intersection of Graph Algorithms and Machine Learning, Co-located with IPDPS 2018 May 25, 2018. Vancouver, British Columbia, Canada
• Co-organized 2017:GraML’17: First Workshop on the Intersection of Graph Algorithms and Machine Learning, Co-located with IPDPS 2017. Orlando, Florida, USA.
  
• Co-organized the Workshop on Parallel Algorithms and Software for Analysis of Massive Graphs (ParGraph), held in conjunction with HiPC, India, 2011 and 2012.
• Co-organized mini-symposiums at SIAM conferences (Annual Meeting, Parallel Processing for Scientific Computing, Computational Science and Engineering).
• Participated on the program committees for several conferences and workshops.

---

Doctoral Thesis

• Adviser: Alex Pothen, Professor of Computer Science, Purdue University
• Committee: Jessica Crouch, Bruce Hendrickson (Sandia National Labs), Stephen Olariu, Mohammad Zubair
• Thesis: Algorithms for Vertex Weighted Matching in Graphs. Old Dominion University, 2009. (Defense slides)
  

Abstract: A matching M in a graph is a subset of edges such that no two edges in M are incident on the same vertex. Matching is a fundamental combinatorial problem with many applications. In the first part of this thesis, we develop exact and approximation algorithms for vertex weighted matchings, an under-studied variant of the weighted matching problem. We propose three exact algorithms, three half approximation algorithms, and a two-third approximation algorithm. We exploit inherent properties of this problem such as lexicographical orders, decomposition into sub-problems, and the reachability property, not only to design efficient algorithms, but also to provide simple proofs of correctness of the proposed algorithms. In the second part of this thesis, we describe work on a new parallel half-approximation algorithm for weighted matching. Algorithms for computing optimal matchings are not amenable to parallelism, and hence we consider approximation algorithms here. We extend the existing work on a parallel half approximation algorithm for weighted matching and provide an analysis of its time complexity. We support the theoretical observations with experimental results obtained with MatchBoxP, toolkit designed and implemented in C++ and MPI using modern software engineering techniques. The work in this thesis has resulted in better understanding of matching theory, a functional public-domain software toolkit, and modeling of the sparsest basis problem as a vertex-weighted matching problem.