You are currently browsing the tag archive for the ‘Dynamical Systems’ tag.

Figure – Attractor basins (fig.2 pp.6 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Mária Ercsey-Ravasz and Zoltán Toroczkai have proposed a way of mapping satisfiability problems to differential equations and a deterministic algorithm that solves them in polynomial continuous time at the expense of exponential energy functions (so the discrete approximation of the algorithm does not run in polynomial time, and an analogue system would need exponential resources).

The map assigns a phase space to a problem; the algorithm chooses random initial conditions from within that phase space.  In the graphs above and below, they pick a 2-d subspace of the phase space and for each initial point in that space they illustrate 1) the particular solution the algorithm finds, 2) the corresponding “solution cluster”, an equivalence class of solutions that identifies two solutions if they differ in exactly one variable assignment, and 3) the time it takes to solve the problem.  Each row adds another clause to satisfy.

The especially interesting part of the paper is the notion of an escape rate,  the proportion of the trajectories still searching for a solution after a time t.  In a companion paper, they show that the escape rate for Sudoku combinatorial instances (The Chaos Within Sudoku, Nature, August 2012)  correlates strongly with human judgements of hardness. This escape rate is similar to the Kolmogorov complexity in that it gives a notion of hardness to individual problem instances rather than to classes of problems. Full paper could be retrieved from arXiv: Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011. (at arXiv on August 2012).

Figure – Attractor basins for 3-XORSAT (fig.8 pp.18 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Advertisements

“… words are not numbers, nor even signs. They are animals, alive and with a will of their own. Put together, they are invariably less or more than their sum. Words die in antisepsis. Asked to be neutral, they display allegiances and stubborn propensities. They assume the color of their new surroundings, like chameleons; they perversely develop echoes.” Guy Davenport, “Another Odyssey”, 1967. [above: painting by Mark Rothko – untitled]

Figure (clik to enlarge) – Applying P(0)=0.6; r=4; N=100000; for(n=0;n<=N;n++) { P(n+1)=r*P(n)*(1-P(n)); } Robert May Population Dynamics equation [1974-76] (do check on Logistic maps) for several iterations (generations). After 780 iterations, P is attracted to 1 (max. population), and then suddenly, for the next generations the very same population is almost extinguish.

Not only in research, but also in the everyday world of politics and economics, we would all be better off if more people realised that simple non-linear systems do not necessarily possess simple dynamical properties.” ~ Robert M. May, “Simple Mathematical models with very complicated Dynamics”, Nature, Vol. 261, p.459, June 10, 1976.

(…) The fact that the simple and deterministic equation (1) can possess dynamical trajectories which look like some sort of random noise has disturbing practical implications. It means, for example, that apparently erratic fluctuations in the census data for an animal population need not necessarily betoken either the vagaries of an unpredictable environment or sampling errors: they may simply derive from a rigidly deterministic population growth relationship such as equation (1). This point is discussed more fully and carefully elsewhere [1]. Alternatively, it may be observed that in the chaotic regime arbitrarily close initial conditions can lead to trajectories which, after a sufficiently long time, diverge widely. This means that, even if we have a simple model in which all the parameters are determined exactly, long term prediction is nevertheless impossible. In a meteorological context, Lorenz [15] has called this general phenomenon the “butterfly effect“: even if the atmosphere could be described by a deterministic model in which all parameters were known, the fluttering of a butterfly’s wings could alter the initial conditions, and thus (in the chaotic regime) alter the long term prediction. Fluid turbulence provides a classic example where, as a parameter (the Reynolds number) is tuned in a set of deterministic equations (the Navier-Stokes equations), the motion can undergo an abrupt transition from some stable configuration (for example, laminar flow) into an apparently stochastic, chaotic regime. Various models, based on the Navier-Stokes differential equations, have been proposed as mathematical metaphors for this process [15,40,41] . In a recent review of the theory of turbulence, Martin [42] has observed that the one-dimensional difference equation (1) may be useful in this context. Compared with the earlier models [15,40,41] it has the disadvantage of being even more abstractly metaphorical, and the advantage of having a spectrum of dynamical behaviour which is more richly complicated yet more amenable to analytical investigation. A more down-to-earth application is possible in the use of equation (1) to fit data [1,2,3,38,39,43] on biological populations with discrete, non-overlapping generations, as is the case for many temperate zone arthropods. (…) in pp. 13-14, Robert M. May, “Simple Mathematical models with very complicated Dynamics“, Nature, Vol. 261, p.459, June 10, 1976 [PDF link].

… fortunately for all of us.

The three stages of response to a new idea: 1. Ridicule 2. Outrage 3. Declaration that it’s obvious” ~ Arthur Schopenhauer.

[…] However, Cage himself never softened. The culture might have moved on, but he kept on his radical edge, continuing his revolution in a quiet way for those who cared not only to listen, but to act on and live by his words. Through the 1980’s, Cage’s influence was felt in the underground, influencing many of the more interesting cultural movements of that decade–the birth of indy rock, the renewal of Conceptual Art, and the rise of Language Poetry. Many of these artists studied Cage in the ’60s and ’70s and went on to synthesize newer aesthetic/cultural concerns with older Cageian ideals. While the 80’s played out in the media with Wall Street Yuppies and decadent consumerists grabbing the spotlight, many of us spent time on the edge of the culture, which in turn planted the seeds for the more politically charged times in which we now live. […] The final essay here is “Poethics of a Complex Realism” by Joan Retallack and note the word realism in the title. Retallack begins her essay with an invocation of American Pragmatist John Dewey’s “Art As Experience” and launches into a long discussion of the idea of weather as it relates to the ideas of John Cage. Cage said that he wanted his music to be like the weather–unpredictable, omnidirectional, impermanent, and always changing–complex systems that parallel the conditions of our daily life. He did several works involving the weather, modeling his ideas after nature (again, a tip of the hat to American Transcendentalist Henry David Thoreau), which are described here. Retallack takes the word play of weather/whether and sets up a correspondence between the physical (realized) and the theoretical (unrealized). She then posits an ethic based on the principle of weather/whether. Imagine, she says, a culture sophisticated and open enough to be able to accept difference and otherness, a culture that rejects the oversimplified media response of black/white, yes/no, a culture that embraces complexity and contradiction–a “breathable” culture. And it is here where the book brilliantly dovetails with the multicultural attitudes sweeping the country today. Cage stands in opposition to the reductive and closed ideas that multiculturalism have come to stand for. While multiculturalism plays by the media-supplied dualistic rules, Cage seems to dump the idea of rules altogether and instead celebrates the idea of difference and unpredictability as a prerequisite to understanding and accepting the difficulties inherent in a pluralistic culture. It appeals to this reader as the path of least resistance and being based in action, seems entirely workable. The multicultural debate has made many people aware of the issues, but it stands in theory only and lacks the kind of pragmatism and functionality that could lead to real change as prescribed here. […], in Kenneth Goldsmith, University of Buffalo, 1995, reviewing and revisiting “John Cage Composed In America“, Essays edited by Marjorie Perloff & Charles Junkerman 1994, 286 pages, paperback, The University of Chicago Press, USA.

Video – John Cage, appearing on a 1960 CBS gameshow called I’ve Got A Secret (from Ian Leslie + Alex Ross). Cage’s ‘secret’ is that he is an avant-garde composer. After being introduced by the presenter he performs a piece called Water Walk (… more).

Video -“Sand, sand, pile of sand” by Robert Proch (2009) – Impression without an idea, about trying to catch one (music by Pinkfreud).

Complex Adaptive Systems (CAS) are dynamic developing systems which arrange themselves according to external influences and to their own inner current state. If you are familiar with Conway’s “Game of Life“, you have an example of such a system. Complex adaptive systems arrange themselves around one or more critical factors (like in a sandpile, for example, where the pile will rearrange itself when you drop additional sand grains onto it). The theory behind these systems is related to chaos theory, but the systems are said to be “on the edge of chaos“, because they have the ability to adjust themselves (around the critical factors), unlike truly chaotic systems. One interesting thing with CA-systems is that they can suddenly rearrange themselves rather violently or criticality. Like in a sandpile which has a grain added to it, which topples onto other grains, which in turn topple onto other grains, etc. In physics, the Bak-Tang-Wiesenfeld sandpile model is the first discovered example of a dynamical system displaying self-organized criticality and is named after Per Bak [1] [2] [3], Chao Tang [1] [2] and Kurt Wiesenfeld [1] [2]. While running the model, you soon then have an avalanche effect and signatures produced equivalent to those found in nature. In fact, many phenomena in daily life are complex adaptive systems, like weather, traffic, earthquakes, eco-systems, or the stock market, and many of them share this precise 1/f noise pattern. As our brains.

[1] Per Bak, Chao Tang and Kurt Wiesenfeld (1987). “Self-organized criticality: an explanation of 1/f noise“. Physical Review Letters 59: pp. 381-384.
[2] Per Bak, Chao Tang and Kurt Wiesenfeld (1988). “Self-organized criticality“. Physical Review A 38: pp. 364-374.
[3] Per Bak (1996). How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus. ISBN 0-387-94791-4.

[...] People should learn how to play Lego with their minds. Concepts are building bricks [...] V. Ramos, 2002.

@ViRAms on Twitter

Archives

Blog Stats

  • 245,958 hits