Parallel Distance-k Coloring Algorithms for Numerical Optimization

Matrix partitioning problems that arise in the e#cient estimation of sparse Jacobians and Hessians can be modeled using variants of graph coloring problems. In a previous work [6], we argue that distance-2 and distance- graph coloring are robust and flexible formulations of the respective matrix estimation problems. The problem size in large-scale optimization contexts makes the matrix estimation phase an expensive part of the entire computation both in terms of execution time and memory space. Hence, there is a need for both sharedand distributed-memory parallel algorithms for the stated graph coloring problems. In the current work, we present the first practical shared address space parallel algorithms for these problems. The main idea in our algorithms is to randomly partition the vertex set equally among the available processors, let each processor speculatively color its vertices using information about already colored vertices, detect eventual conflicts in parallel, and finally re-color conflicting vertices sequentially