An Improved Independent Set Ordering Algorithm for Solving Large-Scale Sparse Linear Systems

Author

Yao, Lu ; Cao, Wei ; Li, Zongzhe ; Wang, Yongxian ; Wang, Zhenghua

Author_Institution

Nat. Key Lab. for Parallel & Distrib. Process., Nat. Univ. of Defense Technol., Changsha, China

Volume

1

fYear

2010

fDate

26-28 Aug. 2010

Firstpage

178

Lastpage

181

Abstract

The independent set ordering algorithm is a heuristic algorithm based on finding maximal independent sets of vertices in the matrix adjacency graph, which is commonly used for parallel matrix factorization. However, Disadvantages appear when it is applied to large-scale sparse linear systems. In this paper, we propose an improved algorithm by finding an optimal size of independent set in each elimination step rather than find a maximal independent set, which is proved to be effective by both theoretical analysis and parallel implementation.

Keywords

graph theory; heuristic programming; matrix decomposition; set theory; sparse matrices; heuristic algorithm; independent set ordering algorithm; large scale sparse linear system; matrix adjacency graph; maximal independent set; parallel implementation; parallel matrix factorization; Algorithm design and analysis; Heuristic algorithms; Linear systems; Parallel processing; Program processors; Sparse matrices; Timing; independent set; large-scale sparse linear systems; matrix ordering; parallel LU decomposition;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2010 2nd International Conference on

Conference_Location

Nanjing, Jiangsu

Print_ISBN

978-1-4244-7869-9

Type

conf

DOI

10.1109/IHMSC.2010.51

Filename

5590588