A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM

Creative Commons License

Torun F. S., Manguoglu M., Aykanat C.

SIAM JOURNAL ON SCIENTIFIC COMPUTING, cilt.40, sa.6, 2018 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 40 Sayı: 6
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1137/18m1166407
  • Dergi Adı: SIAM JOURNAL ON SCIENTIFIC COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Anahtar Kelimeler: row projection methods, block Cimmino algorithm, Krylov subspace methods, row inner-product graph, graph partitioning, ITERATIVE METHODS, PROJECTION METHOD, SPARSE, SYSTEMS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation defined on this graph model, the partitioning objective of minimizing the cutsize directly corresponds to minimizing the sum of interblock inner products between block rows thus leading to an improvement in the eigenvalue spectrum of the iteration matrix. This in turn leads to a significant reduction in the number of iterations required for convergence. Extensive experiments conducted on a large set of matrices confirm the validity of the proposed method against a state-of-the-art method.