Re: FindRoots?

*To*: mathgroup at smc.vnet.net*Subject*: [mg112362] Re: FindRoots?*From*: "Ted Ersek" <ersekt at md.metrocast.net>*Date*: Sat, 11 Sep 2010 05:42:52 -0400 (EDT)

(**** What do we need RootSearch for? ****) In [1] Andrzej Kozlowski showed that Reduce in Mathematica 7 can quickly locate many roots of a transcendental equation. He then asked, "So what do you need RootSearch for?" Well I think RootSearch is still an important tool in cases that are not at all rare such as ... Others were correct when they mentioned that RootSearch is very good at finding roots of an InterpolatingFunction such as the ones we get from the built-in functions NDSolve, and Interpolation. In [2] Ingolf Dahl gave two examples of finding solutions of closed form equations where Reduce is very slow, but RootSearch can quickly find all the roots provided the search interval isn't too large. RootSearch also comes to the rescue in cases like Foo[x_Real] := SomeNumericalAlgorithm[x] RootSearch[ Foo[x]==0, {x, xmin, xmax} ] We also know from [3] that Reduce can't handle branch cuts. The same Blog post also seems to indicate that Reduce can only find roots of holomorphic functions. That probably gives us other problems where we need RootSearch. In [4] Andrzej Kozlowski said, "there are ways to do essentially the same things that RootSearch attempts to do and obtain the complete set of roots (provably complete)." Are these methods practical in every conceivable case? I wonder if it's even possible in every case. In [3] Roger Germundsson of Wolfram Research said there are theorems about undecidability of finding roots of a general numeric function. The new capability of Reduce is a wonderful addition, and in many cases Reduce should be preferred over RootSearch. However, I think we will always have a need for RootSearch (or a similar function) just as we will always have a need for NIntegrate, NDSolve even though Integrate, DSolve are state-of-the-art. (**** Limitations of Numerical Root Finding ****) Of course RootSearch has its own limitations as does any numerical method for Root Finding, Numerical Integration, or Solving Differential Equations. All such algorithms are limited by the number of discrete samples taken and the number of iterations allowed. In addition for any such algorithm to be practical, it must use approximate numbers. As with other numerical methods we can use RootSearch options to make it more robust at the expense of needing more time to get a result. (****** Why I wrote RootSearch ******) When I wrote the RootSearch package several years ago there was much more need for it because FindRoot was the best thing Wolfram provided for solving transcendental functions. Mathematica is a fantastic application, and nearly all its algorithms have amazing power. However, my RootSearch package is proof that FindRoot is far from state-of-the-art when it comes to finding roots in one-dimension. It should be an embarrassment to Wolfram that the "rather primitive" methods in my "amateurish package" perform far better than FindRoot in the case of searching in one-dimension. (***** Wolfram Can Improve RootSearch. Then Include it in Mathematica *****) Several times I told Wolfram Research they can use any of the packages I posted on MathSource in future versions of Mathematica. I also told them they can make any changes to my code that they want, and I expect nothing in return. I don't even care if I get credit for my contribution. Actually, I don't want Wolfram to use my RootSearch package verbatim in Mathematica. Instead I want them to implement a state-of-the-art routine with the same design goals as RootSearch. However, I think they should study my implementation because I may have had some good ideas. Also, I don't care if they call the function RootSearch, NReduce, or whatever. (***** Searching for Roots in N-dimensions *****) RootSearch doesn't attempt to find all roots of N-equations in a finite region of N-dimensions. I would have included that capability, but I still have a lot to learn before I can do that. I hope Wolfram will implement a state-of-the-art numerical algorithm to search for roots in N-dimensions. As Andrzej Kozlowski mentioned in this thread, he explains how this could be done in a Mathematica demonstration [5]. (***** Other Routines That Search for All Roots? *****) As a side note, I have tried to find evidence that someone else has written a routine with the same design goal as RootSearch. I have yet to find such evidence in any journal, math library, commercial application, free-ware, etc. In particular Mathematica's competition only provides functions similar to FindRoot. It's a great mystery to me why this subject is so neglected. I think the subject has important applications, and the algorithms needed are probably is simple compared to what's inside NDSolve. (***** FindRoot Is Not Used In RootSearch *****) Contrary to what Andrzej Kozlowski said my RootSearch package doesn't use Mathematica's FindRoot. I had to write my own implementations of Secant-Method and Brent's-Method to give RootSearch some of it's nice features. (****** RootSearch posts a message about $MinPrecision=-Infinity ******) With recent versions of Mathematica RootSearch posts a message about $MinPrecision=-Infinity. This is due to a few places where my implementation uses Block[ {$MinPrecision=-Infinity}, expr ] It makes more sense to use the following instead. Block[ {$MinPrecision=0}, expr ] You can make that change in the code and RootSearch will stop posting the message with no adverse consequences. (****** My Next RootSearch Version ******) A while ago I started work on a major overhaul of my code. I have made slow progress on it with the little bit of time I have for Mathematica. Ted Ersek (*********** References ***********) [1] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00009.html [2] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00148.html [3] http://blog.wolfram.com/2008/12/18/mathematica-7-johannes-kepler-and-transce ndental-roots/ [4] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00168.html [5] http://demonstrations.wolfram.com/SolvingSystemsOfTranscendentalEquations/