Parallel solution of sparse linear systems to find the shortest path in large scale graphs

Arslan, Hilal
Manguoğlu, Murat
Solving the shortest path problem on large scale networks is crucial for many applications. As parallelism became more common with the advent of multi-core architectures as well as large and complex networks have begun to emerge in many settings, it is inevitable to come up with algorithms that take advantage of the current architectures. One alternative to solve the shortest path problem is to use one of the classical or improved parallel variations of the Dijkstra’s algorithm. However, when the size of the network becomes large, finding the shortest path requires excessive computational time. Recently, some bio-inspired methods to find the shortest path have been proposed, such as Genetic algorithms, Ant Colony Optimization, Swarm Systems, and Physarum Solver. Physarum Solver is capable of finding the shortest path in a labyrinth and is developed by modelling the behavior of Physarum Polycephalum, which is an amoeba-like organism. Physarum Solver has been applied in many applications recently. It can efficiently solve a variety of network optimization problems such as the traveling salesmen problem, the vehicle routing problem, and scheduling of multi-gravity assist trajectories and various optimization problems required linear programming. However, earlier studies provide only sequential variants of Physarum Solver. In this study, a parallel and scalable Physarum Solver is proposed with the objective to find the shortest path for static graphs with positive edge weights. The proposed scheme is applied on both large scale realistic and real world static graphs as well as dynamically changing graphs. Physarum Solver requires the solution of the linear systems whose coefficient matrix is an M-matrix at each iteration. This step is the most time consuming step especially for problems having excessive data or information size. However, Physarum related studies in the literature do not take advantage of M-matrix property of the coefficient matrix to solve the linear systems in Physarum Solver. They use a direct method to solve such systems, which is infeasible for large scale problems with several millions of unknowns. A parallel preconditioned iterative method for solving prementioned sparse linear systems is presented. The proposed preconditioner is specifically designed based on the properties of the coefficient matrix of those linear systems, and the effectiveness of the proposed preconditioner is compared against other state-of-the-art preconditioners on dynamic graphs. Furthermore, the proposed dynamic algorithm is designed to be suitable for dynamically changing graphs since it uses the information arising in earlier iterations. The parallel scalability as well as the effect of changing the edge weights to the time to solution are evaluated for each graph model, separately and compared against a state-of-the-art parallel implementation of the Dijkstra’s algorithm on a parallel multicore cluster. In contrast to the classical shortest path algorithms, the proposed scheme has a distinct advantage that it is using array based data-structures and optimized kernels which take advantage of today’s multi level cache hierarchies. Our implementation exhibits remarkable speedups with comparable accuracy for synthetic and real-world applications.
PMAA18 10th International Workshop on Parallel Matrix Algorithms and Applications, (27 - 29 Haziran 2018)


Rigorous Solutions of Large-Scale Scattering Problems Discretized with Hundreds of Millions of Unknowns
Guerel, L.; Ergül, Özgür Salih (2009-09-18)
We present fast and accurate solutions of large-scale scattering problems using a parallel implementation of the multilevel fast multipole algorithm (MLFMA). By employing a hierarchical partitioning strategy, MLFMA can be parallelized efficiently on distributed-memory architectures. This way, it becomes possible to solve very large problems discretized with hundreds of millions of unknowns. Effectiveness of the developed simulation environment is demonstrated on various scattering problems involving canonic...
Ergül, Özgür Salih (2013-11-09)
A parallel implementation of the multilevel fast multipole algorithm (MLFMA) is developed for fast and accurate solutions of electromagnetics problems involving complex plasmonic metamaterial structures. Composite objects that consist of multiple penetrable regions, such as dielectric, lossy, and plasmonic parts, are formulated rigorously with surface integral equations and solved iteratively via MLFMA. Using the hierarchical strategy for the parallelization, the developed implementation is capable of simul...
Broadband Multilevel Fast Multipole Algorithm Based on an Approximate Diagonalization of the Green's Function
Ergül, Özgür Salih (2015-07-01)
We present a broadband multilevel fast multipole algorithm (MLFMA) for fast and efficient solutions of three-dimensional multiscale problems involving large objects with dense discretizations. The proposed solver is based on the approximate diagonalization of the Green's function using scaled spherical and plane waves, leading to stable interaction computations for arbitrarily short distances in terms of wavelength. Despite contradictory requirements on the scaling factor that limit the accuracy of the diag...
Implicit monolithic parallel solution algorithm for seismic analysis of dam-reservoir systems
Özmen, Semih; Kurç, Özgür; Department of Civil Engineering (2016)
This research mainly focuses on developing a computationally scalable and efficient solution algorithm that can handle linear dynamic analysis of dam-reservoir interaction problem. Lagrangian fluid finite elements are utilized and compressibility and viscosity of the fluid are taken into consideration during the reservoir modeling. In order to provide computational scalability and efficiency, domain decomposition methods implemented with parallel computing approaches such as Finite Element Tearing and Inter...
Broadband Multilevel Fast Multipole Algorithm For Large-Scale Problems With Nonuniform Discretizations
Ergül, Özgür Salih; Takrimi, Manouchehr; Erturk, Vakur B. (2016-08-18)
We present a broadband implementation of the multilevel fast multipole algorithm (MLFMA) for fast and accurate solutions of multiscale problems involving highly nonuniform discretizations. Incomplete tree structures, which are based on population-based clustering with flexible leaf-level boxes at different levels, are used to handle extremely varying triangulation sizes on the same structures. Superior efficiency and accuracy of the developed implementation, in comparison to the standard and broadband MLFMA...
Citation Formats
H. Arslan and M. Manguoğlu, “Parallel solution of sparse linear systems to find the shortest path in large scale graphs,” presented at the PMAA18 10th International Workshop on Parallel Matrix Algorithms and Applications, (27 - 29 Haziran 2018), Switzerland, 2018, Accessed: 00, 2021. [Online]. Available: