commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Bruce A Johnson <johns...@umbc.edu>
Subject Re: [math] puzzled by generics in root solvers
Date Wed, 06 Jul 2011 23:48:15 GMT
While there is a discussion of solvers going on I thought I would point out that I have done
a Java translation of Dario Bini's implementation of Aberth's method.  I've attached the header
of the original Fortran file below.  I'd be happy to donate my translation to Commons Math
if there is interest and if you all think Apache licensing is consistent with the copyright
given in the Fortran header.

I've done nothing to make it look like Commons Math code, though I do use the Commons Math
Complex class in the implementation.

And at this point I have no time to do any work on it, but if anyone else is interested let
me know.

Bruce





 ***************************************************************************
  * All the software  contained in this library  is protected by copyright. *
  * Permission  to use, copy, modify, and  distribute this software for any *
  * purpose without fee is hereby granted, provided that this entire notice *
  * is included  in all copies  of any software which is or includes a copy *
  * or modification  of this software  and in all copies  of the supporting *
  * documentation for such software.                                        *
  ***************************************************************************
  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED *
  * WARRANTY. IN NO EVENT, NEITHER  THE AUTHORS, NOR THE PUBLISHER, NOR ANY *
  * MEMBER  OF THE EDITORIAL BOARD OF  THE JOURNAL  "NUMERICAL ALGORITHMS", *
  * NOR ITS EDITOR-IN-CHIEF, BE  LIABLE FOR ANY ERROR  IN THE SOFTWARE, ANY *
  * MISUSE  OF IT  OR ANY DAMAGE ARISING OUT OF ITS USE. THE ENTIRE RISK OF *
  * USING THE SOFTWARE LIES WITH THE PARTY DOING SO.                        *
  ***************************************************************************
  * ANY USE  OF THE SOFTWARE  CONSTITUTES  ACCEPTANCE  OF THE TERMS  OF THE *
  * ABOVE STATEMENT.                                                        *
  ***************************************************************************

   AUTHOR:

       DARIO ANDREA BINI
       UNIVERSITY OF PISA, ITALY
       E-MAIL: bini@dm.unipi.it

   REFERENCE:

    -  NUMERICAL COMPUTATION OF POLYNOMIAL ZEROS BY MEANS OF
       ABERTH'S METHOD
       NUMERICAL ALGORITHMS, 13 (1996), PP. 179-200





On Jul 6, 2011, at 7:11 PM, Gilles Sadowski wrote:

> Hello.
> 
>> 
>> Here are my personal opinions on this entire discussion:
>> 
>> I'm not sure I like the auto-magic under the hood conversion from unbracketed solver
to bracketed solver.
> 
> It's not really "under the hood", as the user must specify an enum value to
> get the "bracketing". The default ("ANY_SIDE") will return the original
> output.
> 
>> I think the BracketingWrapperSolver that was proposed would keep the clear distinction
between the two.
>> This new classs would then have the purpose to do the conversion.
>> This takes the magic out of the process.
>> The new class has a very clear purpose that could be easily explained.
>> It is also a matter of separation of concerns.
>> Furthermore, using a non-bracketed algorithm you would expect to get non-bracketed
solutions.
>> Using the auto-magic conversion to bracketed solutions may change the properties
of the algorithms.
>> I also think it is important to have a clear separation by means of an interface
or base class to separate bracketing algorithms from non-bracketing algorithms.
> 
> Really, there is no mixing (cf. above).
> As a matter of principle, I'd agree with you on having another class etc.
> But in the current design, this leads to other drawbacks, as this discussion
> has shown. This design has eliminated shortcomings of the previous one, but
> it might not be good enough. However, as it is, the "BracketingWrapperSolver"
> is most probably not the optimal solution.
> 
> We also do not have a clear separation between algorithms that take a
> bracket (e.g. "BrentSolver") and those that don't (e.g. "NewtonSolver").
> If the "solve" methods called by the user contains more parameters than
> needed by the algorithm implemented in the instance, they will be ignored.
> [In some sense, this is even worst than the bracketing "enum" case. However,
> in both cases we could maybe assume that the user has a minimal knowledge of
> the concept implemented in the class which he is using. And, again, not
> specifying a parameter (in the call to "solve") won't do any harm ;-).]
> 
>> 
>> I think it would be preferable to not hardcode the PegasusSolver as 'fallback' bracketing
solver.
> 
> Yes, this is probably a good point.
> It could be solved by adding a "setBracketingSolver" method to the base
> class. If not explicitely specified, which one should be the default?
> 
>> It would be better to have a two parameter version of the BracketingWrapperSolver
constructor:
>> an instance of the non-bracketing solver, and an instance of the fallback bracketing
solver.
>> A one argument constructor could be added that does use the Pegasus as default.
>> There were also some numbers hard-coded. It would be preferable to have them configurable.
> 
> Another reason that I don't like this class is that it is somehow a
> user-level utility. Let's say that CM provides solvers; some are bracketing,
> some not. We'd say: "If you need a bracketing one, then use a bracketing
> one."
> Adding this interface plus an implementing class, plus three interfaces and
> three classes to hide the generic parameter is, IMHO, a bit too much to
> support for this kind of syntactic sugar.
> 
> However, if we do want to provide the utility, maybe that it should be considered
> as such and _not_ as a solver by itself. E.g. some method "refine" in some
> utility class:
> 
> public static double refine(UnivariateRealFunction f,
>                            double baseRoot,
>                            BracketingSolver solver,
>                            double epsilon,
>                            AllowedSolutions solutionType) {
>    // ...
> }
> where "baseRoot" is the root to refine (and we don't care how it was
> obtained).
> 
>> 
>> I'm not sure if it is easy to do, but I think it would be better to check if it is
necessary to use the 'fallback' bracketing solver.
>> If a non-bracketing solver already returned a solution that is on a valid side,
>> then that answer should be used, and the use of the fallback solver should be avoided.
>> I think we can do this by evaluating the function that the returned solution and
the
>> absolute tolerance before or after it (depending on the requested solution).
>> Also, the found solution is extended on both sides to obtain an interval,
>> which is then passed to the bracketing solver. If there is another root at the 'wrong'
>> side of the first solution, can we guarantee that the correct side is found?
>> Maybe we should only extend it to the direction where we need to find the new bracketed
solution?
> 
> Indeed, these are good questions. Once we agree on the interface, they should
> probably be the next steps to improve the functionality.
> 
>> 
>> I kind of like AllowedSolutions as argument to the solve(...) method.
>> I think it would be an improvement over a setAllowedSolutions, as it would make the
feature more prominent.
>> A version of the method without the argument should have the backwards compatible
behavior of
>> EITHER_SIDE (ANY_SIDE).
> 
> Indeed, that's what is supposed to happen with the (untested) code I had
> proposed.
> 
>> Either non-bracketing solvers should not have to implement the extended version of
the method, or they
>> should throw UnsupportedExceptions for solutions that they can not guarantee.
> 
> In principle, you are right.
> But in practice, we'd add an efficiency penalty to the algorithm by checking
> for unused arguments instead of simply ignoring them and assuming that the
> user knows what he does.
> 
>> 
>> Question: what other solvers that are available maintain a bracketed solution, besides
the secant-based methods?
> 
> "BrentSolver" (referring to Luc's nice ASCII art picture a few posts ago).
> 
> 
> Best regards,
> Gilles
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
> 
> 


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message