An evaluation of low-cost heuristics for matrix bandwidth and profile reductions

DOI10.1007/s40314-016-0394-9zbMath1405.90111OpenAlexW2560052022MaRDI QIDQ725777

Júnior A. B. Bernardes, Guilherme O. Chagas, Sanderson L. Gonzaga de Oliveira

Publication date: 2 August 2018

Published in: Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40314-016-0394-9

zbMATH Keywords

orderingheuristicscombinatorial optimizationmetaheuristicssparse matricesgraph labelingbandwidth reductionbandwidth minimizationenvelope reduction problemprofile reductionrenumberingreordering algorithms

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Metaheuristic algorithms for the bandwidth reduction of large-scale matrices ⋮ A Hypergraph Partitioning Model for Profile Minimization ⋮ An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method ⋮ Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions

Uses Software

• HSL
• Matlab
• SparseMatrix
• DIMACS
• Harwell-Boeing sparse matrix collection
• Tabu search
• symrcm
• profile wavefront

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs
• The NP-completeness of the bandwidth minimization problem
• The effect of ordering on preconditioned conjugate gradients
• A new matrix bandwidth reduction algorithm
• Profile minimization problem for matrices and graphs
• Two improved algorithms for envelope and wavefront reduction
• GRASP and path relinking for the matrix bandwidth minimization.
• Preconditioning techniques for large linear systems: A survey
• Variable neighbourhood search for bandwidth reduction
• An improved simulated annealing algorithm for bandwidth minimization
• A Multilevel Algorithm for Wavefront Reduction
• The university of Florida sparse matrix collection
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• A new mode renumbering algorithm for bandwidth reduction
• Sparse matrix test problems
• An Implementation of a Pseudoperipheral Node Finder
• Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms
• Solution of linear equations with skyline-stored symmetric matrix
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• A Comparison of Several Bandwidth and Profile Reduction Algorithms
• A comparasion of three resequencing algorithms for the reduction of matrix profile and wavefront
• Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Problems
• A two‐step approach to finite element ordering
• A FORTRAN program for profile and wavefront reduction
• Reducing the Total Bandwidth of a Sparse Unsymmetric Matrix
• Methods of conjugate gradients for solving linear systems
• Reducing the bandwidth of a sparse matrix with tabu search.

This page was built for publication: An evaluation of low-cost heuristics for matrix bandwidth and profile reductions