Re: Re: Re: Problems with NSolve

Daniel Lichtblau wrote:
> Kshitij Wagh wrote:
>
>>Hi
>>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.
>>Thanks,
>>Kshitij
>> [...]

> 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