.png){kind=icon}
返回
A parallel bio-inspried shortest path algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/s00607-018-0621-x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Sparse numerical linear algebra
Preconditioning
Physarum polycephalum
Parallel shortest path
Krylov subspace methods
Gauss-Seidel preconditioner
M-Matrix
Delta-Stepping
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
2.8
论文数:
2.3K
被引数:
3.5K
机构
引用论文
.png){kind=icon}
查看更多内容