.png){kind=icon}
.png){kind=icon}
Return
A parallel bio-inspried shortest path algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/s00607-018-0621-x.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Sparse numerical linear algebra
Preconditioning
Physarum polycephalum
Parallel shortest path
Krylov subspace methods
Gauss-Seidel preconditioner
M-Matrix
Delta-Stepping
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.