Approximations for the general block distribution of a matrix

The general block distribution of a matrix is a rectilinear partition of the matrix into orthogonal blocks such that the maximum sum of the elements within a single block is mini-mized. This corresponds to partitioning the matrix onto parallel processors so as to minimize processor load while maintaining regular communication patterns. Applications of the prob-lem include various parallel sparse matrix computations, compilers for high-performance languages, particle in cell computations, video and image compression, and simulations as-sociated with a communication network. We analyze the performance guarantee of a natural and practical heuristic based on iterative renement, which has previously been shown to give good empirical results. When p 2 is the number of blocks, we show that the tight performance ratio is