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.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021102
Keywords: Bandwidth reduction, sparse matrix, ant colony optimization, hyper-heuristic, reordering algorithms, renumbering, ordering, graph labeling, graph algorithm, local search procedure, Hill-Climbing procedure
@article{RO_2021__55_4_2247_0,
author = {Gonzaga de Oliveira, Sanderson L. and Silva, Lib\'erio M.},
title = {Low-cost heuristics for matrix bandwidth reduction combined with a {Hill-Climbing} strategy},
journal = {RAIRO. Operations Research},
pages = {2247--2264},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021102},
zbl = {07412783},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021102/}
}
TY - JOUR AU - Gonzaga de Oliveira, Sanderson L. AU - Silva, Libério M. TI - Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy JO - RAIRO. Operations Research PY - 2021 SP - 2247 EP - 2264 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021102/ DO - 10.1051/ro/2021102 LA - en ID - RO_2021__55_4_2247_0 ER -
%0 Journal Article %A Gonzaga de Oliveira, Sanderson L. %A Silva, Libério M. %T Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy %J RAIRO. Operations Research %D 2021 %P 2247-2264 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021102/ %R 10.1051/ro/2021102 %G en %F RO_2021__55_4_2247_0
Gonzaga de Oliveira, Sanderson L.; Silva, Libério M. Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2247-2264. doi: 10.1051/ro/2021102
[1] , and , Gradient-based variable ordering of decision diagrams for systems with structural units, edited by and . In: Vol. 10482 of ATVA 2017. Lecture Notes in Computer Science. Springer, Cham (2017) 184–200. | Zbl
[2] , Ant colony hyper-heuristics for travelling salesman problem. Proc. Comput. Sci. 76 (2015) 534–538. 2015 IEEE International Symposium on Robotics and Intelligent Sensors (IEEE IRIS2015). | DOI
[3] , and , Sparse matrix reordering schemes for browsing hypertext, edited by , and . In: Vol. 32 of Lectures in Applied Mathematics. The Mathematics of Numerical Analysis. American Mathematical Society Press, Park City, Utah, USA (1996) pp. 99–123. | Zbl
[4] , and , Graph entropy rate minimization and the compressibility of undirected binary graphs. In: Proceedings of IEEE Statistical Signal Processing Workshop (SSP). IEEE, Ann Arbor, MI (2012) 109–112.
[5] and , Metaheuristic-based heuristics for symmetric-matrix bandwidth reduction: a systematic review. Proc. Comput. Sci. (ICCS 2015 Int. Conf. Comput. Sci.) 51 (2015) 211–220.
[6] , Evaluation of triangular mesh layout techniques using large mesh simplification. Multimedia Tools App. 76 (2017) 25391–25419. | DOI
[7] , and , PQser: a Matlab package for spectral seriation. Numer. Algorithms 80 (2019) 879–902. | MR | Zbl | DOI
[8] and , The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38 (2011) 1–25. | MR | Zbl | DOI
[9] , , and , A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1 (2011) 3–18. | DOI
[10] and , Ant Colony Optimization. The MIT Press, Cambridge, MA (2004). | Zbl | DOI
[11] , and , Ant colony optimization: artificial ants as a computational intelligence technique. IEEE Comput. Intell. Mag. 1 (2006) 28–39. | DOI
[12] , , and , Recent advances in selection hyper-heuristics. Eur. J. Oper. Res. 2852 (2020) 405–428. | MR | Zbl | DOI
[13] , , and , Propagation path optimization of product attribute design changes based on petri net fusion ant colony algorithm. Expert Syst. App. 173 (2021) 114664. | DOI
[14] and , Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs (1981). | MR | Zbl
[15] and , A systematic review of heuristics for symmetric-matrix bandwidth reduction: methods not based on metaheuristics. In: Proceedings of the Brazilian Symposium on Operations Research (SBPO 2015). Sobrapo, Pernambuco, Brazil (2015).
[16] and , Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method. Eng. Comput. 36 (2019) 1857–1873. | DOI
[17] and , An ant colony hyperheuristic approach for matrix bandwidth reduction. Appl. Soft Comput. 94 (2020) 106434. | DOI
[18] , , and , Finding a starting vertex for the reverse Cuthill–Mckee method for bandwidth reduction: a comparative analysis using asymmetric matrices, edited by , et al. In: Vol. 10960 of The 18th International Conference on Computational Science and Its Applications (ICCSA), Lecture Notes in Computer Science. Springer International Publishing, Cham (2018) 123–137. | MR
[19] , and , An evaluation of low-cost heuristics for matrix bandwidth and profile reductions. Comput. Appl. Math. 37 (2018) 1412–1471. | MR | Zbl | DOI
[20] , and , An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method. Comput. Appl. Math. 37 (2018) 2965–3004. | MR | Zbl | DOI
[21] , Unravelling small world networks. J. Comput. Appl. Math. 158 (2003) 61–74. | MR | Zbl | DOI
[22] and , A hyper-heuristic approach to evolving algorithms for bandwidth reduction based on genetic programming. In: Research and Development in Intelligent Systems XXVIII. Springer, London, London, UK (2011) 93–106. | DOI
[23] , and , A fast algorithm for bandwidth minimization. Int. J. Artif. Intell. Tools 16 (2007) 537–544. | DOI
[24] , , , and , A two-stage hybrid ant colony optimization for high-dimensional feature selection. Pattern Recognit. 116 (2021) 107933. | DOI
[25] , and , A comparison of vertex ordering algorithms for large graph visualization. In: Proceedings of the 6th International Asia-Pacific Symposium on Visualization (APVIS’07). Sydney, Australia (2007) 141–148. | DOI
[26] , The NP-completeness of bandwidth minimization problem. Comput. J. 16 (1976) 177–192. | MR | Zbl
[27] and , An experimental analysis of a GP hyperheuristic approach for evolving low-cost heuristics for profile reductions. In: Anais do SEMISH – Seminário Integrado de Software e Hardware. Cuiabá, MT (2020). | DOI
[28] , , , and , An aco-based hyperheuristic with dynamic decision blocks for intercell scheduling. J. Intell. Manuf. 29 (2018) 1905–1921. | DOI
[29] , , , , and , A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs. Inf. Sci. 303 (2015) 33–49. | MR | Zbl | DOI
[30] , , and , Controlling a scattered field output of light passing through turbid medium using an improved ant colony optimization algorithm. Optics Lasers Eng. 144 (2021). | DOI
[31] , and , Some new strategies for RCM ordering in solving electromagnetic stattering problems. Comput. Phys. Commun. 184 (2013) 1161–1164. | MR | DOI
[32] , , and , A decomposition-based multi-objective genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Knowl.-Based Syst. 225 (2021) 107099. | DOI
Cité par Sources :
