An interactive educational module illustrating sparse matrix compression via graph coloring.

Abstract

The importance and presence of graph theory in many different scientific areas has led to the development and use of various software tools, intended to explain graph concepts and graph algorithms. Graphs are also ubiquitous in sparse matrix computations. However, there is currently no educational software addressing the intimate connection between sparse matrix problems and corresponding graph problems. Though combinatorial techniques are of primary importance to analyze and understand sparse matrix problems arising in scientific computing, the relation between sparse matrix problems and their graph theoretical counterparts is often not easy to catch for students. We propose a novel interactive educational module for teaching how to group columns of a sparse matrix in a certain way and its connection to graph coloring. The goal is to give students the opportunity to interactively explore the underlying phenomena from the point of view of both, linear algebra and graph theory.