A cost effective graph-based partitioning algorithm for a system of linear equations. (2018)

• Record Type: Journal Article
• Authors: Yui, Hiroaki; Nishimura, Satoshi
• Is Part Of: International journal of computational science and engineering. Volume 16:Number 2(2018)
• Page Start: 181
• Page End: 190
• Publication Date: 2018
• Subjects: sparse matrix -- nested dissection -- graph partitioning -- graph algorithm -- Kruskal's algorithm -- Gaussian elimination -- bit vector -- adjacent list -- refinement -- system of equations; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

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.