Application Specific Computing - Research

Graph Decompositions+

There are benefits in decomposing the adjacency graph of a sparse matrix into subgraphs. Depending on the decomposition we obtain better numerical schemes (e.g. better preconditioners) or better execution schemes (e.g. better data locality). However, we need fast parallel algorithms for the decompositions or else this preprocessing time eats up the benefits of the improved schemes.