Interchange Opportunity in Average Bandwidth Reduction in Sparse Matrices

Mafteiu-Scai, Liviu Octavian

doi:10.2478/v10324-012-0015-2

Abstract

This paper proposes two methods for determining suit- able interchanges of lines/columns in case of average bandwidth re- duction in sparse and symmetric matrices. First, a greedy heuristic inspired by the laws of physics (mechanics) to reduce the average bandwidth is proposed. The second method is an exact method that allows to estimate the potential of a row/column interchange to reduce the average bandwidth.

References

1. P. Arbenz, A. Cleary, J. Dongarra, and Heglan. M., Parallel numerical linear algebra.chapter A comparison of parallel solvers for diagonally dominant and general narrowbanded linear systems, Nova Science Publishers, Inc., Commack, NY, USA, 2001
Search in Google Scholar
2. A. Caprara and J. Salazar-Gonzalez, Laying out sparse graphs with provably minimum bandwidth, INFORMS J. on Computing, 17/3, (2005), 356-373.10.1287/ijoc.1040.0083
Search in Google Scholar
3. E. Cuthill and J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proc. of ACM, (1969), 157-172.10.1145/800195.805928
Search in Google Scholar
4. G. M. Del Corso and G. Manzini, Finding exact solutions to the bandwidth minimization problem, Computing, (1999), 189-203.10.1007/s006070050002
Search in Google Scholar
5. N. E. Gibbs, W. G. Poole, and P. K. Stockmeyer, An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM Journal on Numerical Analysis, (1976), 236-250.10.1137/0713023
Search in Google Scholar
6. A. Lim, J. Lin, and F. Xiao, Particle swarm optimization and hill climbing for the bandwidth minimization problem, Applied Intelligence, 26/3, (2007), 175-182.10.1007/s10489-006-0019-x
Search in Google Scholar
7. A. Lim, B. Rodrigues, and F. Xiao, Heuristics for matrix bandwidth reduction, European Journal of Operational Research, 174/1, (2006), 69-91.10.1016/j.ejor.2005.02.066
Search in Google Scholar
8. L. O. Mafteiu-Scai, Bandwidth reduction on sparse matrix, West University of Timisoara Annals, XLVIII/3, (2010.)
Search in Google Scholar
9. R. Marti, V. Campos, and E. Pinana, A branch and bound algorithm for the matrix bandwidth minimization, European Journal of Operational Research, 186, (2008), 513-528.10.1016/j.ejor.2007.02.004
Search in Google Scholar
10. R. Marti, M. Laguna, F. Glover, and V. Campos, Reducing the bandwidth of a sparse matrix with tabu search, European Journal of Operational Research, 135, (2001), 450-459.10.1016/S0377-2217(00)00325-8
Search in Google Scholar
11. N. Mladenovic, D. Urosevic, D. Perez-Brito, and C. Garcia-Gonzalez, Variable neighbourhood search for bandwidth reduction, European Journal of Operational Research, 200, (2010), 14-27.10.1016/j.ejor.2008.12.015
Search in Google Scholar
12. C. Pintea, G. Crisan, and C. Chira, A Hybrid ACO Approach to the Matrix Bandwidth Minimization Problem, M. Graa Romay et al., Springer-Verlag Berlin Heidelberg, 201010.1007/978-3-642-13769-3_49
Search in Google Scholar
13. L. O. Mafteiu-Scai, V. Negru, D. Zaharie, and O. Aritoni, Average bandwidth reduction in sparse matrices using hybrid heuristics, Studia Universitatis Babes-Bolyai University, Cluj Napoca, 3/2011, (2011.)
Search in Google Scholar
14. R. Mart, V. Campos, and E. Piana, A Branch and Bound Algorithm for the Matrix Bandwidth Minimization, European Journal of Operational Research 186, (2010), 513-528.10.1016/j.ejor.2007.02.004
Search in Google Scholar
15. Eduardo Rodriguez-Tello, Jin-Kao Hao, and Jose Torres-Jimenez, An Improved Simulated Annealing Algorithm for Bandwidth Minimization, European Journal of Operational Research, 185(3): 1319-1335, Elsevier, (2008.) 10.1016/j.ejor.2005.12.052
Search in Google Scholar

Interchange Opportunity in Average Bandwidth Reduction in Sparse Matrices

Abstract

Paradigm

My account