An Improved Independent Set Ordering Algorithm for Solving Large-Scale Sparse Linear Systems
Lu Yao, Wei Cao, Zongzhe Li, Yongxian Wang, Zhenghua Wang · 2010
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.