Implement more sophisticated strategies for detecting zero-crossings

[albert-mathews]

when _find_active_events, you carefully handle the required "direction" of the event. However, when _find_event_time, it looks like the direction might be overlooked. If that is the case, then it is possible that _find_event_time returns a time that is earlier than the first valid time, since there may be a root that is earlier, but does not match the direction criteria. Is this possible? If not, then I would certainly appreciate help improving my understanding.

[ralfgerlich]

Your assessment is correct. The current event handler implicitly assumes that there is at most one zero-crossing event during a single simulation step. If that assumption is correct, _find_event_time will properly detect only events with the desired direction, as the direction has been previously checked in _find_active_events.

If that assumption is not correct, we would need a different way of detecting events in any case, e.g., by subsampling the simulation interval or by using interval search. This will be adressed in #32.

[ralfgerlich]

Properly split the issues. #32 now only addresses handling of Zeno behaviour, and this one addresses event detection and localization.

There are several strategies for event detection and localization. Zhang et al, 2008 (https://doi.org/10.3182/20080706-5-KR-1001.01346) provides a good entry point.
The main issues are

• dependable detection of zero-crossings, specifically when an even number of zero-crossings occur over the time interval of the respective integration step, and
• efficient localization of the zero-crossings, specifically the crossing with the minimum time index.

The current approach cannot detect even numbers of zero crossings and cannot guarantee the detection of the actual first crossing matching the direction criterion set for the event.

Zhang et al mention three major approaches:

• Step size feedback control using the dynamics of the zero-crossing function (Park and Barton, 1996, https://doi.org/10.1145/232807.232809),
• subsampling of the integration step and application of the classical sign-change check in combination with a classical root-finding algorithm (mentioned without reference by Zhang et al, 2008), and
• detection and localization using interval arithmetics (Pantelides et al, 1988, https://doi.org/10.1016/0098-1354(88)85062-2).

While the step size feedback-control-based approach can guarantee the proper detection and localisation of a single event, it requires modification of the integrator. Specifically, it requires a solver for differential-algebraic-equations, which currently is not available, at least not in scipy. An integration of the state-of-the-art DASKR solver (Brown, Hindmarsh and Petzold, 1998, https://doi.org/10.1137/S1064827595289996) into scipy would help here.

Zhang et al introduce the subsampling approach as the most efficient in their list, without going into detail about the reasons. The approach merely shifts the issue of the original approach (no detection of even-numbered sign changes, no guarantee for finding the first zero-crossing, handling direction constraints). However, it is clearly the simplest of the approaches in terms of implementation and may prove sufficient for most applications.

The approach by Pantelides et al uses interval arithmetic for filtering and the convergence-properties of the Newton-Rhapson-root-finding method combined in the Krawczyk Operator to implement a divide-and-conquer approach for localisation of unique roots. Successively subdividing the time interval of interest and using an interval-convergence check, the method can determine whether a given interval does not contain any roots or a unique root. If neither can be guaranteed, the interval is split and the test is repeated on the new parts. The approach is a bit more involved and requires a polynomial interpolation of the event function with respect to time - introducing possible inaccuracies as well - but for a given class of event functions it can be guaranteed to be correct.

Both the interval-based approach by Pantelides et al and the subsampling approach mentioned by Zhang et al have high potential for implementation. For that, new implementations of the _EventDetector class implementing the different strategies can be created and the Simulator class can be parameterized further to enable users to select a suitable event detection strategy.