Partitioning sparse rectangular matrices for parallel processing

Tamara G. Kolda1998 · DOI

TL;DR

This paper tackles the challenge of partitioning sparse rectangular matrices for parallel processing, a problem less explored than its square symmetric counterpart. The authors introduce and compare several methods, finding that hybrid approaches combining spectral partitioning with an alternating method offer the best balance of performance and efficiency.

What Problem Does This Paper Address?

In scientific computing, especially on parallel systems, efficiently organizing sparse matrices is crucial for tasks like load balancing. The goal is to rearrange the matrix elements (using row and column permutations) so that most non-zero entries fall into a block diagonal structure. This makes computations, particularly matrix-vector and matrix-transpose-vector multiplications, more efficient. While this "matrix partitioning" problem is well-studied for square symmetric matrices, it's significantly less understood for rectangular matrices. This paper aims to formalize the rectangular partitioning problem and propose effective solutions.

Methods

The paper explores several methods for partitioning sparse rectangular matrices into an approximate block diagonal form.

  • Spectral Partitioning (Extended): The authors adapt the well-known spectral partitioning method, typically used for symmetric matrices, to the rectangular case. This involves creating a larger, symmetric matrix by combining the original matrix with its transpose and then applying spectral partitioning to this augmented matrix. The eigenvectors of the Laplacian of this matrix are used to determine the partition.
  • Alternating Partitioning (AP) Method: This is a novel method specifically designed for rectangular matrices. Instead of trying to partition rows and columns simultaneously, it iteratively refines partitions for rows and columns separately. It's derived from a matrix decomposition technique and aims to maximize the sum of non-zeros on the block diagonal while minimizing off-diagonal elements.
  • Hybrid Methods: Two hybrid strategies are proposed to leverage the strengths of the above methods:
  • Hybrid Spectral-AP: Uses the partition generated by the spectral method as an initial guess for the alternating partitioning method.
  • Hybrid RCM-AP: Uses the Reverse Cuthill-McKee (RCM) ordering (a standard technique for reducing matrix bandwidth on symmetric matrices) as the initial guess for the alternating partitioning method.

Datasets

The authors evaluate their methods on a collection of rectangular test matrices obtained from the Matrix Market repository, along with some matrices provided by Michael Berry. These matrices vary in size, ranging from 100x100 to 4000x400. The experiments are conducted for partitioning into 2x2, 8x8, and 16x16 block structures.

Key Insights and Ideas

  • Rectangular matrices pose a unique challenge: Unlike symmetric matrices, rectangular matrices require simultaneous consideration of row and column permutations, making direct application of existing methods less straightforward.
  • Spectral partitioning can be adapted but is computationally expensive: While extending spectral partitioning to rectangular matrices is feasible by symmetrizing, it requires computing eigenvectors of a larger matrix, which can be time-consuming.
  • Alternating partitioning offers a promising greedy approach: The AP method provides a novel way to tackle the rectangular problem by iteratively optimizing row and column partitions. Its greedy nature means the quality of the initial partition is crucial.
  • Hybrid methods are the clear winners: Combining the strengths of spectral partitioning (for a good initial guess) or RCM (for a fast, reasonable initial guess) with the iterative refinement of the AP method yields the best results in terms of reducing off-diagonal non-zeros.
  • Trade-off between quality and time: Spectral methods provide good quality but are slow. The AP method is faster but its quality depends heavily on the starting partition. Hybrid methods strike a good balance.

Key Results

  • Hybrid methods outperform others: The hybrid Spectral-AP and RCM-AP methods consistently reduced the number of non-zeros outside the block diagonal more effectively than the standalone spectral or alternating partitioning methods across various block sizes (2x2, 8x8, 16x16).
  • Hybrid Spectral-AP is best for quality: When partition quality is the top priority, the hybrid Spectral-AP method is recommended.
  • Hybrid RCM-AP is best for time/quality balance: When both time and quality are important, the hybrid RCM-AP method is the preferred choice.
  • Computational cost: Spectral partitioning is significantly more expensive in terms of computation time compared to the alternating partitioning method and its hybrid variants. The hybrid methods are approximately 10 times faster than spectral partitioning.

Limitations and Future Work

  • Spectral method's cost: The authors acknowledge that spectral and hybrid spectral-AP methods are "very expensive in terms of time" due to the need to compute eigenpairs.
  • Starting partition importance: The effectiveness of the alternating partitioning method relies heavily on a good starting partition. The paper proposes spectral and RCM as initializers but notes that the choice is important.
  • Future directions: The authors mention exploring multilevel methods for bipartite graphs and investigating direct handling of four or eight diagonal blocks. They also suggest that their methods could be extended to nonnegatively weighted matrices.

Summary updated

Abstract

The authors are interested in partitioning sparse rectangular matrices for parallel processing. The partitioning problem has been well-studied in the square symmetric case, but the rectangular problem has received very little attention. They will formalize the rectangular matrix partitioning problem and discuss several methods for solving it. They will extend the spectral partitioning method for symmetric matrices to the rectangular case and compare this method to three new methods -- the alternating partitioning method and two hybrid methods. The hybrid methods will be shown to be best.
BibTeX
@misc{kolda1998partitioning,
  author = {Tamara G. Kolda},
  title = {{Partitioning sparse rectangular matrices for parallel processing}},
  year = {1998},
  doi = {10.2172/658436},
}
Figure