HAPPENING VIRTUALLY: SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)
Minitutorials
Minitutorial: An Introduction to Combinatorial Scientific Computing
Tuesday, July 20, 2021
10:15 – 11:45 am Eastern Time
Session Co-Chairs: Rob Bisseling, Henning Meyerhenke, Uwe Naumann
Organizers:
Rob Bisseling, University of Utrecht, the Netherlands
Henning Meyerhenke, Humboldt-Universität zu Berlin, Germany
Uwe Naumann, RWTH Aachen, Germany
Presenters:
Assefaw Gebremedhin, Washington State University, USA
Fredrik Manne, University of Bergen, Norway
Christian Schulz, Heidelberg University, Germany
Abstract:
Graph algorithms have played an important role in numerical methods since at least 1961 when Parter noted that graphs could be used to describe the structure of sparse matrix algorithms. Through the intervening decades, graphs have been used to encode a wide variety of concepts in scientific computing and have played key roles in sparse factorizations, parallel algorithms, algorithmic differentiation, mesh generation and many other problems. In the early 2000s, researchers in this field coalesced around the name “Combinatorial Scientific Computing” (CSC). A series of SIAM Workshops on CSC has now been folded into the new ACDA Conference. This minitutorial will provide an accessible introduction to CSC with a focus on three illustrative research topics: (i) applications of graph matching for entity pairing, (ii) large-scale graph partitioning for load balancing, and (iii) graph models in algorithmic differentiation for computing exact derivatives of computer-generated functions. Through these exemplar problems we will touch on some of the recurring elements of CSC including:
Graph abstractions in numerical algorithmsPractical approximation algorithms for expensive graph operationsEmpirical performance studiesPerformance on modern and emerging computer architecturesConnections between scientific computing and data mining Minitutorial: Combinatorial frontiers in computational biology
Wednesday, July 21, 2021
10:15 – 11:45 am Eastern Time
Session Chair: Lenore Cowen, Tufts University
Organizers:
Lenore Cowen, Tufts University,
Christine Heitsch, Georgia Tech
Presenters:
Christine Heitsch, Georgia Tech
Xiaozhe Hu, Tufts University
Smita Krishnaswamy, Yale University
James Murphy, Tufts University
Abstract:
There are numerous subfields of computational biology and bioinformatics where important mathematical questions arise that require a combinatorics or graph theory toolbox. This tutorial will introduce some biological problems that are ripe for collaboration opportunities with the ACDA community. We will provide a high-level overview of the landscape and then focus on two emerging "hot topic" areas – protein-protein interaction networks and single cell sketching. For the first topic, we will provide an overview of network science methods in protein-protein interaction networks, which will set the stage for the ACDA’21 plenary talk by Prof. Lenore Cowen. The second topic area will be on the challenge of representing, denoising, and ultimately “sketching” single cell data. This work includes applications of spectral graph theory and manifold learning to denoise and model cellular systems faithfully for predictive insight. This mini-tutorial aims to introduce a set of biologically-important yet mathematically deep problems in an accessible way to applied mathematicians with little prior engagement with biology.