Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG
- PDF / 1,041,735 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 68 Downloads / 216 Views
ORIGINAL ARTICLE
Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method S. L. Gonzaga de Oliveira1 · L. M. Silva1 Received: 5 December 2018 / Accepted: 10 June 2019 © Springer-Verlag London Ltd., part of Springer Nature 2019
Abstract This paper proposes a novel ant colony hyperheuristic approach for reordering the rows and columns of symmetric positive definite matrices. This ant colony hyperheuristic approach evolves heuristics for bandwidth reduction applied to instances arising from specific application areas with the objective of generating low-cost reordering algorithms. This paper evaluates the resulting reordering algorithm in each application area against state-of-the-art reordering algorithms with the purpose of reducing the running times of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method. The results obtained on a wide-ranging set of standard benchmark matrices show that the proposed approach compares favorably with state-of-the-art reordering algorithms when applied to instances arising from computational fluid dynamics, structural, and thermal problems. Keywords Bandwidth reduction · Profile reduction · Heuristics · Reordering algorithms · Sparse matrices · Renumbering · Ordering · Graph labeling · Conjugate gradient method · Graph algorithm · Sparse symmetric positive definite linear systems · Incomplete Cholesky factorization · Ant colony optimization · Hyperheuristic
1 Introduction The solution of large sparse linear systems Ax = b where A is a sparse symmetric positive definite n × n matrix, x is the unknown n-vector solution, and b is a known n-vector is a critical step in various science and engineering applications. It is often the step of the simulation that demands the highest computational cost. The primary origin of the problems with large-scale matrices arises from the discretization of elliptic and parabolic partial differential equations (PDEs) [3]. The methods of finite differences, finite elements, and finite volumes are the most typical numerical problem-solving methods related to physical phenomena governed by PDEs. These methods generate large-scale linear systems [17, 18]. Modern hierarchical memory architecture and paging policies favor programs that consider the locality of reference a relevant aspect. Spatial locality means that a sequence * S. L. Gonzaga de Oliveira [email protected] L. M. Silva [email protected] 1
Departamento de Ciência da Computação, Universidade Federal de Lavras, Lavras, Brazil
of recent memory references is clustered locally rather than randomly in the memory address space. In this context, an adequate vertex ordering of a graph G = (V, E) associated with matrix A is desirable for the low-cost solution of large and sparse linear systems. The use of a heuristic for bandwidth and profile reductions is a convenient choice to produce a sequence of graph vertices with spatial locality. Thus, heuristics for bandwidth and profile reductions are
Data Loading...
