ABSTRACT
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.
