Interactive educational modules illustrating sparse matrix computations and their corresponding graph problems.

Abstract

Applications of graph theory are ubiquitous in many different scientific areas. Therefore various software tools are available that aim at explaining graph concepts and graph algorithms. Graphs are particularly important and common in sparse matrix computations. However, there is currently no educational software demonstrating the intimate connection between sparse matrix problems and their corresponding graph problems. The relation between sparse matrix problems and their graph theoretical counterparts is often not easy to catch for students. We describe two interactive educational modules for classroom teaching. The first module explains how to group columns of a sparse matrix in a certain way and shows its connection to graph coloring. The second module illustrates Cholesky factorization of a sparse matrix and clarifies its relation to vertex elimination in some undirected graph. The goal of these modules is to give students the opportunity to interactively explore the underlying phenomena from the point of view of both, linear algebra and graph theory.