Re: CAS and interval computation and pseudo-values like infinity, undefined

Christopher Creutzig wrote:

Assuming you want to evaluate x^3+x^2-2*x+1, it does not look
reasonable to me to first find a tight enclosure of x^3+x^2 just to
throw the result away afterwards. That was my point when asking about
putting this dependency analysis in the overloading of operators. This
is not really an issue if the analysis takes place at compilation stage,
but with CAS I usually think of interactive and/or interpreted
evaluation of at least some of the formulas.

I agree that you can save effort by looking at a whole expression and
compiling it into an interval evaluation without intermediate steps.
The right way to do this is to try to find one (or more) formulas that
minimize the width. Transforming expressions into "single use
expressions" when possible.

And with polynomials of degree > 2, I do think the evaluation type is
important. Sure you can find the extreme values for a univariate
polynomial, but most real-world problems are multivariate and this
approach may be too slow to be of use. Then again, it may not.

This is hard to judge in advance: you pay for a tighter interval. How
much is it worth?

If f is a polynomial, you hardly need AD to compute f'. A simple

True. But you are essentially doing it nevertheless. :-) And for large
degrees, it may be worth while truncating the polynomial just like an
infinite Taylor series. It depends on the problem.

be produced as well, in a time comparable to evaluating f(x). So if
computing f(x) takes time T, you can get f(x), f'(x), and error(f(x))
in about 3T.

I'm probably not interested in these three values. What I'm interested
in is an enclosure of f(center(x)) and one of f'(x), for x an interval,
to find a sharper enclosure of f(x) than with a direct computation.

I do not see, offhand, that computing an interval for f' is less work
than computing an interval for f. It is commonly thought that f' is
simpler than f, but this is generally not true. Our impresions are
based on the common case of polynomials, but consider that d(u*v*w) =
u'*v*w+u*v'*w +u*v*w' etc. so the growth may be substantial, and in
the case of intervals, the "dependency" problem may be worse. (perhaps
so-called logarithmic derivatives would look simpler. )


Thank you for the opportunity to let us see some unfinished thoughts
by someone else than ourselves.


It is great to get comments. The originally referenced draft paper
will be revised.
RJF

.

Relevant Pages

  • Re: GCD of multivariate polynomials
    ... I am looking for writing a program for computing the GCD of two ... multivariate polynomials in a fast and efficient way. ... >is necessary to simplify ratios of polynomials to simplest form. ...
    (sci.math.symbolic)
  • Re: Distance problem
    ... I need some help with computing the distance between the polynomial x->x^2 to the subspace of polynomials of degree less than or equal to 1. ...
    (sci.math)
  • Distance problem
    ... I need some help with computing the distance between the polynomial x->x^2 to the subspace of polynomials of degree less than or equal to 1. ...
    (sci.math)