DISEÑO E IMPLEMENTACIÓN EN CUDA DE ALGORITMO MATRIX-FREE PARA MINIMIZAR EL RESIDUO DE SISTEMAS DE ECUACIONES NO LINEALES SOBREDETERMINADOS

Abstract

La necesidad de resolver sistemas de ecuaciones no lineales aparece en muchasáreas de la investigación. Distintos métodos se han desarrollado para resolver estos problemas,cada uno con diferentes requerimientos computacionales. Para sistemas sobredeterminadosse utilizan métodos como el de Levenberg-Marquardt pero lamentablemente no sonadecuados para problemas de gran tamaño. Los métodos Quasi-Newton no necesariamentefuncionan debido a que la raíz podría no existir. En esta memoria se propone e implementaen CUDA un algoritmo matrix-free para minimizar el residuo de un sistema de ecuacionesno lineales sobredeterminado. Este se basa en el método Jacobian-Free Newton-Krylov, unaalternativa de tipo matrix-free al método de Newton. El algoritmo propuesto requiere latranspuesta de la matriz Jacobiana por lo que se propone un nuevo algoritmo para calcularsu producto por un vector arbitrario. Además, se presentan experimentos numéricos paravalidar la propuesta, mostrar sus capacidades de minimización y de uso de memoria.

The need for solving nonlinear system of equations arise in many fields of research.Several methods were designed for solving such problems, each one with differentcomputational requirements. For overdetermined system of nonlinear equations, methodslike Levenberg-Marquardt have been used but they are not suitable if the system of equationsis large. Quasi-Newton’s method does not necessarily work since a root may not exist.In this thesis we propose a matrix-free algorithm, and its implementation using CUDA, to minimizethe residual of an overdetermined system of nonlinear equations. It is based on theJacobian-Free Newton-Krylov method, a matrix-free alternative to classical Newton’s method.The proposed algorithm requires the transpose of the Jacobian matrix, so we propose anew way for computing its product with an arbitrary vector. Numerical results are presentedto verify the effectiveness of the proposed approximations, its capabilities for minimizing theresidual and its memory usage.