Interactively exploring the connection between bidirectional compression and star bicoloring.

Abstract

The connection between scientific computing and graph theory is detailed for a problem called bidirectional compression. This problem consists of finding a pair of seed matrices in automatic differentiation. In terms of graph theory, the problem is nothing but finding a star bicoloring. An interactive educational module is designed and implemented to illustrate the connection between bidirectional compression and star bicoloring. The web-based module is intended to be used in the classroom to illustrate the intricate nature of this combinatorial problem.