Title: An evaluation of four reordering algorithms to reduce the computational cost of the Jacobi-preconditioned conjugate gradient method using high-precision arithmetic

Authors: Sanderson L. Gonzaga De Oliveira; Alexandre A.A.M. De Abreu; Diogo Robaina; Mauricio Kischinhevsky

Addresses: Departamento de Ciência da Computação, Universidade Federal de Lavras, Lavras, MG, Brazil ' Departamento de Ciência da Computação, Universidade Federal de Lavras, Lavras, MG, Brazil ' Universidade Federal Fluminense, Niterói, Rio de Janeiro, RJ, Brazil ' Universidade Federal Fluminense, Niterói, Rio de Janeiro, RJ, Brazil

Abstract: In this work, four heuristics for bandwidth and profile reductions are evaluated. Specifically, the results of a recent proposed heuristic for bandwidth and profile reductions of symmetric and asymmetric matrices using a one-dimensional self-organising map is evaluated against the results obtained from the variable neighbourhood search for bandwidth reduction heuristic, the original reverse Cuthill-McKee method, and the reverse Cuthill-McKee method with starting pseudo-peripheral vertex given by the George-Liu algorithm. These four heuristics were applied to three datasets of linear systems composed of sparse symmetric positive-definite matrices arising from discretisations of the heat conduction and Laplace equations by finite volumes. The linear systems are solved by the Jacobi-preconditioned conjugate gradient method when using high-precision numerical computations. The best heuristic in the simulations performed with one of the datasets used was the Cuthill-McKee method with starting pseudo-peripheral vertex given by the George-Liu algorithm. On the other hand, no gain was obtained in relation to the computational cost of the linear system solver when a heuristic for bandwidth and profile reduction is applied to instances contained in two of the datasets used.

Keywords: bandwidth reduction; profile reduction; self-organising maps; conjugate gradient method; CGM; graph labelling; combinatorial optimisation; heuristics; metaheuristics; reordering algorithms; sparse matrices; renumbering; ordering; graph algorithm; high-precision arithmetic; sparse symmetric positive-definite linear systems.

DOI: 10.1504/IJBIDM.2017.084281

International Journal of Business Intelligence and Data Mining, 2017 Vol.12 No.2, pp.190 - 209

Received: 21 Jan 2017
Accepted: 03 Feb 2017
Published online: 23 May 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article