  In a recent paper we presented a new ultra efficient numerical method for
solving kinetic equations of the Boltzmann type (G. Dimarco, R. Loubere,
Towards an ultra efficient kinetic scheme. Part I: basics on the 689 BGK
equation, J. Comp. Phys., (2013), http://dx.doi.org/10.1016/j.jcp.2012.10.058).
The key idea, on which the method relies, is to solve the collision part on a
grid and then to solve exactly the transport part by following the
characteristics backward in time. On the contrary to classical semi-Lagrangian
methods one does not need to reconstruct the distribution function at each time
step. This allows to tremendously reduce the computational cost and to perform
efficient numerical simulations of kinetic equations up to the six dimensional
case without parallelization. However, the main drawback of the method
developed was the loss of spatial accuracy close to the fluid limit. In the
present work, we modify the scheme in such a way that it is able to preserve
the high order spatial accuracy for extremely rarefied and fluid regimes. In
particular, in the fluid limit, the method automatically degenerates into a
high order method for the compressible Euler equations. Numerical examples are
presented which validate the method, show the higher accuracy with respect to
the previous approach and measure its efficiency with respect to well known
schemes (Direct Simulation Monte Carlo, Finite Volume, MUSCL, WENO).
