chapter  12
30 Pages

Two-Dimensional Approaches to Sparse Matrix Partitioning

Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 12.5 Fine-Grain Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 12.6 The Hybrid Partitioning Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 12.7 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 12.8 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 12.9 Conclusions and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Parallel computers are appearing on our desktops, as the multicore revolution is driving technology towards parallelism. In our applications, this causes the need for partitioning of the computational work and the corresponding data. In scientific computing, these data are often represented by a sparse

matrix, which has many zero elements but stores the interesting information in its nonzero elements.