Minitutorials


HAPPENING VIRTUALLY: SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)

Minitutorials


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 algorithms
  • Practical approximation algorithms for expensive graph operations
  • Empirical performance studies
  • Performance on modern and emerging computer architectures
  • Connections between scientific computing and data mining
  • 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.