Addressing the envelope reduction of sparse matrices using a genetic programming system

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Behrooz Koohestani and Riccardo Poli",
  title =        "Addressing the envelope reduction of sparse matrices
                 using a genetic programming system",
  journal =      "Computational Optimization and Applications",
  year =         "2015",
  volume =       "60",
  number =       "3",
  pages =        "789--814",
  month =        apr,
  keywords =     "genetic algorithms, genetic programming, Envelope
                 reduction problem, Sparse matrices, Graph labelling,
                 Combinatorial optimisation",
  ISSN =         "0926-6003",
  publisher =    "Springer US",
  URL =          "",
  URL =          "",
  DOI =          "doi:10.1007/s10589-014-9688-2",
  size =         "26 pages",
  abstract =     "Large sparse symmetric matrix problems arise in a
                 number of scientific and engineering fields such as
                 fluid mechanics, structural engineering, finite element
                 analysis and network analysis. In all such problems,
                 the performance of solvers depends critically on the
                 sum of the row bandwidths of the matrix, a quantity
                 known as envelope size. This can be reduced by
                 appropriately reordering the rows and columns of the
                 matrix, but for an N by N matrix, there are N! such
                 permutations, and it is difficult to predict how each
                 permutation affects the envelope size without actually
                 performing the reordering of rows and columns. These
                 two facts compounded with the large values of N used in
                 practical applications, make the problem of minimising
                 the envelope size of a matrix an exceptionally hard
                 one. Several methods have been developed to reduce the
                 envelope size. These methods are mainly heuristic in
                 nature and based on graph-theoretic concepts. While
                 metaheuristic approaches are popular alternatives to
                 classical optimisation techniques in a variety of
                 domains, in the case of the envelope reduction problem,
                 there has been a very limited exploration of such
                 methods. In this paper, a Genetic Programming system
                 capable of reducing the envelope size of sparse
                 matrices is presented and evaluated against four of the
                 best-known and broadly used envelope reduction
                 algorithms. The results obtained on a wide-ranging set
                 of standard benchmarks from the Harwell-Boeing sparse
                 matrix collection show that the proposed method
                 compares very favourably with these algorithms.",

Genetic Programming entries for Behrooz Koohestani Riccardo Poli