It is well-known that customary direct solution methods (based on the discretization of the fluid fields) for the fluid equations of incompressible fluids may be affected by a high computational complexity. This is due primarily to the numerical solution of the Poisson equation for the fluid pressure and occurs when the scale-length of turbulent fluctuations becomes comparable to the discretization scale which characterizes the numerical solution method. An alternative, which can reduce significantly the complexity caused by the numerical solution of the fluid equations for incompressible fluids, may be achieved by so-called particle simulation methods. In such a case the dynamics of fluids is approximated in terms of a set of test particles which advance in time in terms of suitable evolution equations defined in such a way to satisfy identically the Poisson equation. Particle simulation methods rely typically on appropriate kinetic models for the fluid equations which permit the evaluation of the fluid fields in terms of suitable expectation values (or momenta) of the kinetic distribution function f(r,v,t), being respectively r and v the position an velocity of a test particle with probability density f(r,v,t). These kinetic models can be continuous or discrete in phase space, yielding respectively continuous or discrete kinetic models for the fluids. However, also particle simulation methods may be biased by an undesirable computational complexity. In particular, a fundamental issue is to estimate the algorithmic complexity of numerical simulations based on traditional LBM's (Lattice-Boltzmann methods; for review see Succi, 2001 <cite>Succi</cite>). These methods, based on a discrete kinetic approach, represent currently an interesting alternative to direct solution methods. Here we intend to prove that for incompressible fluids fluids LBM's may present a high complexity. The goal of the investigation is to present a detailed account of the origin of the various complexity sources appearing in customary LBM's. The result is relevant to establish possible strategies for improving the numerical efficiency of existing numerical methods.
