[WIP] A Faster (Experimental) Version of Multiple Shooting

[avik-pal]

Main Idea

Place Nodes at points the BC is evaluate to minimize ODE Sensitivity Cost

How it is done?

• Create a wrapper around the ODESolution and capture the calls and store them in a vector!
• Indexing not supported
• Once we locate the points we just place the nodes at those points and continue as usual with Multiple Shooting
  • For the BC part, we no longer have to use Forward Sensitivity.
• We don't support grid-coarsening for now. But not very hard to support.

TODOs

• [ ] Tests
• [ ] Share more code
• [ ] Grid Coarsening
• [ ] Some more detailed benchmarks
• [ ] Ensure Project.toml doesn't have unnecessary dependencies

Benchmark

using BoundaryValueDiffEq, OrdinaryDiffEq

tspan = (0.0, π / 2)
function simplependulum!(du, u, p, t)
    g, L, θ, dθ = 9.81, 1.0, u[1], u[2]
    du[1] = dθ
    du[2] = -(g / L) * sin(θ)
end

function bc_pendulum!(residual, u, p, t)
    t0, t1 = extrema(t)
    residual[1] = u((t0 + t1) / 2)[1] + π / 2
    residual[2] = u(t1)[1] - π / 2 # the solution at the end of the time span should be pi/2
end

bvp1 = BVProblem(simplependulum!, bc_pendulum!, [π / 2, π / 2], tspan)

alg1 = MultipleShooting(100, Tsit5(); auto_static_nodes = Val(true))
alg2 = MultipleShooting(100, Tsit5(); auto_static_nodes = Val(false),
    grid_coarsening = false)

@benchmark solve(bvp1, alg1)

#=
BenchmarkTools.Trial: 713 samples with 1 evaluation.
 Range (min … max):  4.286 ms … 26.760 ms  ┊ GC (min … max):  0.00% … 62.69%
 Time  (median):     5.920 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   6.995 ms ±  3.894 ms  ┊ GC (mean ± σ):  14.13% ± 17.30%

      ▁█▅                                                     
  ▄▆▆████▅▅▄▄▃▂▃▂▂▁▂▁▂▁▁▁▂▁▂▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂▃▃▃▂▂ ▃
  4.29 ms        Histogram: frequency by time        21.3 ms <

 Memory estimate: 6.60 MiB, allocs estimate: 74812.
=#

@benchmark solve(bvp1, alg2)

#=
BenchmarkTools.Trial: 112 samples with 1 evaluation.
 Range (min … max):  24.958 ms … 94.565 ms  ┊ GC (min … max):  0.00% … 47.87%
 Time  (median):     33.904 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   44.865 ms ± 20.232 ms  ┊ GC (mean ± σ):  27.83% ± 25.83%

  ▇█▁▅  ▇▁                                     ▁  ▁            
  ████████▆▅▃▃▅▅▁█▃█▅▁▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▁█▆██▃▃█▃▆▁▃▃▃▁▁▁▃ ▃
  25 ms           Histogram: frequency by time        86.2 ms <

 Memory estimate: 71.60 MiB, allocs estimate: 881218.
=#

(The current benchmark is a bit contrived to show scale of improvements, but we see improvements even in the smallest cases)