CONJUGATE GRADIENT METHOD FOR SOLVING LARGE SPARSE LINEAR SYSTEMS ON MULTI-CORE PROCESSORS

CONJUGATE GRADIENT METHOD FOR SOLVING LARGE SPARSE LINEAR SYSTEMS ON MULTI-CORE PROCESSORS

Souza, N. Z. de; Campos-Silva, J. B.; Aparecido, J. B.

Full Article:

In the mathematical modelling of the fluid flow and heat transfer processes it is frequent to find systems of second order linear or non linear partial differential equations. When solving such systems of partial differential equations through the use of numerical methods such as finite elements or finite differences it is necessary to do the discretization process that transforms the original systems of equations, defined over a continuum domain, into a linear or non linear algebraic system, defined over a discrete domain. Due to the char-acteristics of discretization methods for the partial differential equations domain as well for the equations themselves, generally the algebraic system that appears has the coefficient ma-trix with a very high sparsity. In this work we present the implementation in parallel pro-cessing of routines capable to solve large linear sparse systems with positive definite coeffi-cient matrix, exploiting and preserving the initial sparsity. It is analyzed the use of the conju-gate gradient method in the solution of large sparse linear systems running on multi-core processors.

In the mathematical modelling of the fluid flow and heat transfer processes it is frequent to find systems of second order linear or non linear partial differential equations. When solving such systems of partial differential equations through the use of numerical methods such as finite elements or finite differences it is necessary to do the discretization process that transforms the original systems of equations, defined over a continuum domain, into a linear or non linear algebraic system, defined over a discrete domain. Due to the char-acteristics of discretization methods for the partial differential equations domain as well for the equations themselves, generally the algebraic system that appears has the coefficient ma-trix with a very high sparsity. In this work we present the implementation in parallel pro-cessing of routines capable to solve large linear sparse systems with positive definite coeffi-cient matrix, exploiting and preserving the initial sparsity. It is analyzed the use of the conju-gate gradient method in the solution of large sparse linear systems running on multi-core processors.

Palavras-chave:

DOI: 10.5151/meceng-wccm2012-18559

Referências bibliográficas

• [1] J. B. Aparecido, N. Z. de Souza and J. B. Campos-Silva, “Data Structure and the Pre-Conditioned Conjugate Gradient Method for Solving Large Sparse Linear Systems with Symmetric Positive Definite Matrix”. Proceedings of CILAMCE-2011, Ouro Preto, 2011
• [2] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. M. Donato, J. Dongarra, V. Eikhout, R. Pozo, C. Romine and H. Van Der Vorst, “Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods”, SIAM, Philadelphia, PA, 1994.
• [3] J. B. Campos-Silva and J. B. Aparecido, “Data structure and stationary iterative solution methods for large sparse linear systems”. Proceedings of the 17th International Congress 020040060080010001200140016001E-151E-141E-131E-121E-111E-101E-91E-81E-71E-61E-51E-41E-30,010,1110 n = 100 thousands n = 500 thousands n = 1 million n = 5 millions n = 10 millionsL2 norm of the residualiteration number of Mechanical Engineering – COBEM 2003, Paper 0036, November 10-14, São Paulo, SP, 2003.
• [4] B. Chapman, G. Jost and R. van der Pas, “Using OpenMP”, The MIT Press, Cambridge, 2008.
• [5] V. Faber and T. Manteuffel, “Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method”, SIAM J. Numer. Anal., 21, pp. 315-339, 1984.
• [6] G. H. Golub and G. Meurant, “Résolution Numérique des Grandes Systèmes Linéaires”, Collection de la Direction des Etudes et Recherches de l´Electricité de France, vol. 49, Eyolles, Paris, 1983.
• [7] G. H. Golub and van Loan, C. F., “Matrix Computations”, Third Edition, The John Hop-kins University Press, 1996.
• [8] M. R. Hestenes and E. Stiefel, “Methods of conjugates gradients for solving linear sys-tems”, J. Res. Nat. Bur. Standards, 49, pp. 409-436, 1952.
• [9] J. Reid, “On the method of conjugate gradients for the solution of large sparse systems of linear equations”, in Large Sparse Sets of Linear Equations, Ed. J. Reid, Academic Press, London, pp. 231-254, 1971.
• [10] A. Van Der Sluis and H. Van Der Vorst, “The Rate of Convergence fo Conjugate Gra-dients”, Numer. Math., 48, pp. 543-560, 1992.
• [11] W.A. Wiggers, V. Bakker, A.B.J. Kokkeler and G.J.M. Smit, “Implementing the conju-gate gradient algorithm on multi-core systems”, In: International Symposium on System-on-Chip, SoC, Tampere, Finland, 2007.

Como citar:

Souza, N. Z. de; Campos-Silva, J. B.; João Batista Aparecido; "CONJUGATE GRADIENT METHOD FOR SOLVING LARGE SPARSE LINEAR SYSTEMS ON MULTI-CORE PROCESSORS", p-1819-1834. In: In Proceedings of the 10th World Congress on Computational Mechanics [= Blucher Mechanical Engineering Proceedings, v. 1, n. 1]. São Paulo: Blucher, 2014.
ISSN 23580828, DOI 10.5151/meceng-wccm2012-18559