Improving Parallel Ordering of Sparse Matrices Using Genetic Algorithms | Zendy

Wen-Yang Lin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Improving Parallel Ordering of Sparse Matrices Using Genetic Algorithms

Author(s) -

Wen-Yang Lin

Publication year - 2005

Publication title -

applied intelligence

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.791

H-Index - 66

eISSN - 1573-7497

pISSN - 0924-669X

DOI - 10.1007/s10489-005-4611-2

Subject(s) - cholesky decomposition , computer science , crossover , heuristics , merge (version control) , minimum degree algorithm , mathematical optimization , algorithm , tree (set theory) , genetic algorithm , sparse matrix , parallel computing , incomplete cholesky factorization , mathematics , combinatorics , artificial intelligence , machine learning , eigenvalues and eigenvectors , physics , quantum mechanics , operating system , gaussian

In the direct solution of sparse symmetric and positive definite linear systems, finding an ordering of the matrix to minimize the height of the elimination tree (an indication of the number of parallel elimination steps) is crucial for effectively computing the Cholesky factor in parallel. This problem is known to be NP-hard. Though many effective heuristics have been proposed, the problems of how good these heuristics are near optimal and how to further reduce the height of the elimination tree remain unanswered. This paper is an effort for this investigation. We introduce a genetic algorithm tailored to this parallel ordering problem, which is characterized by two novel genetic operators, adaptive merge crossover and tree rotate mutation. Experiments showed that our approach is cost effective in the number of generations evolved to reach a better solution in reducing the height of the elimination tree.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research