4 ms·

Intel has an ODE solver [1] that seems unbelievably good at solving certain kinds of differential equations. I'm surprised/disappointed it wasn't even mentioned

Intel has an ODE solver [1] that seems unbelievably good at solving certain kinds of differential equations. I'm surprised/disappointed it wasn't even mentioned. I would've loved to see an evaluation of it against MATLAB (or other solvers) more than any other pair in the list. [1] https://software.intel.com/en-us/articles/intel-ordinary-differential-equations-solver-library https://software.intel.com/en-us/articles/intel-ordinary-dif...

keldaris 9y ago
Could you elaborate on what's "unbelievably good" about it? From a quick glance at the site and documentation I don't see any particularly distinguishing features.
- throwaway613834 9y ago
  Sure. Digging through my old emails, here's the particular example (a very stiff Van der Pol equation) I was looking at, taken from Intel's own examples, which for MATLAB would be: tic; [t, x] = ode15s( @(t, x) [x(2); ((1 - x(1)^2) * x(2) - x(1)) * 10^6], [0, 160], [2; 0], odeset('RelTol', 1e-5)); toc; x(size(x, 1), :) MATLAB takes 7.2 seconds to output the result [1.872, -0.748]. Intel's dodesol_rkm9mkn() gave me [1.877, -0.743], which is a more accurate result, in less than the blink of an eye: in 0.035 seconds. That's more than 200x faster, by mere virtue of using a better algorithm. Apparently the algorithm is "Merson's method", which I'm completely unfamiliar with and which I'd never heard of until then.
  - RBerenguel 9y ago
    Do the initials stand for Runge-Kutta-Merson, order 9? I wonder about the other 3 (mkn)
    - throwaway613834 9y ago
      I believe those are the initials, yes. The "9" refers to the maximum number of "stages" which is not the same thing as the order of the solver. The (m,k) refer to the corresponding parameters of the method (I think). The "n" at the end is for "numerical" Jacobian (as opposed to "a" for user-provided/"analytical"). There should be a PDF in the download that explains these better than I possibly can (though it's still somewhat terse).
      - RBerenguel 9y ago
        I had a look before asking but could not find anything before the download. Thanks, it piqued my curiosity (used to write & theoretically analyse several numerical integrators back in my teaching days)
  - ChrisRackauckas 9y ago
    I don't think this really backs up your statement though. I am not at all surprised by this result. In the post I mentioned that MATLAB wasn't really designed for efficiency, and in this repo I show how even with explicit Runge-Kutta methods (i.e. the exact same methods, and these methods are simple enough that there isn't too much variation in implementation details sans getting it all to SIMD/FMA/etc.) you can get orders of magnitude better than MATLAB: https://github.com/JuliaDiffEq/MATLABDiffEq.jl https://github.com/JuliaDiffEq/MATLABDiffEq.jl So since stiff solvers have a lot more moving parts and thus tend to have even larger differences, 200x is easily explained by just language differences. One way to test this is to instead test the Intel solver against Sundials. I wouldn't be surprised if Sundials actually was faster in this case. But there's another factor here. I explained in the blog post that multistep methods like BDF tend to do well on asymtopically large problems since they minimize the amount of user-function evaluations, but they don't tend to do well on smaller systems of ODEs. This is exactly that case: you're comparing an implicit RK (Intel) to MATLAB's BDF method, and see that the RK is more accurate and is fast. But this effect of the method choice on small (user-scale) problems is exactly why I emphasized it as a downside when solver suites only include multistep BDF methods as their stiff solvers. That isn't to say there isn't interesting here. Intel's nonstiff method is a 4th order method that can add extra 1st order stages to boost the stability region, similar to a Runge-Kutta Chevyshev method. I honestly have no idea what this stiff solver is so I bookmarked it to read when I get to a campus where the paper is free: http://www.sciencedirect.com/science/article/pii/0041555389900578 http://www.sciencedirect.com/science/article/pii/00415553899... But in general, RKC methods weren't widely adopted because usually using a full non-stiff or stiff solver ends of being better, and picking wildly different methods like this which are not widely known usually isn't a good sign in a very "crowded" field like ODE solvers where generally things are pretty figured out and it's all about the details.
    - throwaway613834 9y ago
      > I don't think this really backs up your statement though. I'm not sure which statement you're reading, but everything you said so far is in agreement with my statement: >> Intel has an ODE solver that seems unbelievably good at solving certain kinds of differential equations. I'm surprised/disappointed it wasn't even mentioned. I would've loved to see an evaluation of it against MATLAB (or other solvers) more than any other pair in the list. Note that I have specifically stated that this method seems better on (at least) certain kinds of equations, and that, therefore, I would have loved to see a comparison of it with everything else. In particular, note that I never claimed the method Intel uses is better, at least (especially?) not in general. If I knew that to be the case, I wouldn't have even had a reason to hope for a comparison! The entire point of my comment was that I would be interested in an evaluation of its performance, and I'm glad to see that you feel similarly. :)
  - ChrisRackauckas 9y ago
    I went ahead and ran some stuff on my laptop. using DifferentialEquations van = @ode_def_noinvhes VanDerPol2 begin dy = μ*((1-x^2)*y - x) dx = 1*y end μ=>1. prob = ODEProblem(VanDerPol2(μ=1e6),[0;2.],(0.0,160.0)) solve(prob,CVODE_BDF(),reltol=1/10^5,save_everystep=false) solve(prob,Rodas5(),reltol=1/10^5,save_everystep=false) @time sol1 = solve(prob,CVODE_BDF(),reltol=1/10^5,save_everystep=false) @time sol2 = solve(prob,Rodas5(),reltol=1/10^5,save_everystep=false) sol3 = solve(prob,CVODE_BDF(),abstol=1/10^10,reltol=1/10^10) On my laptop I'm getting ~0.1 seconds for both, with Sundials being a little less accurate and OrdinaryDiffEq.jl being a little more accurate against the 10^-10 reference solution than the reported Intel. But "spot checking" like this makes it hard to just timings without issues of more/less error involved, which is why more sophisticated benchmarks use work-precision diagrams. So the timings are in the same ballpark as Intel and I'd assume my (not so fast) laptop doesn't match what you benchmarked with, the point being that MATLAB is just slow here instead of Intel being unbelievably exceptional (though admirable). Still, maybe Intel does pull off some extra efficiency here, but then of course no method is universally good so I wouldn't expect that everywhere. In the end, it's probably a well optimized (probably in the DiffEq.jl/Sundials/FATODE range) single method without event handling or other extra features, but importantly it is abandoned. Probably would've been interesting if development kept up, but without it I think I'm just not going to try to get it installed. Thanks for pointing me to it though. It's definitely an interesting nugget of ODE history that I didn't know existed.
    - throwaway613834 9y ago
      > Probably would've been interesting if development kept up, but without it I think I'm just not going to try to get it installed. Out of curiosity, why is this an issue? Wouldn't you have just downloaded the library and run it regardless of whether someone is actively developing it or not? I don't really understand this argument (and I see many people making it, not just you).
      - ChrisRackauckas 9y ago
        Well vanilla ODE solvers are a dime a dozen. Sufficiently optimized stiff ODE solvers tend to get around the same efficiency, with some methods doing better on some problems, and others doing better on other problems. So it's all problem dependent and this is just one implicit RK method, while things like ARKODE already have quite a few, FATODE has quite a few, and DifferentialEquations.jl has quite a few, etc, meaning I wouldn't expect it to be too different. What would make it exciting to play with if it added something. Free parallelism or uses the Xeon Phi automatically, complex number support, event handling (many examples where this is necessary. One: PDE solvers need this for adding projection steps). But since development has halted, we're pretty much guaranteed that none of this will ever come.
SloopJon 9y ago
Intel's ODE solver library appears to be pre-release software, retired in 2011, that was only licensed for "internal testing and development."
- throwaway613834 9y ago
  That's the ironic thing about it. At least for the examples I've tried (probably a biased subset, but still), it beats the crap out of the couple of commercial solvers I've tried.
snaky 9y ago
Might it be somewhat related to the 'Neuromorphic Chip' recently announced by Intel - which is, as discussed here on HN[1], being especially good for approximating dynamic systems and to use symbolic computation? [1] https://news.ycombinator.com/item?id=15334533 https://news.ycombinator.com/item?id=15334533

keldaris 9y ago

Could you elaborate on what's "unbelievably good" about it? From a quick glance at the site and documentation I don't see any particularly distinguishing features.

throwaway613834 9y ago
Sure. Digging through my old emails, here's the particular example (a very stiff Van der Pol equation) I was looking at, taken from Intel's own examples, which for MATLAB would be: tic; [t, x] = ode15s( @(t, x) [x(2); ((1 - x(1)^2) * x(2) - x(1)) * 10^6], [0, 160], [2; 0], odeset('RelTol', 1e-5)); toc; x(size(x, 1), :) MATLAB takes 7.2 seconds to output the result [1.872, -0.748]. Intel's dodesol_rkm9mkn() gave me [1.877, -0.743], which is a more accurate result, in less than the blink of an eye: in 0.035 seconds. That's more than 200x faster, by mere virtue of using a better algorithm. Apparently the algorithm is "Merson's method", which I'm completely unfamiliar with and which I'd never heard of until then.
- RBerenguel 9y ago
  Do the initials stand for Runge-Kutta-Merson, order 9? I wonder about the other 3 (mkn)
  - throwaway613834 9y ago
    I believe those are the initials, yes. The "9" refers to the maximum number of "stages" which is not the same thing as the order of the solver. The (m,k) refer to the corresponding parameters of the method (I think). The "n" at the end is for "numerical" Jacobian (as opposed to "a" for user-provided/"analytical"). There should be a PDF in the download that explains these better than I possibly can (though it's still somewhat terse).
    - RBerenguel 9y ago
      I had a look before asking but could not find anything before the download. Thanks, it piqued my curiosity (used to write & theoretically analyse several numerical integrators back in my teaching days)
- ChrisRackauckas 9y ago
  I don't think this really backs up your statement though. I am not at all surprised by this result. In the post I mentioned that MATLAB wasn't really designed for efficiency, and in this repo I show how even with explicit Runge-Kutta methods (i.e. the exact same methods, and these methods are simple enough that there isn't too much variation in implementation details sans getting it all to SIMD/FMA/etc.) you can get orders of magnitude better than MATLAB: https://github.com/JuliaDiffEq/MATLABDiffEq.jl https://github.com/JuliaDiffEq/MATLABDiffEq.jl So since stiff solvers have a lot more moving parts and thus tend to have even larger differences, 200x is easily explained by just language differences. One way to test this is to instead test the Intel solver against Sundials. I wouldn't be surprised if Sundials actually was faster in this case. But there's another factor here. I explained in the blog post that multistep methods like BDF tend to do well on asymtopically large problems since they minimize the amount of user-function evaluations, but they don't tend to do well on smaller systems of ODEs. This is exactly that case: you're comparing an implicit RK (Intel) to MATLAB's BDF method, and see that the RK is more accurate and is fast. But this effect of the method choice on small (user-scale) problems is exactly why I emphasized it as a downside when solver suites only include multistep BDF methods as their stiff solvers. That isn't to say there isn't interesting here. Intel's nonstiff method is a 4th order method that can add extra 1st order stages to boost the stability region, similar to a Runge-Kutta Chevyshev method. I honestly have no idea what this stiff solver is so I bookmarked it to read when I get to a campus where the paper is free: http://www.sciencedirect.com/science/article/pii/0041555389900578 http://www.sciencedirect.com/science/article/pii/00415553899... But in general, RKC methods weren't widely adopted because usually using a full non-stiff or stiff solver ends of being better, and picking wildly different methods like this which are not widely known usually isn't a good sign in a very "crowded" field like ODE solvers where generally things are pretty figured out and it's all about the details.
  - throwaway613834 9y ago
    > I don't think this really backs up your statement though. I'm not sure which statement you're reading, but everything you said so far is in agreement with my statement: >> Intel has an ODE solver that seems unbelievably good at solving certain kinds of differential equations. I'm surprised/disappointed it wasn't even mentioned. I would've loved to see an evaluation of it against MATLAB (or other solvers) more than any other pair in the list. Note that I have specifically stated that this method seems better on (at least) certain kinds of equations, and that, therefore, I would have loved to see a comparison of it with everything else. In particular, note that I never claimed the method Intel uses is better, at least (especially?) not in general. If I knew that to be the case, I wouldn't have even had a reason to hope for a comparison! The entire point of my comment was that I would be interested in an evaluation of its performance, and I'm glad to see that you feel similarly. :)
- ChrisRackauckas 9y ago
  I went ahead and ran some stuff on my laptop. using DifferentialEquations van = @ode_def_noinvhes VanDerPol2 begin dy = μ*((1-x^2)*y - x) dx = 1*y end μ=>1. prob = ODEProblem(VanDerPol2(μ=1e6),[0;2.],(0.0,160.0)) solve(prob,CVODE_BDF(),reltol=1/10^5,save_everystep=false) solve(prob,Rodas5(),reltol=1/10^5,save_everystep=false) @time sol1 = solve(prob,CVODE_BDF(),reltol=1/10^5,save_everystep=false) @time sol2 = solve(prob,Rodas5(),reltol=1/10^5,save_everystep=false) sol3 = solve(prob,CVODE_BDF(),abstol=1/10^10,reltol=1/10^10) On my laptop I'm getting ~0.1 seconds for both, with Sundials being a little less accurate and OrdinaryDiffEq.jl being a little more accurate against the 10^-10 reference solution than the reported Intel. But "spot checking" like this makes it hard to just timings without issues of more/less error involved, which is why more sophisticated benchmarks use work-precision diagrams. So the timings are in the same ballpark as Intel and I'd assume my (not so fast) laptop doesn't match what you benchmarked with, the point being that MATLAB is just slow here instead of Intel being unbelievably exceptional (though admirable). Still, maybe Intel does pull off some extra efficiency here, but then of course no method is universally good so I wouldn't expect that everywhere. In the end, it's probably a well optimized (probably in the DiffEq.jl/Sundials/FATODE range) single method without event handling or other extra features, but importantly it is abandoned. Probably would've been interesting if development kept up, but without it I think I'm just not going to try to get it installed. Thanks for pointing me to it though. It's definitely an interesting nugget of ODE history that I didn't know existed.
  - throwaway613834 9y ago
    > Probably would've been interesting if development kept up, but without it I think I'm just not going to try to get it installed. Out of curiosity, why is this an issue? Wouldn't you have just downloaded the library and run it regardless of whether someone is actively developing it or not? I don't really understand this argument (and I see many people making it, not just you).
    - ChrisRackauckas 9y ago
      Well vanilla ODE solvers are a dime a dozen. Sufficiently optimized stiff ODE solvers tend to get around the same efficiency, with some methods doing better on some problems, and others doing better on other problems. So it's all problem dependent and this is just one implicit RK method, while things like ARKODE already have quite a few, FATODE has quite a few, and DifferentialEquations.jl has quite a few, etc, meaning I wouldn't expect it to be too different. What would make it exciting to play with if it added something. Free parallelism or uses the Xeon Phi automatically, complex number support, event handling (many examples where this is necessary. One: PDE solvers need this for adding projection steps). But since development has halted, we're pretty much guaranteed that none of this will ever come.

SloopJon 9y ago

Intel's ODE solver library appears to be pre-release software, retired in 2011, that was only licensed for "internal testing and development."

throwaway613834 9y ago
That's the ironic thing about it. At least for the examples I've tried (probably a biased subset, but still), it beats the crap out of the couple of commercial solvers I've tried.

snaky 9y ago

Might it be somewhat related to the 'Neuromorphic Chip' recently announced by Intel - which is, as discussed here on HN[1], being especially good for approximating dynamic systems and to use symbolic computation? [1] https://news.ycombinator.com/item?id=15334533 https://news.ycombinator.com/item?id=15334533