Title :
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
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;
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
DOI :
10.1109/IHMSC.2010.51
