Intel® oneAPI Math Kernel Library
Ask questions and share information with other developers who use Intel® Math Kernel Library.

Diverge in Newton Method

YC_H_
Beginner
974 Views

Hi,

I encounter a diverge problem when using Intel MKL PARDISO to solve a transient simulation by Newton method.

This case is a unsymmetrical matrix with  size is 64,000 and 1,721,082 non-zeros (L+U).

I found that it diverges when the values are changes during a sequential solving.

I tried to use CGS to "iparm[3]=101" to reduce the error, different ordering and with/without scale.

But they don't work in my case.

Is there a possible way or options to deal with it?

Thanks!

 

0 Kudos
9 Replies
mecej4
Honored Contributor III
974 Views

Newton's method, even for a single equation with one unknown variable, is not globally convergent. Consider, for example, f(x) = x + 1.5 - exp(x). With the starting value x = 0.1, Newton's method converges to the root at 0.8577 in about ten iterations. With the starting value x = 0.01, more than fifty iterations are needed. Started at x = 0.005, the iterations diverge. If something similar to this happens in your application, tweaking Pardiso parameters is not going to make Newton's method work.

Consult the literature regarding quasi-Newton and truncated Newton algorithms.

0 Kudos
YC_H_
Beginner
974 Views

Hi mecej4,

Thank you for the reply.

I know that Newton method would act differently with different intial values.

I also tried different sparse solvers such as SuperLU and UMFPACK to solve the same problem.

They do converge in this case.

Is it casused by the difference of factorization algorithms?

Any hint that I can make Intel PARDISO work?

 

0 Kudos
mecej4
Honored Contributor III
974 Views

The first thing to check is that you are passing the correct arguments to Pardiso. If the equations are such that one or more of the other solvers that you listed are able to obtain the correct solution, you should be able to do the same with Pardiso. Can you post an example of the linear(ized) equations that you solve?

0 Kudos
YC_H_
Beginner
974 Views

I am afraid I cannot post this equation due to the policy issue.

In this case, PARDISO could solve this linear system but the solutions between two iteration are not close enough to converge.

PARDISO parameters are checked and are verified by solving some small cases.

For the large case, I enable maximum weight algorithm and scale to make it robust.

Different number of threads can also influence the results and lead to diverge. Only 1 thread converge more iterations than others setting.

I also used different CNR options such as SSE, SSE2, AVX, AUTO and COMPATIBLE. None of them converges in my case.

0 Kudos
YC_H_
Beginner
974 Views

Hi,

I found that I make PARDISO converge in my case by loosing the absolute tolerance of Newton's method larger than 1-10.

I know to ask too much accuracy is unfeasible in floating point arithmetic.

How to estimate the accuracy of PARDISO in a case? I got ||A||inf = 12,000 in my case.

Is there any diagnostic function that I can use?

Thanks!

0 Kudos
mecej4
Honored Contributor III
974 Views

You can use an MKL routine (a number of routines with "con" in their name are available, and you need to select one appropriate to the type of your matrix -- symmetric, positive-definite, banded, etc.) to estimate the condition number of a representative instance of the matrix A, and select a convergence criterion for Newton's method that is one or two orders of magnitude larger than the estimated error in the solution of A.

0 Kudos
YC_H_
Beginner
974 Views

Thanks for your advice, mecej4.

I computed the condition number by a condest() function.

All the condition numbers I got are larger than 1010.

In my case, the absolute tolerance of Newton method must be less than 10-12.

I tried iterative refinement but it does not help.

Set iparm(8) = -5 always makes it NaN.

Another way is to use CGS by setting iparm[4]=101 but it does not converge at the beginning.

Is there any suggestion for me to resolve it?

I am glad to try any possible solution.

Thanks!

0 Kudos
mecej4
Honored Contributor III
974 Views

If the condition numbers are about 1010, you should try setting the tolerance in Newton's method to 10-9 or 10-8.

0 Kudos
YC_H_
Beginner
974 Views

If I loss the absolute tolerance to 10-11, it will converge in my case.

But I have another question here, how come another solver can solver this problem with tight absolute tolerance?

Is it just lucky to converge in this case?

Can I conclude it by the following sentence?

MKL PARDISO solver does not promise to give an answer with such tight absolute tolerance (=10-12) from a matrix with a large condition number(=1010)

Is it a good idea to use a pre-conditioner to converge it without loss the absolute tolerance?

I hope that I can stick with this setting.

0 Kudos
Reply