A parallel bio-inspried shortest path algorithm

arslan h., MANGUOĞLU M.

COMPUTING, cilt.101, sa.8, ss.969-988, 2019 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 101 Sayı: 8
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1007/s00607-018-0621-x
  • Dergi Adı: COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.969-988
  • Anahtar Kelimeler: Sparse numerical linear algebra, Preconditioning, Physarum polycephalum, Parallel shortest path, Krylov subspace methods, Gauss-Seidel preconditioner, M-Matrix, Delta-Stepping, INSPIRED ALGORITHM, PHYSARUM, NETWORK, MODEL
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Physarum polycephalum is an amoeba-like organism and is able to find the shortest path in a labyrinth. Inspired by P. polycephalum, recently, a mathematical model and an algorithm (Physarum Solver) was developed. There are, however, only sequential implementations of this algorithm. In this paper, a fast and efficient parallel Physarum Solver is proposed. The proposed algorithm requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix. The solution of the linear system is the most time consuming step of the Physarum Solver which is classically handled by direct solvers without taking advantage of the fact that the coefficient matrix is an M-matrix. However, direct solvers are infeasible for solving large real-world problems. In the proposed parallel Physarum Solver, an effective parallel iterative linear solver with a parallel preconditioner for M-matrices is used. The parallel scalability, solution time, and accuracy of the proposed algorithm are presented and compared to a state-of-the-art parallel implementation of -stepping shortest path algorithm in the Parallel Boost Graph Library. Our implementation exhibits a remarkable parallel speedup with comparable accuracy for synthetic and real world applications.