Matrix inversion routines for Newton's method

[dpo854]

Hi everyone,

I am a newbie when it comes to intel. So, pardon me if my question is too simple and bears resemblance to any of the questions that have been asked before on this platform. I need to invert a Jacobian matrix(of the order of 500*500) in each step of Newton's method for a system of non-linear equations. Currently, my Fortan code, which is quite old (probably written around 2002), uses Gauss-Jordan method for Matrix inversion, which is quite time consuming. I just wanted to know if intel mkl libraries are capable of bringing down the computation time significantly since the matrix is quite general and can't be brought into a sparse form or any other forms amenable to special operations. I believe the intel libraries have some sort of parallelized schemes running behind the scenes. Just need some info in terms of rough orders of magnitude of the relative reduction in computational time. 

Thanks,

Debadutta Prusty

[mecej4]

MKL provides a nice solver for nonlinear equations. 

There are at least two drawbacks to the steps that you outlined. The first is that the effort to compute the Jacobian can be quite substantial. Furthermore, in the initial stages when the current trial solution is far away from the true solution, there is little benefit derived from computing that Jacobian in full.

Secondly, when solving simultaneous linear equations on a computer one should not compute the inverse of the matrix. Rather, one performs an L-U factorization and then solves two triangular systems to obtain the solution. See the description of the Lapack routine ?GESV.

[dpo854]

Thanks for directing me to the non-linear solver. I will go through the documentation to see if it can be used for my problem. By the way, aren't all these factorization techniques only for simultaneous linear equations? The problem I am trying to solve has a system of non-linear equations. So, explicit computation of the Gaussian matrix at each step is probably unavoidable.

[mecej4]

Almost all solution methods for nonlinear simultaneous equations construct a sequence of linear approximations. If a solution exists for the nonlinear equations, given a good starting solution ("guess", it is sometimes called), a good algorithm will cause the sequence of solutions of the linear sub-problems to converge to the solution of the nonlinear equations. 

Newton's method is not the only method of linearization, nor is it efficient for all problems. You may see a descriptions of some of these issues in this article, among others.