MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Re: Problems with NSolve

Daniel Lichtblau wrote:
> Kshitij Wagh wrote:
>>Sorry for the "fuzziness" :)
>>chpoly was found by using  Det[A  - x*IdentityMatrix[dim]] (where A is a
>>matrix function of u with \alpha etc. being some random parameters).  \Alpha
>>etc are random real numbers between -1 and 1 with working precision 30. Also
>>please find attached a notebook of a working sample.
>>[contact the sender to get this attachment - moderator]
>>So I think  the problem seems here, that instead of getting polynomials, I
>>am getting rational functions.  The thread Carl sent mentions some
>>alternatives - I will try them out.
>> [...]

> Without a specific matrix it is still fuzzy.
 > [....]

I guess I should have been more specific. If you provide plain ascii 
text of your code, you will not require a notebook attachment and can 
have it directly in the MathGroup post. That way people can try it 
without needing to contact you off line.

> Now to address what I believe is the main bottleneck. You are computing 
> bivariate determinants, and Det is not using any method adapted to the 
> specifications of your particular family of matrices. For dimension 
> higher than 11 or so, it will do some thing that might well create 
> denominators (at least, if inputs are not exact), and moreover I expect 
> would be slow.

I was probably incorrect in thinking this would be the main bottleneck. 
Subsequent experimentation indicated that the method Det uses for larger 
matrices is substantially faster than what I showed for dimension 11 
(though still slower than the interpolation-based approach). I did not 
check with approximate inputs but that could well give rise to 
problematic denominators. That would more affect the NSolve step than 
the Det computation speed.

> [...]
> Next is the issue of finding, or at least counting, the real solutions 
> to the system that results when we look for multiple eigenvalues. One 
> approach, as you indicate, is to solve it and count the real solutions.
> findcrossings1[poly_, u_, t_] :=
>   Cases[{u, t} /. NSolve[{poly, D[poly, t]}, {u, t}], {_Real, _Real}]
> [...]
> This is a bit slow, and while I expect it to not deteriorate as fast as 
> CharacteristicPolynomial, it will all the same become problematic as 
> dimension rises.
 > [...]

When I tried at dimension 16 it took 400 seconds, compated to 10 for the 
CountRoots[Resultant[...]] approach. At dimension 21 that latter took 40 
seconds, and I did not bother trying the NSolve method. In your case, 
where Det may be giving back expressions with denominators due to not 
recognizing cancellation (this happens when approximate input is mixed 
with polynomial expressions), I'd not be surprised if NSolve behavior is 
substantially worse.

One (I hope) final remark. There are other ways to go about counting 
real roots. I do not have familiarity with the details. I just wanted to 
mention that if this problem is important to your work, and you cannot 
make progress with the methods already indicated, then there may still 
be other avenues to explore.

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: Enable multicore calculation ?
  • Next by Date: Re: Does Mathematica really need more printed, introductory documentation?
  • Previous by thread: Re: Re: Problems with NSolve
  • Next by thread: Re: Problems with NSolve