Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
02:01 AM

68 Views

Diverge in Newton Method

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!

9 Replies

Highlighted
##

mecej4

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
11:15 AM

68 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.

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
05:11 PM

68 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?

Highlighted
##

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?

mecej4

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
05:56 PM

68 Views

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
07:24 PM

68 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.

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-11-2014
11:59 PM

68 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!

Highlighted
##

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.

mecej4

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-12-2014
04:33 AM

68 Views

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-16-2014
07:48 PM

68 Views

Thanks for your advice, mecej4.

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

All the condition numbers I got are larger than 10^{10}.

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!

Highlighted
##

mecej4

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-16-2014
09:02 PM

68 Views

^{10}, you should try setting the tolerance in Newton's method to 10^{-9} or 10^{-8}.

Highlighted
##

YC_H_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-16-2014
09:29 PM

68 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(=10^{10})

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.

For more complete information about compiler optimizations, see our Optimization Notice.