Metaheuristic-based Heuristics for Symmetric-matrix Bandwidth Reduction: A Systematic Review
| Autor: | Sanderson L. Gonzaga de Oliveira, Guilherme Oliveira Chagas |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Mathematical optimization
Computer science Linear system Bandwidth (signal processing) Metaheuristics Main diagonal Bandwidth reduction Graph Vertex (geometry) Renumbering Sparse matrices General Earth and Planetary Sciences Symmetric matrix Adjacency matrix Heuristics Metaheuristic Reordering algorithms General Environmental Science Sparse matrix |
| Zdroj: | ICCS |
| ISSN: | 1877-0509 |
| DOI: | 10.1016/j.procs.2015.05.229 |
| Popis: | Computational and storage costs of resolution of large sparse linear systems Ax=b can be performed by reducing the bandwidth of A. Bandwidth reduction consists of carrying out permutations of lines and columns so that they allow coefficients to remain near the main diagonal.When considering an adjacency matrix of a graph, bandwidth reduction can be considered in the sense of modifying the order in which the graph vertices are numbered. Heuristics for bandwidth reduction are revised in this study, aiming at determining which of them offers the higher bandwidth reduction with a reasonable computational cost. Specifically, metaheuristic-based heuristics are reviewed in this systematic review. Moreover, 29 metaheuristic-based heuristics tested for bandwidth reduction were found. Among them, 4 are recommended as possible state-of-the-art heuristics for addressing the problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|