Re: Re: Re: Problems with NSolve

*To*: mathgroup at smc.vnet.net*Subject*: [mg88262] Re: [mg88240] Re: [mg88214] Re: Problems with NSolve*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 30 Apr 2008 04:23:12 -0400 (EDT)*References*: <fuumfl$8dr$1@smc.vnet.net> <48131E36.1090106@gmail.com> <200804280841.EAA06082@smc.vnet.net> <200804291049.GAA28250@smc.vnet.net>

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

**References**:**Re: Problems with NSolve***From:*"Kshitij Wagh" <kgwagh@gmail.com>

**Re: Re: Problems with NSolve***From:*Daniel Lichtblau <danl@wolfram.com>