Title: A cost effective graph-based partitioning algorithm for a system of linear equations

Authors: Hiroaki Yui; Satoshi Nishimura

Addresses: Database Systems Laboratory, The University of Aizu, Fukushima, Japan ' Computer Arts Laboratory, The University of Aizu, Fukushima, Japan

Abstract: There are many techniques for reducing the number of operations in directly solving a system of sparse linear equations. One such method is nested dissection (ND). In numerical analysis, the ND algorithm heuristically divides and conquers a system of linear equations, based on graph partitioning. In this article, we present a new algorithm for the first level of such graph partitioning, which splits a graph into two roughly equalised subgraphs. The algorithm runs in almost linear time. We evaluate and discuss the solving costs by applying the proposed algorithm to various matrices.

Keywords: sparse matrix; nested dissection; graph partitioning; graph algorithm; Kruskal's algorithm; Gaussian elimination; bit vector; adjacent list; refinement; system of equations.

DOI: 10.1504/IJCSE.2018.090440

International Journal of Computational Science and Engineering, 2018 Vol.16 No.2, pp.181 - 190

Received: 26 Feb 2015
Accepted: 29 Jan 2016
Published online: 19 Mar 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article