Downsampling is slow

[pleroy]

There has to be a better way to approximate a trajectory by a low-degree polynomial. The current implementation does O(N Ln N) evaluations of the cubic sequentially.

[rnlahaye]

I can see two approaches:

1. The error in a cubic approximation can be bounded using the fourth derivative of the underlying function. Using this bound, a semi-optimal cubic spline can be constructed in O(N) time. Of course this bound is not exact and the constructed spline might not be optimal.
2. If you are willing to restrict the segments of the spline to powers of 2 (i.e. the endpoints would be of the form (k*2^i, (k + 1)*2^i)), an optimal spline can be constructed in O(N log log N) time.

I'd be happy to send a PR for either of them.

[rnlahaye]

Note for the first approach that there is a nice bound for cubic Hermite splines in particular; see Lemma 1 from this paper by Carlson and Hall.

[pleroy]

Note that I am not at all sure that a cubic is really what we want, it was just convenient when this code was implemented. Once you have specified continuity of the position and velocity at the endpoints, a cubic doesn't give you many degrees of freedom (understatement!). A higher degree polynomial, like we use for continuous trajectory, might be preferable.

If we look at the problem as trying to find a point in a suitable function space that is "close enough" to the trajectory, I have a hunch that we could be sublinear as long as we are not looking for the closest possible match. Pick a subset of the points, find an approximation, add more points, repeat until the approximation stabilizes.

[rnlahaye]

Since vessels are user controllable, their trajectories can have weird kinks in them. I don’t see any way to detect these without checking every point (although of course these checks do not have to be performed at interpolation time; they can be performed when the points are initially added to the trajectory).

That is, I don’t think it is possible to do better than O(N) amortized.

[eggrobin]

although of course these checks do not have to be performed at interpolation time; they can be performed when the points are initially added to the trajectory

This ties into our ideas in https://github.com/mockingbirdnest/Principia/issues/2400#issuecomment-830861942 (the sections of trajectory that do not contain burns should not be serialized, and thus the burns need to be flagged in some fashion).

It would probably be a good idea to have a more concrete plan on that side before we start changing the representation from an interpolating spline to something else (downsampling and reanimation will have to coëxist, the former to make sizes mangeable in memory, and the latter to keep saves small).

[pleroy]

Going forward it will be important to separate burns from coasts, both for serialization and for downsampling. I have some ideas about serialization, but I won't start coding until the stuff in Grassmannian is finalized.

Regarding downsampling: The burns are integrated using an adaptive step integrator, it's not even clear that downsampling buys us a lot, as the integrator adapts to the kinks. Surely errors of 10 m are excessive, e.g., when doing a rendezvous. The coasts on the other hand must be close to arcs of conics, so I am hoping to reuse some of the work that didn't quite pan out for #2400.

[pleroy]

Possible low-hanging fruit: I ran into this code which seems rather dumb: https://github.com/mockingbirdnest/Principia/blob/9e6326d7db6412cf78686e30c4541f32b9fb6fea/physics/discrete_trajectory_body.hpp#L311-L328 In the very common case where these functions are called with an actual point of the trajectory, maybe they could avoid constructing an interpolation and just do a lookup in the map instead.