abstract = "Large sparse matrices characterise the linear systems
found in various scientific and engineering domains
such as fluid mechanics, structural engineering, finite
element analysis and network analysis. The ordering of
the rows and columns of a matrix determines how close
to the main diagonal its non-zero elements are, which
in turn greatly influences the performance of solvers
for the associated linear system. The reduction of the
sum of the distance of non-zero elements from the
matrix's main diagonal, a quantity known as envelope,
is thus a key issue in many domains. Formally, the
problem consists in finding a permutation of the rows
and columns of a matrix which minimises its envelope.
The problem is known to be NP-complete. A considerable
number of methods have been proposed for reducing the
envelope. These methods are mostly based on
graph-theoretic concepts. While metaheuristic
approaches are viable 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 of sparse matrices is presented. We
evaluate our method on a set of standard benchmarks
from the Harwell-Boeing sparse matrix collection
against four state-of-the-art algorithms from the
literature. The results obtained show that the proposed
method compares very favourably with these
algorithms.",