You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Connor Petty <mi...@gmail.com> on 2016/03/12 02:50:59 UTC
[Math] MullerSolver2 does not respect initial bracketing
I've been doing some investigation regarding MATH-1333 and I cam across
some bounds issues in MullerSolver and MullerSolver2. There are a few test
cases I've created which cause these solvers to return values outside of
their initial bracket. I've created fixes for MullerSolver but
MullerSolver2 baffles me. MullerSolver is more or less an implementation of
the algorithm you can find at https://en.wikipedia.org/wiki/Muller's_method
while MullerSolver2 is an implementation of the algorithm at
http://mathworld.wolfram.com/MullersMethod.html. But the major difference
between MullerSolver 1 & 2 is that MullerSolver2 was designed to work
without bracketing. This turns out to make it fairly easy to make it return
faulty values.
Now my question is: How much should these solvers stick to their original
algorithms? If the original algorithm is flawed should solver exhibit those
same flaws?
There is some precedent for that in SecantSolver which has the same
guarantees of convergence as the original algorithm (which has none).
But MullerSolver2 is clearly a patched version of the algorithm it is based
off of and exhibits some very characteristic flaws from the original
algorithm. Should MullerSolver2's bounds issue be fixed or should that
issue just be accepted a limitation of that algorithm?
Best Regards,
Connor Petty
Re: [Math] MullerSolver2 does not respect initial bracketing
Posted by Connor Petty <mi...@gmail.com>.
Ok, so is it correct to say that it doesn't matter how close these solvers
match the original algorithm as long as the differences between the
original and our implementation are well documented?
I should also note that the bracketing behavior in MullerSolver is not part
of the original algorithm nor is some of MullerSolver2's erroneous state
recovery logic (for handling complex roots and straight lines). Now, it
would be fair to say that MullerSolver2 is a more "pure" implementation of
Muller's method since the original Muller's method never used bracketing.
Given that bracketing is not part of the original Muller's Method, would
that also mean that in our Muller's Method implementation it should
completely reasonable (and in some cases expected) for the implementation
to return values outside of the original bracket?
Or is it our goal to make sure that all solver implementations always
return a value within the bracket even if it means changing the original
algorithm to support bracketing?
I'm assuming that the latter is preferred since the bracketing behavior is
expected by users.
Best Regards,
Connor Petty
On Fri, Mar 11, 2016 at 6:34 PM, Gilles <gi...@harfang.homelinux.org>
wrote:
> Hi.
>
> On Fri, 11 Mar 2016 17:50:59 -0800, Connor Petty wrote:
>
>> I've been doing some investigation regarding MATH-1333 and I cam across
>> some bounds issues in MullerSolver and MullerSolver2. There are a few test
>> cases I've created which cause these solvers to return values outside of
>> their initial bracket. I've created fixes for MullerSolver but
>> MullerSolver2 baffles me. MullerSolver is more or less an implementation
>> of
>> the algorithm you can find at
>> https://en.wikipedia.org/wiki/Muller's_method
>> while MullerSolver2 is an implementation of the algorithm at
>> http://mathworld.wolfram.com/MullersMethod.html. But the major difference
>> between MullerSolver 1 & 2 is that MullerSolver2 was designed to work
>> without bracketing. This turns out to make it fairly easy to make it
>> return
>> faulty values.
>>
>> Now my question is: How much should these solvers stick to their original
>> algorithms?
>>
>
> Fully.
> Or the name and documentation of the class must clearly reflect that
> it is a variation.
>
> If the original algorithm is flawed should solver exhibit those
>> same flaws?
>>
>
> Yes (if the flaw is in the algorithm itself, not just in the
> implementation,
> e.g. because the expected properties assume infinite precision).
>
> But whenever possible the implementation should (_must_, IMHO) check that
> it has not hit one of its own limitation, and "fail early".
>
> There is some precedent for that in SecantSolver which has the same
>> guarantees of convergence as the original algorithm (which has none).
>> But MullerSolver2 is clearly a patched version of the algorithm
>>
>
> Do you have the possibility to check another implementation of that
> algorithm?
> Since the Javadoc says that the original deals with complex values but CM
> avoids it, I wonder whether this could be the problem.
>
> it is based
>> off of and exhibits some very characteristic flaws from the original
>> algorithm. Should MullerSolver2's bounds issue be fixed or should that
>> issue just be accepted a limitation of that algorithm?
>>
>
> Cf. above.
>
> Best regards,
> Gilles
>
>
>> Best Regards,
>> Connor Petty
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [Math] MullerSolver2 does not respect initial bracketing
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sun, 13 Mar 2016 14:01:18 -0700, Connor Petty wrote:
> On Fri, Mar 11, 2016 at 6:34 PM, Gilles
> <gi...@harfang.homelinux.org>
> wrote:
>
>> Hi.
>>
>> On Fri, 11 Mar 2016 17:50:59 -0800, Connor Petty wrote:
>>
>>> I've been doing some investigation regarding MATH-1333 and I cam
>>> across
>>> some bounds issues in MullerSolver and MullerSolver2. There are a
>>> few test
>>> cases I've created which cause these solvers to return values
>>> outside of
>>> their initial bracket. I've created fixes for MullerSolver but
>>> MullerSolver2 baffles me. MullerSolver is more or less an
>>> implementation
>>> of
>>> the algorithm you can find at
>>> https://en.wikipedia.org/wiki/Muller's_method
>>> while MullerSolver2 is an implementation of the algorithm at
>>> http://mathworld.wolfram.com/MullersMethod.html. But the major
>>> difference
>>> between MullerSolver 1 & 2 is that MullerSolver2 was designed to
>>> work
>>> without bracketing. This turns out to make it fairly easy to make
>>> it
>>> return
>>> faulty values.
>>>
>>> Now my question is: How much should these solvers stick to their
>>> original
>>> algorithms?
>>>
>>
>> Fully.
>> Or the name and documentation of the class must clearly reflect that
>> it is a variation.
>>
>> If the original algorithm is flawed should solver exhibit those
>>> same flaws?
>>>
>>
>> Yes (if the flaw is in the algorithm itself, not just in the
>> implementation,
>> e.g. because the expected properties assume infinite precision).
>>
>> But whenever possible the implementation should (_must_, IMHO) check
>> that
>> it has not hit one of its own limitation, and "fail early".
>>
>> There is some precedent for that in SecantSolver which has the same
>>> guarantees of convergence as the original algorithm (which has
>>> none).
>>> But MullerSolver2 is clearly a patched version of the algorithm
>>>
>>
>> Do you have the possibility to check another implementation of that
>> algorithm?
>>
> Since the Javadoc says that the original deals with complex values
> but CM
>> avoids it, I wonder whether this could be the problem.
>>
>
> Well, the concepts of Muller's Method will remain the same regardless
> of
> implementation: root finding by using quadratic 3-point
> interpolation.
> Muller's method will find real and complex roots
Is the original method intended to return *all* roots?
> but the solvers
You mean the CM implementations of the method?
There is a solver implementation that returns all (complex) roots:
"LaguerreSolver".
[IIRC, there is a pending issue that "complex" solvers should have
their own hierarchy.]
> only care
> about the real roots so changes have to be made to make sure that you
> either never encounter complex roots or you somehow handle encounters
> with
> complex roots. MullerSolver is designed to never encounter complex
> roots
> using bracketing
My opinion is that this must be fixed in any case since it does not
comply with the documented behaviour (in Javadoc and code).
> while MullerSolver2 is designed to "handle" complex roots.
Does that mean that one root is picked "arbitrarily"?
> Now I say "handle" because the only way you can escape a situation
> where
> the interpolation produces a complex root is to essentially make up a
> value
> and hope it is closer to the real root (usually is). So yes, the way
> complex values are dealt with is large part of the problem.
If that means that by changing undocumented "internal details" of the
implementation, the selected root can change, I wonder what purpose it
can have.
Regards,
Gilles
>
>
>>
>> it is based
>>> off of and exhibits some very characteristic flaws from the
>>> original
>>> algorithm. Should MullerSolver2's bounds issue be fixed or should
>>> that
>>> issue just be accepted a limitation of that algorithm?
>>>
>>
>> Cf. above.
>>
>> Best regards,
>> Gilles
>>
>>
>>> Best Regards,
>>> Connor Petty
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] MullerSolver2 does not respect initial bracketing
Posted by Connor Petty <mi...@gmail.com>.
On Fri, Mar 11, 2016 at 6:34 PM, Gilles <gi...@harfang.homelinux.org>
wrote:
> Hi.
>
> On Fri, 11 Mar 2016 17:50:59 -0800, Connor Petty wrote:
>
>> I've been doing some investigation regarding MATH-1333 and I cam across
>> some bounds issues in MullerSolver and MullerSolver2. There are a few test
>> cases I've created which cause these solvers to return values outside of
>> their initial bracket. I've created fixes for MullerSolver but
>> MullerSolver2 baffles me. MullerSolver is more or less an implementation
>> of
>> the algorithm you can find at
>> https://en.wikipedia.org/wiki/Muller's_method
>> while MullerSolver2 is an implementation of the algorithm at
>> http://mathworld.wolfram.com/MullersMethod.html. But the major difference
>> between MullerSolver 1 & 2 is that MullerSolver2 was designed to work
>> without bracketing. This turns out to make it fairly easy to make it
>> return
>> faulty values.
>>
>> Now my question is: How much should these solvers stick to their original
>> algorithms?
>>
>
> Fully.
> Or the name and documentation of the class must clearly reflect that
> it is a variation.
>
> If the original algorithm is flawed should solver exhibit those
>> same flaws?
>>
>
> Yes (if the flaw is in the algorithm itself, not just in the
> implementation,
> e.g. because the expected properties assume infinite precision).
>
> But whenever possible the implementation should (_must_, IMHO) check that
> it has not hit one of its own limitation, and "fail early".
>
> There is some precedent for that in SecantSolver which has the same
>> guarantees of convergence as the original algorithm (which has none).
>> But MullerSolver2 is clearly a patched version of the algorithm
>>
>
> Do you have the possibility to check another implementation of that
> algorithm?
>
Since the Javadoc says that the original deals with complex values but CM
> avoids it, I wonder whether this could be the problem.
>
Well, the concepts of Muller's Method will remain the same regardless of
implementation: root finding by using quadratic 3-point interpolation.
Muller's method will find real and complex roots but the solvers only care
about the real roots so changes have to be made to make sure that you
either never encounter complex roots or you somehow handle encounters with
complex roots. MullerSolver is designed to never encounter complex roots
using bracketing while MullerSolver2 is designed to "handle" complex roots.
Now I say "handle" because the only way you can escape a situation where
the interpolation produces a complex root is to essentially make up a value
and hope it is closer to the real root (usually is). So yes, the way
complex values are dealt with is large part of the problem.
>
> it is based
>> off of and exhibits some very characteristic flaws from the original
>> algorithm. Should MullerSolver2's bounds issue be fixed or should that
>> issue just be accepted a limitation of that algorithm?
>>
>
> Cf. above.
>
> Best regards,
> Gilles
>
>
>> Best Regards,
>> Connor Petty
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [Math] MullerSolver2 does not respect initial bracketing
Posted by Gilles <gi...@harfang.homelinux.org>.
Hi.
On Fri, 11 Mar 2016 17:50:59 -0800, Connor Petty wrote:
> I've been doing some investigation regarding MATH-1333 and I cam
> across
> some bounds issues in MullerSolver and MullerSolver2. There are a few
> test
> cases I've created which cause these solvers to return values outside
> of
> their initial bracket. I've created fixes for MullerSolver but
> MullerSolver2 baffles me. MullerSolver is more or less an
> implementation of
> the algorithm you can find at
> https://en.wikipedia.org/wiki/Muller's_method
> while MullerSolver2 is an implementation of the algorithm at
> http://mathworld.wolfram.com/MullersMethod.html. But the major
> difference
> between MullerSolver 1 & 2 is that MullerSolver2 was designed to work
> without bracketing. This turns out to make it fairly easy to make it
> return
> faulty values.
>
> Now my question is: How much should these solvers stick to their
> original
> algorithms?
Fully.
Or the name and documentation of the class must clearly reflect that
it is a variation.
> If the original algorithm is flawed should solver exhibit those
> same flaws?
Yes (if the flaw is in the algorithm itself, not just in the
implementation,
e.g. because the expected properties assume infinite precision).
But whenever possible the implementation should (_must_, IMHO) check
that
it has not hit one of its own limitation, and "fail early".
> There is some precedent for that in SecantSolver which has the same
> guarantees of convergence as the original algorithm (which has none).
> But MullerSolver2 is clearly a patched version of the algorithm
Do you have the possibility to check another implementation of that
algorithm?
Since the Javadoc says that the original deals with complex values but
CM
avoids it, I wonder whether this could be the problem.
> it is based
> off of and exhibits some very characteristic flaws from the original
> algorithm. Should MullerSolver2's bounds issue be fixed or should
> that
> issue just be accepted a limitation of that algorithm?
Cf. above.
Best regards,
Gilles
>
> Best Regards,
> Connor Petty
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org