Physical Sciences and Mathematics Commons^™

Graph Partitioning Using Matrix Values For Preconditioning Symmetric Positive Definite Systems, Eugenr Vecharynski, Yousef Saad, Masha Sosonkina

Computational Modeling & Simulation Engineering Faculty Publications

Prior to the parallel solution of a large linear system, it is required to perform a partitioning of its equations/unknowns. Standard partitioning algorithms are designed using the considerations of the efficiency of the parallel matrix-vector multiplication, and typically disregard the information on the coefficients of the matrix. This information, however, may have a significant impact on the quality of the preconditioning procedure used within the chosen iterative scheme. In the present paper, we suggest a spectral partitioning algorithm, which takes into account the information on the matrix coefficients and constructs partitions with respect to the objective of enhancing the quality …