Uma avaliação de implementações via OpenMP e Pthreads de duas heurísticas para reduções de largura de banda de matrizes

Abstract

In this work, two parallel algorithms are described in multicore architectures to solve the bandwidth and profile reduction problems of symmetric and sparse matrices. For this, the rows and columns of the coefficient matrix are permuted, leaving it with a compact structure so that the nonzero coefficients are close to the main diagonal. The new parallel algorithms were compared to algorithms available in the HSL library and in the Octave and Matlab softwares. In the simulations, these algorithms are applied as a preprocessing in the resolution of systems of linear equations. More specifically, systems of linear equations will be solved by the conjugate gradients method with incomplete Cholesky factorization preconditioning, where the coefficient matrix is symmetric and positive definite. A suitable memory location contributes to the efficiency of the preconditioned conjugate gradient method, and this characteristic can be obtained by rearrangements of rows and columns of the coefficient matrix. The libraries used were OpenMP and Pthreads. The quality of the solution for sequential and parallel algorithms was maintained for most of the tested instances. However, computational time was better with the OpenMP library than with the Pthreads library, especially when two threads were used in the execution of the algorithms. Nevertheless, in this work, it is shown that parallel heuristics for bandwidth reductions have the potential to accelerate the parallel method of the preconditioned conjugate gradients. However, the computational experiments carried out in this work showed that parallel heuristics for bandwidth reductions have the potential to accelerate the parallel method of preconditioned conjugate gradients.