You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Tim O'Brien <to...@discursive.com> on 2003/05/27 13:27:42 UTC
[math] Priority
On Tue, 2003-05-27 at 11:00, Mark R. Diggory wrote:
> Basically what this is saying is "talk to us". ACM is suggesting
> involvement and acknowledgment of their efforts in organizing and
> archiving these algorithms...<snip>...Open Source
> Apache project and the legal bindings they would want in such a
> relationship..
-1
I welcome greater participation especially from the ACM, but I also
encourage people not to "jump the gun". Commons-math is a sandbox
component, nothing guarantees promotion to Commons proper. Commons-math
is not attempting to be a repository for all numerical algorithms - at
least not in the current proposal.
The scope as defined in the proposal is very limited to encourage
developers to submit patches focused on a small set of realistic goals.
aimed at a real-world requirements.
I'd like to see us explore an idea of providing an interface to other
implementations of algorithms (i.e. commons-logging), but I think that
is something for *the future*. Right now, we need focus, unit tests,
pages of detailed documentation, and attention to detail.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by "Mark R. Diggory" <md...@latte.harvard.edu>.
Tim O'Brien wrote:
>On Tue, 2003-05-27 at 11:00, Mark R. Diggory wrote:
>
>
>>Basically what this is saying is "talk to us". ACM is suggesting
>>involvement and acknowledgment of their efforts in organizing and
>>archiving these algorithms...<snip>...Open Source
>>Apache project and the legal bindings they would want in such a
>>relationship..
>>
>>
>
>-1
>
>I welcome greater participation especially from the ACM, but I also
>encourage people not to "jump the gun". Commons-math is a sandbox
>component, nothing guarantees promotion to Commons proper. Commons-math
>is not attempting to be a repository for all numerical algorithms - at
>least not in the current proposal.
>
>
+1 Yes I do agree that we should not focus on being a repository for all
numerical algoithms.
>The scope as defined in the proposal is very limited to encourage
>developers to submit patches focused on a small set of realistic goals.
>aimed at a real-world requirements.
>
>
IMHO, I don't consider this discussion to be "jumping the gun" or out of
scope of the issues realted to this project. My primary point is that if
your interested in using/developing code based on an algorithm published
by the ACM, that instead of looking at the license and say, nope, can't
do that. You contact the responsible parties at ACM and ask them
directly concerning if you can apply it in this case. Seems overly
"assuming" to do otherwise. Finally, I wanted to state is that there was
also a probible future of activity between ACM and Apache Math
developers considering such cases.
>I'd like to see us explore an idea of providing an interface to other
>implementations of algorithms (i.e. commons-logging), but I think that
>is something for *the future*. Right now, we need focus, unit tests,
>pages of detailed documentation, and attention to detail.
>
>
Yes, I think that would be intersting, I suspect in the future we will
see cases wher ethis can be applied.
Cheers,
-Mark
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by "J.Pietschmann" <j3...@yahoo.de>.
Brent Worden wrote:
> I agree. The this looks like a very solid framework. One suggestion I
> would like to make, is instead of a both a firstDirevative and
> secondDerivate method to evaluate the derivates. Create a single
> getDerivate() method that returns a UnivariateRealFunction. That way if a
> user needs the n-th derivate, they just call the getDerivate() method n
> times, once on the original function and once on each of the returned
> functions. That way, common-math supports creating whatever degree derivate a
> method might need without ever having to change the framework. We provide
> the maximum amout of derivate creation support to the user while providing
> us with the minimual amount of maintenance.
Given that numerical algorithms try to avoid derivatives
for a number of reasons, a generic method to calculate
potentially arbitrary derivatives seems to be overkill.
In fact, only very few methods even use a second derivative.
Furthermore, the implementor of the function should know best
how the derivatives are calculated. Note that the contract
allows for numerical derivatives (although this is discouraged).
If a function object is returned, implementation is decoupled,
and higher derivatives might be implemented by someone who
does not match the precision and performance perceptions of
the implementor of the base function.
I'd like to keep it all in one object for this reasons.
I know this may seem to be a bit inconvenient for people who
want to find a zero of a derivative of a function they just
see lying around, but you definitely don't want to solve a
numerical derivative for a root, you'll just get garbage.
> Why not allow the user to supply any number of initial values and design the
> solvers to compensate as best they can when not enough values are provided.
> Each algorithm has criteria about the initial values that must be met before
> root finding can be attempted. If the user provided initial values do not
> satisfy the criteria, the solver should first attempt to morph the initial
> values into a set of values that do satisfy the criteria. If this can not
> be accomplish, then the solver would raise an exception. This would take
> away some of the user's responsibility of knowing how these algorithms
> actually work and place it on us to create more robust components.
The user should have some rough ideas of the interval of the root.
It could be quite a large interval, but then the solver may complain.
There is no "best" algorithm, which can take arbitrary functions
and start values and produce a root with a reasonable amount of work.
Also, many functions have multiple roots. An exhaustive search for
all roots is often impossible. Therefore, the interval is mostly to
prevent the solver from finding a root outside of the domain of
interest for the user. There is no way to get the user's domain of
interest without explicit input.
J.Pietschmann
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by Phil Steitz <ph...@steitz.com>.
Brent Worden wrote:
> "J.Pietschmann" <j3...@yahoo.de> wrote in message
> news:3ED655F4.7000903@yahoo.de...
>
>>Phil Steitz wrote:
>>
>>>Can you provide a math reference desribing this?
>>
>>H.M.Antia: Num. Methods for Scientists and Engineers.
>>
>>
>>> I have been referring
>>>to Atkinson and I am having a hard time following the implementation.
>>>What exactly do you mean by "only inverse quadratic interpolation"?
>>
>>Brent's method requires a bracketed root as a start. The primary
>>method for shrinking the bracket is inverse quadratic interpolation.
>>This means you get three points
>> x0,y0 x1,y1 x2,y2 x0<x2<x1
>>and interpolate a parabola
>> x=a*y^2+b*y+c
>>and because your goal is to find the x for y=0, your next estimate
>>for the root is c (set y=0). The convergence is of the order 1.8,
>>which is better than the secant method (~1.4 if non bracketing, 1..1.2
>>on average if bracketing).
>>The full Brent algorithm measures how well the interval shrinks, and
>>resorts to bisection if progress is too slow. I didn't implement this
>>because I forgot to take the book with me and had only a hazy memory
>>of the control parameters. All in all the algorithm combines
>>near-guaranteed convergence (occasionally problems might falsely
>>detected as ill-conditioned) with near Newton-speed.
>>
>>
>>>What do you have in mind re: plausibility?
>>
>>If the interval to search is (x0,x1), then absAccuracy should be of
>>the order of max(abs(x0),abs(x1))*relAccuracy. Achievable relative
>>accuracy depends on underlying hardware, although nowadays basically
>>everyone uses IEEE 754 (means, uh, 52 bit for double? Damn, have to
>>look it up!). Both relative and absolute accuracy of function
>>evaluation are also important, which is the reason to let the user
>>override defaults.
>>This means if relAcc is given then reject absAcc if
>> max(abs(x0),abs(x1))*relAcc+c*absAcc == max(abs(x0),abs(x1))*relAcc
>>for some predermined constant c in 0.2..1.
>>
>>
>>>I guess I like your rootfinding framework better than Brent's (Here I
>>>mean Brent Worden, the famous commons-math contributor, not the
>>>numerical analyst). I suggest that we agree to use your interfaces and
>>>UnivariateRealSolverImpl base,include Brent's bisection implementation
>>>strategy and modify his CDF inversion to use the new rootfinding
>>
> framework.
>
>>No argument against :-) I took special care for the JavaDocs, which
>>seems to pay off...
>
>
> I agree. The this looks like a very solid framework. One suggestion I
> would like to make, is instead of a both a firstDirevative and
> secondDerivate method to evaluate the derivates. Create a single
> getDerivate() method that returns a UnivariateRealFunction. That way if a
> user needs the n-th derivate, they just call the getDerivate() method n
> times, once on the original function and once on each of the returned
> functions. That way, common-math supports creating whatever degree derivate
> a
> method might need without ever having to change the framework. We provide
> the maximum amout of derivate creation support to the user while providing
> us with the minimual amount of maintenance.
Mathematically, that is certainly a natural suggestion. I am not sure,
however, how easy it will be to implement in UnivariateRealFunction
implementations (contract will be tricky regarding existence) or how
often it will actually be used. Given that the rootfinding solutions
that we seem to be converging on (pun intended) for the first release do
not require derivative computations,
one thing we might consider would be to remove derivatives entirely from
the UnivariateRealFunction interface for now.
It may be more natural for an R->R function to mark itself (infinitely?)
differentiable by implementing a DifferentiableUnivariateRealFunction
(getting a bit long, but you get the idea) interface that extends
UnivariateRealFunction than to not throw exceptions or return null or
"NaF" (not a function, of course) when you ask it for its derivative.
>
>
>>>I do have a few small questions/comments on the framework:
>>>
>>>1. Having solve() *require* brackets makes it impossible (or at least,
>>>un-natural) to add Newton's method or any other method that just starts
>>>with one initial value.
>>
>>Why? Start with -4000000,+4000000000 or so. The algorithm is not
>>*required* to start with a bracket, just with an interval. Individual
>>solver implementations should document whether they require a bracket.
>>Apart from this, there is always the possiblity to add another method.
>
>
> Why not allow the user to supply any number of initial values and design the
> solvers to compensate as best they can when not enough values are provided.
> Each algorithm has criteria about the initial values that must be met before
> root finding can be attempted. If the user provided initial values do not
> satisfy the criteria, the solver should first attempt to morph the initial
> values into a set of values that do satisfy the criteria. If this can not
> be accomplish, then the solver would raise an exception. This would take
> away some of the user's responsibility of knowing how these algorithms
> actually work and place it on us to create more robust components.
>
>
>>>2. I am curious as to why the "result" property is there. How exactly
>>>do we expect clients to make use of this?
>>
>>The client can ask for the last result as long as no further attempt
>>to solve for another root was made. I found this handy. I don't insist
>>on keeping it.
>>
>>
>>>3. What were you thinking about putting into the base solve()
>>>implementation as diagnostics? Do you mean things like checking to make
>>>sure the bracket is good?\
>>
>>No, just adding a message indicating that an unimplemented method
>>was called. Some frameworks don't display the type of the exception
>>to the user and rely on the message.
>>
>>
>>>4. Thinking of the developers who will use this stuff, I feel like we
>>>need a way to insulate them from having to think about rootfinding
>>>strategy choice. As Al has pointed out, we are not (at least yet ;-))
>>>in the AI business, so we can't automagically make the best choice for
>>>them; but it might be a good idea to somehow specify a default strategy.
>>
>
> A simple and flexible way to make the "best" choice for the user, is to
> control the creation of solver instances.
> This could be done via a factory or factory method. The creation could be
> based on the class of function the user want to evaluate (real, polynomial,
> rational, etc.) Also, we could create a solver chain that provides the
> ability to link various solvers together so if a solver fails to find a
> root, the next solver in the chain is given a chance to solve it. Either,
> eventually one of the solvers finds a root or all solvers fail and an
> exception is raised. The complexity of creating the "best chain" would be
> contained in the factory or factory method, totally hidden from the user.
> This again would relieve users of having some numerical method knowledge
> about root finding methods.
Nice idea; but do we really need to do this? See below.
>
>
>>> Unfortunately, the "safe" choice would likely be bisection.
>>
>>Brent's algorithm is quite safe in this respect.
>
>
> I'm by no means beholden to bisection. I just used it because I needed
> something to use for the distribution work. Brent's algorithm is
> guarranteed to converge to a root, provided one is bracketed by the initial
> values. So, if a bracket can be provided or generated, it is just as good
> as bisection as far as safety and it should almost always beat it in speed
> of convergence.
I agree. I suggest that we make the necessary adjustments, test the heck
out of it, beg Al, J. and whatever other numerical analysts we can find
to review it, and annoint Richard Brent's algorithm as our Solver and,
while leaving the extensibility in the framework, we do not add any
other strategies to the initial release.
>
>
>>I'll see whether I can complete the implementation near term.
>
> Unfortunately
>
>>I'll go on vacation on saturday and will be offline until 2003-06-09.
>>
>>
>>J.Pietschmann
>
>
> Brent Worden
> http://www.brent.worden.org
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by Brent Worden <br...@worden.org>.
"J.Pietschmann" <j3...@yahoo.de> wrote in message
news:3ED655F4.7000903@yahoo.de...
> Phil Steitz wrote:
> > Can you provide a math reference desribing this?
>
> H.M.Antia: Num. Methods for Scientists and Engineers.
>
> > I have been referring
> > to Atkinson and I am having a hard time following the implementation.
> > What exactly do you mean by "only inverse quadratic interpolation"?
>
> Brent's method requires a bracketed root as a start. The primary
> method for shrinking the bracket is inverse quadratic interpolation.
> This means you get three points
> x0,y0 x1,y1 x2,y2 x0<x2<x1
> and interpolate a parabola
> x=a*y^2+b*y+c
> and because your goal is to find the x for y=0, your next estimate
> for the root is c (set y=0). The convergence is of the order 1.8,
> which is better than the secant method (~1.4 if non bracketing, 1..1.2
> on average if bracketing).
> The full Brent algorithm measures how well the interval shrinks, and
> resorts to bisection if progress is too slow. I didn't implement this
> because I forgot to take the book with me and had only a hazy memory
> of the control parameters. All in all the algorithm combines
> near-guaranteed convergence (occasionally problems might falsely
> detected as ill-conditioned) with near Newton-speed.
>
> > What do you have in mind re: plausibility?
> If the interval to search is (x0,x1), then absAccuracy should be of
> the order of max(abs(x0),abs(x1))*relAccuracy. Achievable relative
> accuracy depends on underlying hardware, although nowadays basically
> everyone uses IEEE 754 (means, uh, 52 bit for double? Damn, have to
> look it up!). Both relative and absolute accuracy of function
> evaluation are also important, which is the reason to let the user
> override defaults.
> This means if relAcc is given then reject absAcc if
> max(abs(x0),abs(x1))*relAcc+c*absAcc == max(abs(x0),abs(x1))*relAcc
> for some predermined constant c in 0.2..1.
>
> > I guess I like your rootfinding framework better than Brent's (Here I
> > mean Brent Worden, the famous commons-math contributor, not the
> > numerical analyst). I suggest that we agree to use your interfaces and
> > UnivariateRealSolverImpl base,include Brent's bisection implementation
> > strategy and modify his CDF inversion to use the new rootfinding
framework.
>
> No argument against :-) I took special care for the JavaDocs, which
> seems to pay off...
I agree. The this looks like a very solid framework. One suggestion I
would like to make, is instead of a both a firstDirevative and
secondDerivate method to evaluate the derivates. Create a single
getDerivate() method that returns a UnivariateRealFunction. That way if a
user needs the n-th derivate, they just call the getDerivate() method n
times, once on the original function and once on each of the returned
functions. That way, common-math supports creating whatever degree derivate
a
method might need without ever having to change the framework. We provide
the maximum amout of derivate creation support to the user while providing
us with the minimual amount of maintenance.
>
> > I do have a few small questions/comments on the framework:
> >
> > 1. Having solve() *require* brackets makes it impossible (or at least,
> > un-natural) to add Newton's method or any other method that just starts
> > with one initial value.
>
> Why? Start with -4000000,+4000000000 or so. The algorithm is not
> *required* to start with a bracket, just with an interval. Individual
> solver implementations should document whether they require a bracket.
> Apart from this, there is always the possiblity to add another method.
Why not allow the user to supply any number of initial values and design the
solvers to compensate as best they can when not enough values are provided.
Each algorithm has criteria about the initial values that must be met before
root finding can be attempted. If the user provided initial values do not
satisfy the criteria, the solver should first attempt to morph the initial
values into a set of values that do satisfy the criteria. If this can not
be accomplish, then the solver would raise an exception. This would take
away some of the user's responsibility of knowing how these algorithms
actually work and place it on us to create more robust components.
>
> > 2. I am curious as to why the "result" property is there. How exactly
> > do we expect clients to make use of this?
>
> The client can ask for the last result as long as no further attempt
> to solve for another root was made. I found this handy. I don't insist
> on keeping it.
>
> > 3. What were you thinking about putting into the base solve()
> > implementation as diagnostics? Do you mean things like checking to make
> > sure the bracket is good?\
>
> No, just adding a message indicating that an unimplemented method
> was called. Some frameworks don't display the type of the exception
> to the user and rely on the message.
>
> > 4. Thinking of the developers who will use this stuff, I feel like we
> > need a way to insulate them from having to think about rootfinding
> > strategy choice. As Al has pointed out, we are not (at least yet ;-))
> > in the AI business, so we can't automagically make the best choice for
> > them; but it might be a good idea to somehow specify a default strategy.
A simple and flexible way to make the "best" choice for the user, is to
control the creation of solver instances.
This could be done via a factory or factory method. The creation could be
based on the class of function the user want to evaluate (real, polynomial,
rational, etc.) Also, we could create a solver chain that provides the
ability to link various solvers together so if a solver fails to find a
root, the next solver in the chain is given a chance to solve it. Either,
eventually one of the solvers finds a root or all solvers fail and an
exception is raised. The complexity of creating the "best chain" would be
contained in the factory or factory method, totally hidden from the user.
This again would relieve users of having some numerical method knowledge
about root finding methods.
> > Unfortunately, the "safe" choice would likely be bisection.
>
> Brent's algorithm is quite safe in this respect.
I'm by no means beholden to bisection. I just used it because I needed
something to use for the distribution work. Brent's algorithm is
guarranteed to converge to a root, provided one is bracketed by the initial
values. So, if a bracket can be provided or generated, it is just as good
as bisection as far as safety and it should almost always beat it in speed
of convergence.
> I'll see whether I can complete the implementation near term.
Unfortunately
> I'll go on vacation on saturday and will be offline until 2003-06-09.
>
>
> J.Pietschmann
Brent Worden
http://www.brent.worden.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by "J.Pietschmann" <j3...@yahoo.de>.
Phil Steitz wrote:
> Can you provide a math reference desribing this?
H.M.Antia: Num. Methods for Scientists and Engineers.
> I have been referring
> to Atkinson and I am having a hard time following the implementation.
> What exactly do you mean by "only inverse quadratic interpolation"?
Brent's method requires a bracketed root as a start. The primary
method for shrinking the bracket is inverse quadratic interpolation.
This means you get three points
x0,y0 x1,y1 x2,y2 x0<x2<x1
and interpolate a parabola
x=a*y^2+b*y+c
and because your goal is to find the x for y=0, your next estimate
for the root is c (set y=0). The convergence is of the order 1.8,
which is better than the secant method (~1.4 if non bracketing, 1..1.2
on average if bracketing).
The full Brent algorithm measures how well the interval shrinks, and
resorts to bisection if progress is too slow. I didn't implement this
because I forgot to take the book with me and had only a hazy memory
of the control parameters. All in all the algorithm combines
near-guaranteed convergence (occasionally problems might falsely
detected as ill-conditioned) with near Newton-speed.
> What do you have in mind re: plausibility?
If the interval to search is (x0,x1), then absAccuracy should be of
the order of max(abs(x0),abs(x1))*relAccuracy. Achievable relative
accuracy depends on underlying hardware, although nowadays basically
everyone uses IEEE 754 (means, uh, 52 bit for double? Damn, have to
look it up!). Both relative and absolute accuracy of function
evaluation are also important, which is the reason to let the user
override defaults.
This means if relAcc is given then reject absAcc if
max(abs(x0),abs(x1))*relAcc+c*absAcc == max(abs(x0),abs(x1))*relAcc
for some predermined constant c in 0.2..1.
> I guess I like your rootfinding framework better than Brent's (Here I
> mean Brent Worden, the famous commons-math contributor, not the
> numerical analyst). I suggest that we agree to use your interfaces and
> UnivariateRealSolverImpl base,include Brent's bisection implementation
> strategy and modify his CDF inversion to use the new rootfinding framework.
No argument against :-) I took special care for the JavaDocs, which
seems to pay off...
> I do have a few small questions/comments on the framework:
>
> 1. Having solve() *require* brackets makes it impossible (or at least,
> un-natural) to add Newton's method or any other method that just starts
> with one initial value.
Why? Start with -4000000,+4000000000 or so. The algorithm is not
*required* to start with a bracket, just with an interval. Individual
solver implementations should document whether they require a bracket.
Apart from this, there is always the possiblity to add another method.
> 2. I am curious as to why the "result" property is there. How exactly
> do we expect clients to make use of this?
The client can ask for the last result as long as no further attempt
to solve for another root was made. I found this handy. I don't insist
on keeping it.
> 3. What were you thinking about putting into the base solve()
> implementation as diagnostics? Do you mean things like checking to make
> sure the bracket is good?\
No, just adding a message indicating that an unimplemented method
was called. Some frameworks don't display the type of the exception
to the user and rely on the message.
> 4. Thinking of the developers who will use this stuff, I feel like we
> need a way to insulate them from having to think about rootfinding
> strategy choice. As Al has pointed out, we are not (at least yet ;-))
> in the AI business, so we can't automagically make the best choice for
> them; but it might be a good idea to somehow specify a default strategy.
> Unfortunately, the "safe" choice would likely be bisection.
Brent's algorithm is quite safe in this respect.
I'll see whether I can complete the implementation near term. Unfortunately
I'll go on vacation on saturday and will be offline until 2003-06-09.
J.Pietschmann
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by Phil Steitz <ph...@steitz.com>.
J.Pietschmann wrote:
> Brent Worden wrote:
>
>> In the chi-square patch, I created a root finding utility class. I
>> used the
>> bisection method to provide a default mechanism for computing inverse
>> CDFs.
>> It's driven by a simple Function interface. Check it out and see if it's
>> something you can use or improve.
>
>
> Here's my take on root finding. Note that BrentSolver uses only
> inverse quadratic interpolation rather than the full Brent algorithm.
Can you provide a math reference desribing this? I have been referring
to Atkinson and I am having a hard time following the implementation.
What exactly do you mean by "only inverse quadratic interpolation"? Am
I correct in assuming that what you mean by this is that you *never* use
Secant or Bisection? Looks to me like this is the case, but I am having
a little difficulty following the code. If it is the case, what impact
does this have on convergence/stability?
>
> THere are a few issues with accuracy, there should really be a
> relative accuracy too, as well as some plausiblity checks.
What do you have in mind re: plausibility?
I guess I like your rootfinding framework better than Brent's (Here I
mean Brent Worden, the famous commons-math contributor, not the
numerical analyst). I suggest that we agree to use your interfaces and
UnivariateRealSolverImpl base,include Brent's bisection implementation
strategy and modify his CDF inversion to use the new rootfinding framework.
I do have a few small questions/comments on the framework:
1. Having solve() *require* brackets makes it impossible (or at least,
un-natural) to add Newton's method or any other method that just starts
with one initial value. Brent W. includes a method that will try to
find a bracket from initial values. I suppose that we could add a
solve() with only one initial value and if necessary push it out to a
bracket. Personally, given the multiple good implementations available
now, I am OK with dropping Newton altogether, so this could be a moot
point at least for the initial release.
2. I am curious as to why the "result" property is there. How exactly
do we expect clients to make use of this?
3. What were you thinking about putting into the base solve()
implementation as diagnostics? Do you mean things like checking to make
sure the bracket is good?
4. Thinking of the developers who will use this stuff, I feel like we
need a way to insulate them from having to think about rootfinding
strategy choice. As Al has pointed out, we are not (at least yet ;-))
in the AI business, so we can't automagically make the best choice for
them; but it might be a good idea to somehow specify a default strategy.
Unfortunately, the "safe" choice would likely be bisection. We
could obviously annoint bisection as the "default" by naming it
something like "Solver", but there might be simpler/better ways to do this.
<flame-invitation> I bet that in most real world applications the
difference in convergence speed is not a big deal and guaranteed
convergence/domain of application is more important than expected speed
of convergence. Consider, for example, our own use in CDF inversion to
get critical values for stat tests. </flame-invitation>.
Phil
>
> J.Pietschmann
>
>
> ------------------------------------------------------------------------
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by "J.Pietschmann" <j3...@yahoo.de>.
Brent Worden wrote:
> In the chi-square patch, I created a root finding utility class. I used the
> bisection method to provide a default mechanism for computing inverse CDFs.
> It's driven by a simple Function interface. Check it out and see if it's
> something you can use or improve.
Here's my take on root finding. Note that BrentSolver uses only
inverse quadratic interpolation rather than the full Brent algorithm.
THere are a few issues with accuracy, there should really be a
relative accuracy too, as well as some plausiblity checks.
J.Pietschmann
Re: [math] Priority
Posted by Phil Steitz <ph...@steitz.com>.
Brent Worden wrote:
>>and unit tests. While things like rootfinding for
>>non-differentiable functions
>>may eventually have a place and may benefit from algorithms that
>>someone can
>>claim copyright ownership of, if no one else does it before I get
>>to it, I will
>>translate my simple newton's method implementation (which is trivial) and
>>submit it. I would appreciate input on what a nice Java interface
>>would look
>>like for rootfinding, initally assuming that the function has a
>>derivative, but
>>ideally extensible to support strategies that do not require
>>differentiability.
>
>
> In the chi-square patch, I created a root finding utility class. I used the
> bisection method to provide a default mechanism for computing inverse CDFs.
> It's driven by a simple Function interface. Check it out and see if it's
> something you can use or improve.
>
> The relevant types are org.apache.jakarta.commons.math.RootFinding and
> org.apache.jakarta.commons.math.Function and there it's utilized in
> org.apache.jakarta.commons.math.stat.distribution.AbstractContinuousDistribu
> tion.
>
> Let me know what you think.
>
Looks fine to me,at least. I was looking for some magical way to avoid
the "Function" interface requirement; but after thinking about this some
more and looking at your implementation, I think that is about as
convenient as we can make it for users. Newton's method or other
algorithms could be added as alternative RootFinding strategies. I
didn't think of bisection, which is a great idea for the CDF inversion
application, since these functions tend to be well-behaved. Thanks for
setting this up.
Phil
> Brent Worden
> http://www.brent.worden.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
RE: [math] Priority
Posted by Al Chou <ho...@yahoo.com>.
--- Brent Worden <br...@worden.org> wrote:
> > and unit tests. While things like rootfinding for
> > non-differentiable functions
> > may eventually have a place and may benefit from algorithms that
> > someone can
> > claim copyright ownership of, if no one else does it before I get
> > to it, I will
> > translate my simple newton's method implementation (which is trivial) and
> > submit it. I would appreciate input on what a nice Java interface
> > would look
> > like for rootfinding, initally assuming that the function has a
> > derivative, but
> > ideally extensible to support strategies that do not require
> > differentiability.
>
> In the chi-square patch, I created a root finding utility class. I used the
> bisection method to provide a default mechanism for computing inverse CDFs.
> It's driven by a simple Function interface. Check it out and see if it's
> something you can use or improve.
>
> The relevant types are org.apache.jakarta.commons.math.RootFinding and
> org.apache.jakarta.commons.math.Function and there it's utilized in
> org.apache.jakarta.commons.math.stat.distribution.AbstractContinuousDistribu
> tion.
>
> Let me know what you think.
>
> Brent Worden
> http://www.brent.worden.org
Brent,
I think I have a few improvements that came to mind while I was coding a
Ridders' method implementation. Should I send you a diff file privately?
Al
=====
Albert Davidson Chou
Get answers to Mac questions at http://www.Mac-Mgrs.org/ .
__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
RE: [math] Priority
Posted by Brent Worden <br...@worden.org>.
> and unit tests. While things like rootfinding for
> non-differentiable functions
> may eventually have a place and may benefit from algorithms that
> someone can
> claim copyright ownership of, if no one else does it before I get
> to it, I will
> translate my simple newton's method implementation (which is trivial) and
> submit it. I would appreciate input on what a nice Java interface
> would look
> like for rootfinding, initally assuming that the function has a
> derivative, but
> ideally extensible to support strategies that do not require
> differentiability.
In the chi-square patch, I created a root finding utility class. I used the
bisection method to provide a default mechanism for computing inverse CDFs.
It's driven by a simple Function interface. Check it out and see if it's
something you can use or improve.
The relevant types are org.apache.jakarta.commons.math.RootFinding and
org.apache.jakarta.commons.math.Function and there it's utilized in
org.apache.jakarta.commons.math.stat.distribution.AbstractContinuousDistribu
tion.
Let me know what you think.
Brent Worden
http://www.brent.worden.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Priority
Posted by Phil Steitz <st...@yahoo.com>.
--- Tim O'Brien <to...@discursive.com> wrote:
> On Tue, 2003-05-27 at 11:00, Mark R. Diggory wrote:
> > Basically what this is saying is "talk to us". ACM is suggesting
> > involvement and acknowledgment of their efforts in organizing and
> > archiving these algorithms...<snip>...Open Source
> > Apache project and the legal bindings they would want in such a
> > relationship..
>
> -1
>
> I welcome greater participation especially from the ACM, but I also
> encourage people not to "jump the gun". Commons-math is a sandbox
> component, nothing guarantees promotion to Commons proper. Commons-math
> is not attempting to be a repository for all numerical algorithms - at
> least not in the current proposal.
>
> The scope as defined in the proposal is very limited to encourage
> developers to submit patches focused on a small set of realistic goals.
> aimed at a real-world requirements.
>
> I'd like to see us explore an idea of providing an interface to other
> implementations of algorithms (i.e. commons-logging), but I think that
> is something for *the future*. Right now, we need focus, unit tests,
> pages of detailed documentation, and attention to detail.
>
I agree. I at least plan to keep plugging away providing simple standard-
algorithm implementations for stuff on the task list and filling out the docs
and unit tests. While things like rootfinding for non-differentiable functions
may eventually have a place and may benefit from algorithms that someone can
claim copyright ownership of, if no one else does it before I get to it, I will
translate my simple newton's method implementation (which is trivial) and
submit it. I would appreciate input on what a nice Java interface would look
like for rootfinding, initally assuming that the function has a derivative, but
ideally extensible to support strategies that do not require differentiability.
Phil
>
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
http://search.yahoo.com
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org