Heuristics and meta-heuristics for bandwidth minimization of sparse matrices

Abdullah, A.; Hussain, A.

Abstract

In this paper a new crossing minimization based method is proposed to solve the well-known matrix bandwidth minimization problem, which is to permute the rows and columns of the matrix so as to bring all the non-zero elements of the matrix to reside in a band that is as close as possible to the main diagonal. The feasibility of the crossing minimization paradigm is explored through an objective comparison of four crossing minimization heuristics, along with four meta crossing minimization heuristics, a relatively new clustering technique and two classical bandwidth minimization heuristics i.e. a total of 11 heuristics and meta heuristics. Based on the results of using the simulated data the crossing minimization heuristics are ranked, and the right combination of meta heuristics identified with a surprising finding that meta heuristics take less overall time as compared to the time taken by the corresponding individual heuristics and yet give better results. Lastly all these 11 heuristics and meta heuristics are applied to real data and the outcomes objectively compared with promising results.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 2006 IEEE International Conference on Engineering of Intelligent Systems
• Start Date: Apr 22, 2006
• End Date: Apr 23, 2006
• Online Publication Date: Sep 18, 2006
• Publication Date: 2006
• Deposit Date: Oct 16, 2019
• Publisher: Institute of Electrical and Electronics Engineers
• Book Title: 2006 IEEE International Conference on Engineering of Intelligent Systems
• ISBN: 1-4244-0456-8
• DOI: https://doi.org/10.1109/ICEIS.2006.1703188
• Keywords: sparse matrices, matrix bandwidth minimization, meta crossing minimization heuristics, clustering technique
• Public URL: http://researchrepository.napier.ac.uk/Output/1793640