A New Heuristic for Bandwidth and Profile Reductions of Matrices Using a Self-organizing Map
In this work, a heuristic for bandwidth and profile reductions of symmetric and asymmetric matrices using a one-dimensional self-organizing map is proposed. Experiments and comparisons of results obtained were performed in relation to results of the Varia
- PDF / 539,405 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 211 Views
2
Universidade Federal de Lavras, Lavras, Minas Gerais, Brazil [email protected], [email protected] Universidade Federal Fluminense, Niter´ oi, Rio de Janeiro, Brazil [email protected], [email protected]
Abstract. In this work, a heuristic for bandwidth and profile reductions of symmetric and asymmetric matrices using a one-dimensional self-organizing map is proposed. Experiments and comparisons of results obtained were performed in relation to results of the Variable neighborhood search for bandwidth reduction. Simulations with these two heuristics were performed with 113 instances of the Harwell-Boeing sparse matrix collection and with 2 sets of instances with linear systems composed of sparse symmetric positive-definite matrices. The linear systems were solved using the Jacobi-preconditioned Conjugate Gradient Method. According to the results presented here, the best heuristic in the simulations performed was the Variable neighborhood search for bandwidth reduction. On the other hand, when the vertices of the corresponding graph were originally ordered in a sequence given by a space-filling curve, no gain was obtained when applying a heuristic for reordering the graph vertices. Keywords: Bandwidth reduction · Profile reduction maps · Conjugate gradient method · Graph labeling
1
·
Self-organizing
Introduction
Various problems in science and engineering, such as heat, fluid flow, or elasticity, are described by partial differential equations. A popular technique for solving partial differential equations is the finite element method. It consists of transforming a continuous differential equation into a system of algebraic equations. In addition, sparse large-scale linear systems of this kind can also be obtained by applying the finite volume method. Such systems of linear equations have the form Ax = b, where A is the matrix of coefficients, x is the vector of unknowns and b is the vector of independent terms. The resolution of this kind of linear systems occurs at the step where the most computation cost is demanded to solve the problem. This type of linear systems also occurs in applications not c Springer International Publishing Switzerland 2016 O. Gervasi et al. (Eds.): ICCSA 2016, Part I, LNCS 9786, pp. 54–70, 2016. DOI: 10.1007/978-3-319-42085-1 5
A New Heuristic for Bandwidth and Profile Reductions of Matrices
55
governed by partial differential equations, such as design and analysis of digital circuits, economic models, and industrial production systems [1]. The resolution of a linear system can be accomplished by either direct or iterative methods. As direct methods have low scalability regarding the processing and use of memory, especially in three-dimensional problems arising from partial differential equations, linear systems composed of large sparse matrices are often solved by iterative methods. The boundaries between direct and iterative methods have become less clear with the use of various ideas and techniques of direct methods in the field of iterative methods. As a result, iterativ
Data Loading...
