Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy
| Autor: | Libério Martins Silva, Sanderson L. Gonzaga de Oliveira |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
0209 industrial biotechnology
Computer science Heuristic MathematicsofComputing_NUMERICALANALYSIS 02 engineering and technology Management Science and Operations Research 01 natural sciences Computer Science Applications Theoretical Computer Science 010309 optics Reduction (complexity) Matrix (mathematics) 020901 industrial engineering & automation 0103 physical sciences Bandwidth (computing) Hyper-heuristic Heuristics Hill climbing Algorithm Sparse matrix |
| Zdroj: | RAIRO - Operations Research. 55:2247-2264 |
| ISSN: | 1290-3868 0399-0559 |
| Popis: | This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A heuristic for bandwidth reduction labels the rows and columns of a given sparse matrix. The algorithm arranges entries with a nonzero coefficient as close to the main diagonal as possible. This paper modifies an ant colony hyper-heuristic approach to generate expert-level heuristics for bandwidth reduction combined with a Hill-Climbing strategy when applied to matrices arising from specific application areas. Specifically, this paper uses low-cost state-of-the-art heuristics for bandwidth reduction in tandem with a Hill-Climbing procedure. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed strategy outperformed low-cost state-of-the-art heuristics for bandwidth reduction when applied to matrices with symmetric sparsity patterns. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|