Computing bounds on a function over an interval

[jagot]

Background:
I want to find all zero crossings of a function, expanded over a basis. I decided I'd give IntervalRootFinding.jl a shot. In essence, IntervalRootFinding.roots needs to evaluate the function (and its derivative) on an interval x and expects an interval y back which holds the minimum and maximum values attained by the function (derivative) on x.

Now, since my function is expressed as a linear combination of basis functions, my best idea so far is to find the corresponding interval y_i for the ith basis function, multiply this interval by the expansion coefficient (which will flip the interval if the coefficient is negative) and sum all the minima and maxima. We cannot simply use the union of the intervals since two functions on top each other would necessarily increase the interval. At the same time, for two disjoint functions, adding the intervals would make the bound looser than it necessarily needs to be. Is there a way to find a tighter bound?

How would the interface for finding the extrema of each basis function over an interval look like? If B isa Basis, with continuous first dimension, extrema(B, interval) could e.g. return a vector of intervals, but I am not sure if this is the best way. It would also be dependent on which particular implementation of Interval one chooses (IntervalSets.jl, IntervalArithmetic.jl, etc.).

Finally, is there a more clever way to find roots than this?

[dlfivefifty]

It should be consistent with vectors, that is,

julia> extrema([1,5,2])
(1, 5)

means extrema(::AbstractQuasiVector{T}) should return a NTuple{N,T} of the extrema. If you want it to return intervals then the T should be an interval.

[jagot]

Fine, but how would I limit the interval within which to compute the bounds? This sort of makes sense to me:

extrema(B[Inclusion(a..b),:]*coeffs)

[jagot]

That interface works well, but it turned out trickier than anticipated to compute good bounds; they need to be rather tight for IntervalRootFinding.jl to function.

EDIT: I had to go with extrema(applied(*, B[Inclusion(a..b),:], coeffs)) instead, since the multiplication drops the restriction along the first dimension.

[dlfivefifty]

This is a bug.

Note that Inclusion should be split into two types, QuasiSlice and Inclusion. At the moment some of the code assumes that an Inclusion is equivalent to QuasiSlice (that is, :) which is why you are seeing these bugs. I just haven't had a need to fix it.