Next: Irreducible Complexity
Up: Table of contents
Previous: Algebraic multigrid

The computational difficulty is one of the main characteristics of complex systems and the time necessary for their investigation and/or simulation grows very fast with their size. The systematic classification of the the difficulty and complexity of computational tasks is a classical problem in computer science.

The emergence of large time scales is often related to random fluctuations of Multi-Agent spatial structures within the system. Long range and long times scale hierarchies (=Critical Slowing Down (CSD)) are usually related to collective degrees of freedom (macros) characterizing the effective dynamics at each scale.

Usually, it is the dynamics of the macros during simulations which produces the Critical Slowing Down (CSD) and reciprocally, the slow modes of the simulation dynamics project out the relevant macros.

Therefore, a better theoretical understanding of the Multi-Agent structure of the system, enables one to construct better algorithms by acting directly on the relevant macros. Reciprocally, understanding the success of a certain algorithm yields a deeper knowledge of the relevant emerging collective objects of the system.

Many complex systems in biophysics, biology, psychophysics and cognition display similar properties generalizing the universality classes and scaling of the statistical mechanics critical systems. This is an unifying effect over a very wide range of phenomena spreading over most of the contemporary scientific fields. In the absence of a rigorous theoretical basis for such wide area of application, the investigation of these effects relies for the moment mainly on a case-by-case studies.

The perception of Critical Slowing Down as an unwanted feature of the simulations, lead into oblivion in the past studies the fundamental importance of CSD as a tool in identifying the relevant Macros and their critical dynamics.

However, in the context of Reduced CSD (RCSD) algorithms the fact that the acceleration of the dynamics of a certain mode eliminates/reduces  CSD is a clear sign that the critical degrees of freedom were correctly identified and their dynamics correctly understood.

RCSD algorithms express and validate in an objective way (by reducing the dynamical critical exponent z) our previous intuitive understanding of the collective macroscopic dynamics of large ensembles of microscopic elementary objects.

In certain systems, which resist the conceptualization of their understanding in closed analytic formulae, this kind of "algorithmic operational understanding" might be the only alternative.

With this in mind, one may attempt to use CSD and its elimination (reduction) as a quantitative measure of the "understanding" of the model's critical properties.

For instance an algorithm leading to z=2 would contain a very low level of understanding while the "ultimate" level of understanding is when one needs not simulate the model at all in order to get the properties of systems independently of their size (z=0 or analytic understanding).

An extreme case are the simulations of spin glasses where for naive simulations the correlation times increase faster then exponentially with the size of the system but where belief propagation techniques have proved quite efficient. 

In simplicial quantum gravity the increase is faster than any function. This is the "ultimate" CSD: computability; that is, impossibility to compute within a systematic approximation procedure the numbers "predicted" by the theory.

The rise of incomputability in the context of the Multi-Agent approach allows a new perspective on the issues of predictability  and reductionism: the possibility arises that the future state the universe is physically totally determined by its present state, yet the future state cannot be predicted because its physical parameters as determined by the theory are mathematically uncomputable numbers.

(Unfortunately this fascinating point falls outside the scope of present document.)

Until now for non-complex, simple problems one would have only two possibilities: to know or not to know. However, as explained above, withn the multi-agent complex paradigm there are intermediate degrees of understanding. One way to categorized them is by the ability to eliminate or reduce the CSD. In many models embedding a knowledge that we have about the model can result in a better (faster) dynamics.

Often, the way to a "more efficient algorithm" passes through the understanding of the "relevant collective objects" and their dynamics.

There are few "tests" to establish that for a given critical system the set of

Macro's was correctly identified:

- One would need to make sure that there is a "large" number of Macro's.

This requirement makes sure that a large fraction of the relevant degrees of freedom is indeed represented by the Macro's that were discovered.

- Then one has to check that they are relevant in the sense that they are not just symmetries of the theory. In other words, a change in an Macro should have an influence on the important measurables of the system.

- One of the more stringent tests is to verify that the resulting Macro dynamics is "free". That is, in a typical configuration of Micro's the resulting dynamics of the Macro seems to be free. This is a signal that the correct Macro have been identified.

An analogy for the relation between Macro's and Micro's can be found in language. The letters would be the Micro's and the words will be the Macro's.

Of course, manipulating words amounts to manipulating letters.

However when one "works"  in the words-level one need not bother with the letter-level, even though these two levels co-exist.

The macros may overlap rather than being separated by sharp boundaries.

In fact, the same Micro may belong (to various degrees) to more than one Macro. This "fuzziness" rends the boundaries defining a Macro a "subjective" choice, a matter of degree/opinion, which, while not affecting the validity of the numerical algorithm, sets the scene for further conceptual elasticity.

 It suggests continuous interpolation and extrapolation procedures closer in their form and essence to the working of the natural human intelligence.

In fact, through substituting the binary logic of the Micros with the continuous one of the Macros, one may avoid the no-go theorems, the paradoxes and the puzzles related to (un)computability, (i}reversibility and (creative) reasoning.

The precise yet "smeared" formulation of the Macros within the multi-agent multiscale modeling approach bypasses these classical conceptual puzzles arising in the naive reductionist methods. In particular, while the Macros acquire a certain degree of reality, individuality and causal behavior at the macroscopic level, their conceptual boundaries are fuzzy enough to avoid the paradoxes which would arise should one try to apply Macro categories in the microscopic domain (their boundaries "dissolve" gracefully as one tries to resolve them with a too sharp "microscope").

In the Multi-Agent Multiscale framework, there is no contradiction between considering the ocean as a set of molecules or a mass of waves. These are just complementary pictures relevant at different scales.

Next: Irreducible Complexity
Up: Table of contents
Previous: Algebraic multigrid