Hybrid algorithm Newton method for solving systems of nonlinear equations with block Jacobi matrix

O.M. Khimich, V.A. Sydoruk, A.N. Nesterenko

Abstract


Systems of nonlinear equations often arise when modeling processes of different nature. These can be both independent problems describing physical processes and also problems arising at the intermediate stage of solving more complex mathematical problems. Usually, these are high-order tasks with the big count of un-knows, that better take into account the local features of the process or the things that are modeled. In addition, more accurate discrete models allow for more accurate solutions. Usually, the matrices of such problems have a sparse structure. Often the structure of sparse matrices is one of next: band, profile, block-diagonal with bordering, etc. In many cases, the matrices of the discrete problems are symmetric and positively defined or half-defined. The solution of systems of nonlinear equations is performed mainly by iterative methods based on the Newton method, which has a high convergence rate (quadratic) near the solution, provided that the initial approximation lies in the area of gravity of the solution. In this case, the method requires, at each iteration, to calculates the Jacobi matrix and to further solving systems of linear algebraic equations. As a consequence, the complexity of one iteration is. Using the parallel computations in the step of the solving of systems of linear algebraic equations greatly accelerates the process of finding the solution of systems of nonlinear equations. In the paper, a new method for solving systems of nonlinear high-order equations with the Jacobi block matrix is proposed. The basis of the new method is to combine the classical algorithm of the Newton method with an efficient small-tile algorithm for solving systems of linear equations with sparse matrices. The times of solving the systems of nonlinear equations of different orders on the nodes of the SKIT supercomputer are given.

Problems in programming 2020; 2-3: 208-217

 


Keywords


systems of nonlinear equations; hybrid algorithm; sparse matrices; systems of linear algebraic equations; high-performance computing

Full Text:

PDF (Ukrainian)

References


Nesterenko, A.N. & Khimich, A.N. & Yakovlev, M.F. (2006) To the problem of solving of non-linear systems on multi-processor distributed memory computing system. Gerald of computer and information technologies. 10. pp. 54-56.

Dzhordzh A., Lyu Dzh. Chyslennoe reshenye bolʹshykh razrezhennykh system uravnenyy. M.: Myr, 1984. 334 p.

Pysanetsky S. Tekhnolohyya razrezhennykh matryts. M.: Myr, 1988. 410 p.

Alfredo Buttari, Julien Langou, Jakub Kurzak, and Jack Dongarra: A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures. Parallel Computing. 2009. Vol. 35. Issue 1. P. 38-53.

Popov O.V. Doslidzhennya efektyvnosti paralelʹnykh alhorytmiv dlya kompʺyuteriv hibrydnoyi arkhitektury. Materialy Mizhnarodnoyi naukovoyi shkoly-seminaru «Pytannya optymizatsiyi obchyslenʹ (POO XLII)», (Zakarpat·sʹka obl., Mukachivsʹkyy r.-n, smt. Chynadiyevo,

–25 veresnya 2015), Kyyiv: 2015, P. 16.

Rezhym dostupu: http://icybcluster.org.ua

Intel® Math Kernel Library (Intel® MKL) – Rezhym dostupu: https://software.intel.com/en-us/intel-mkl

CUDA CUBLAS_Library – Santa Clara: Nvidia, 2010. – 254 c.

Gropp W., Lusk E., and Thakur R. Using MPI-2: Advanced Features of the Message-Passing Interface. Cambridge: MIT Press, 1999. 382 p.

Boreskov A.V., Kharlamov A.A. Osnovy raboty s tekhnolohyey CUDA. M.: DMK Press, 2010. 232 p.


Refbacks

  • There are currently no refbacks.