Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
research_report_pix [2008-03-02 11:52] – created 83.60.175.159research_report_pix [2013-08-22 10:28] (current) – [References] nik
Line 14: Line 14:
 maps. An iterated map is an equation, or often a system of equations, which are maps. An iterated map is an equation, or often a system of equations, which are
 evaluated iteratively. Iteration in this case means that we take the result of evaluated iteratively. Iteration in this case means that we take the result of
-evaulating the equations with, and feed this back into the same equations as+evaluating the equations with, and feed this back into the same equations as
 inputs for the next evaluation.  With most randomly chosen equations, the set inputs for the next evaluation.  With most randomly chosen equations, the set
-of results produced by succesive iterations is not particularly interesting,+of results produced by successive iterations is not particularly interesting,
 perhaps rapidly climbing to infinity, collapsing to 0 or some other fixed perhaps rapidly climbing to infinity, collapsing to 0 or some other fixed
 value. For a small number of equations however, the set of results carves out a value. For a small number of equations however, the set of results carves out a
 region of number space which exhibits interesting fractal properties. This region of number space which exhibits interesting fractal properties. This
 region of number space is called an attractor. The complete term "strange region of number space is called an attractor. The complete term "strange
-attractor" refers also to the chaotic propeties of these attractors (CPiC p10,+attractor" refers also to the chaotic properties of these attractors (CPiC p10,
 CaTSA p127). CaTSA p127).
  
Line 118: Line 118:
  
 The terms a<sub>1</sub> though to a<sub>30</sub> are the parameters which The terms a<sub>1</sub> though to a<sub>30</sub> are the parameters which
-define a particular attractor. When I refer to "parameter space", I am refering+define a particular attractor. When I refer to "parameter space", I am referring
 collectively to these values. In the same way that you could take two numbers collectively to these values. In the same way that you could take two numbers
 to be coordinates on a two-dimensional map, it can be useful to imagine a long to be coordinates on a two-dimensional map, it can be useful to imagine a long
Line 129: Line 129:
 Perhaps the most important aspect to comprehend is that sets of parameters Perhaps the most important aspect to comprehend is that sets of parameters
 where the corresponding values in each set differ only slightly from each other where the corresponding values in each set differ only slightly from each other
-(eg, a<sub>7</sub> in each set) are in some sense adjacent.+are in some sense adjacent.
  
 The right hand side of equation is simply a polynomial of degree 2 in The right hand side of equation is simply a polynomial of degree 2 in
Line 144: Line 144:
 problems of how to sensibly navigate or visualise such high dimensional spaces. problems of how to sensibly navigate or visualise such high dimensional spaces.
  
 +As an aside, many of the plots in this report are of my first automatically
 +discovered attractor which uses degree 5 polynomials. This means that all terms
 +are represented in which the exponents of the X, Y and Z variables sum to 5 or
 +less. This results in 3 equations of 56 terms, making for 168 parameters (or
 +170 if you count the 3 starting values of X, Y and Z).
  
 +Normally, attractors are found within this vast numerical space with a
 +combination of brute force (trying many different random sets of parameters)
 +and automated analysis to determine when an interesting attractor has been
 +found. The two analysis methods employed in the program presented in CPiC are
 +measurements of the correlation dimension and the Lyapunov exponent.
 +
 +The correlation dimension is a particular was of measuring fractal dimension,
 +which is a method of measuring the way in which fractal objects fill space. In
 +the case of the dot plots of strange attractors, the correlation dimension can
 +indicate if the attractor is a collection of disconnected points (dimsions
 +close to 0), if the points are arranged in the form of a line (dimension close
 +to 1), if the points are spread out into a flat plane (dimension close to 2) or
 +if the points form a voluminous cloud (dimension close to 3). Interesting
 +attractors tend to have a dimension greater than 1. Correctly measuring the
 +correlation dimension requires too many calculations to be feasible. As an
 +alternative, the correlation dimension is normally measured approximately using
 +a random sample of points. The accuracy of the measurement increases with the
 +number of points being tested. Additionally the dimension of a fractal is often
 +not consistent across the whole of the fractal, and the resulting value is only
 +an average of the dimension across the tested points.
 +
 +The Lyapunov exponent is a measure of the chaotic behaviour of the fractal.
 +Chaos is concerned with sensitivity of a complex system to small changes in
 +initial conditions. The Lyapunov measures the speed at which slightly different
 +starting conditions diverge.
  
-[ automated help looking at the space, fractal dimension, lyapunov ] 
  
 It is hoped that the ability to explore and derive a structural understanding It is hoped that the ability to explore and derive a structural understanding
Line 181: Line 210:
 face was the construction of a suitable interface for conveniently navigating face was the construction of a suitable interface for conveniently navigating
 the high dimensional number spaces.  the high dimensional number spaces. 
- 
-[ display issues ... when did i switch to soya? .. not documented, just before 
-getting the dotplot working i guess ] 
  
 My early plans were to make a neat, self contained application, displaying the My early plans were to make a neat, self contained application, displaying the
Line 195: Line 221:
 I was to discover that relegating that 3D window to a region within another I was to discover that relegating that 3D window to a region within another
 application window is not always a simple task. The problem was further application window is not always a simple task. The problem was further
-complicated the particular 3D library I had hoped to use (OGRE) and the +complicated the particular 3D library I had hoped to use 
-language in which I had hoped to do the interface programming (Python).+([[http://ogre3d.org/|OGRE]]) and the language in which I had hoped to do the 
 +interface programming ([[http://www.python.org/|Python]]).
  
-[ summary of the problem? ] 
  
 After a number of different trial and error approaches to the problem, I gave After a number of different trial and error approaches to the problem, I gave
Line 217: Line 243:
  
 Soon after completing an initial implementation of the evaluation code, I was Soon after completing an initial implementation of the evaluation code, I was
-somewhat suprised to discover that using functions provided by SciPy,+somewhat surprised to discover that using functions provided by SciPy,
 generating maps of the parameter space would be much easier than I had generating maps of the parameter space would be much easier than I had
 imagined. In fact, I was able to render my first parameter maps long before I imagined. In fact, I was able to render my first parameter maps long before I
-had a working renderer for the 3D dot plots of the attractors themselves.+had a working renderer for the 3D dot plots of the attractors themselves.  
  
-[ randomly chosen attractor 168coeffs.. is that degree 3? ]  
  
 The first plots were quite time consuming. For each point on the map I was The first plots were quite time consuming. For each point on the map I was
 calculating many iterations of the equations, only stopping if the values calculating many iterations of the equations, only stopping if the values
-became incalculably large (infinte). During the ample opportunity for+became incalculably large (infinite). During the ample opportunity for
 reflection afforded by the long rendering times, I was reminded of the way in reflection afforded by the long rendering times, I was reminded of the way in
 which the popular images of the Mandelbrot set are typically generated.  which the popular images of the Mandelbrot set are typically generated. 
  
-Most images of the Mandelbrot set are called "Escape Time" plots. Each pixel in +Most popular images of the Mandelbrot set are called "escape time" plots. Each 
-the image represents a unique starting value which is fed into an iterative +pixel in the image represents a unique starting value which is fed into an 
-equation. The black region in the centre of the image are those starting +iterative equation. The black region in the centre of the image are those 
-conditions for which the succesive values produced by the iteration stay close +starting conditions for which the successive values produced by the iteration 
-to their initial value, and define the Mandelbrot set proper. The coloured +stay close to their initial value, and define the Mandelbrot set proper. The 
-bands surrounding this region represent starting values for which sucessive +coloured bands surrounding this region represent starting values for which 
-iteration causes the values to spin off towards infinity. The different colours +successive iteration causes the values to spin off towards infinity. The 
-represent the number of iterations required for the values to cross some +different colours represent the number of iterations required for the values to 
-arbitrary threshold.+cross some arbitrary threshold.
  
 For my purposes, escape time plots had several benefits. Firstly, there is For my purposes, escape time plots had several benefits. Firstly, there is
Line 245: Line 270:
 Secondly, while not technically representing attractors themselves, the shape Secondly, while not technically representing attractors themselves, the shape
 of the colour bands tend to give clues about the presence of nearby attractors, of the colour bands tend to give clues about the presence of nearby attractors,
-acting as a kind of mathematical aura (the allusion to pseudo-science is +which are possibly not visible in the rendered region, acting as a kind of 
-particularly appropriate).+mathematical aura. The lack of any mathematical justification for this second 
 +property make the allusion to pseudo-science particularly appropriate.
  
-[ animations ]+Until this point, my plots were essentially two dimensional slices of the large 
 +number space. The two-dimensional nature of Computer screens lend themselves 
 +predictably to the direct represention of two-dimensional data. It is possible 
 +to stretch this situation to accommodate one more dimension by making 
 +animations, essentially mapping a new dimension (and hence a parameter) to 
 +time. The resulting animations are made with a sequences of parallel slices 
 +through the number space. 
 + 
 +As computations became more ambitious, optimisation of the calculations became 
 +a more pressing concern. Animations were a particularly taxing development, as 
 +each frame of the animation would require as much computation as earlier plots, 
 +causing even short animations to require 50-100 times as much rendering time. 
 + 
 +The first optimisation was to make use of 
 +[[http://psyco.sourceforge.net|Psyco]], a specialising compiler for Python. 
 +This required some changes in my code to avoid particular 
 +[[http://psyco.sourceforge.net/psycoguide/unsupported.html|structures that 
 +Psyco is unable to optimise]]. The main culprit in my code was the use of 
 +generators, as discussed in note 4 on that list. Fortunately it was reasonably 
 +simple to convert the unsupported generator into an iterator, a similar Python 
 +construct supported by Psyco. This change was rewarded with a halving of render 
 +time (a 100% speed increase).  Some further modifications to the SciPy calls 
 +being used resulted in a further 25% speed increase. 
 + 
 + 
 +Performance gains from each progressive optimisation were decreasing, and I was 
 +considering some other avenues for increasing performance. Initially I had 
 +chosen to use Python as the language of implementation as it has many language 
 +features that make it comfortable to use when sketching out the initial 
 +implementation of an algorithm.  Now that the algorithm was becoming quite 
 +settled, I decided to re-implement it in C, to get an idea of the differences in 
 +efficiency between the two languages. I was assuming that the matrix functions 
 +provided by SciPy were reasonably efficient, and that the performance increases 
 +of a C implementation would not be too dramatic, but I was curious to make the 
 +comparison. 
 + 
 +Creating a C implementation was also an excuse for me to try using a library I 
 +had discovered called [[http://liboil.freedesktop.org|liboil]]. LibOIL is a 
 +library of optimised functions for performing simple instructions across large 
 +sets of data. Most modern processor designs are able to efficiently perform 
 +these kinds of computations, but the specific approach varies 
 +widely between different processors. Liboil has several implementations of each 
 +of its functions and chooses the most efficient implementation depending on the 
 +current processor architecture.  
 + 
 +Initial performance results from the libOIL implementation were very 
 +encouraging, running what appeared to be 492 times faster than my Python 
 +implementation, although with very slight, but intriguing differences in the 
 +output [see fig XX]. Eventually it was discovered that these differences were 
 +due to a programming error. The repaired code was slower, but still 24 times 
 +faster than the Python implementation. 
 + 
 +While the efficiency of a C implementation has obvious benefits, I was 
 +reluctant to give up on the flexibility of Python. After some research I 
 +discovered [[http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/|Pyrex]]. 
 +Pyrex is a meta-language for writing Python modules. It is very similar to 
 +Python, with the exception that it can use functions and access data from C 
 +libraries. With Pyrex I was able to integrate my C evaluation code into my 
 +existing Python code. Following this integration, the result was slightly 
 +slower but still 13 times faster than the earlier pure-Python code.   
 + 
 +As an experiment, I replaced the libOIL code in my C implementation with my own 
 +implementations of the respective functions. Surprisingly, the resulting 
 +program was slightly faster than the original libOIL code. If anything, this 
 +observation is a testament to the optimisation capabilities of the GNU C 
 +compiler. 
 + 
 +[ dot-plot renderer, interface ] 
 + 
 +Much of this work was performed without and graphical representation of the 
 +strange attractors themselves, but only the maps of their parameter spaces. 
 +Development of the dot-plot render was slowed by the problems mentioned 
 +earlier. While the specific problems mentioned earlier had workarounds, some 
 +lingering problems persisted, most of them relating to the interaction between 
 +C++ libraries (such as OGRE) and Python.  I was growing impatient with this 
 +lack of progress, and eventually decided to implement the dot-plot renderer 
 +using a Python game-development library called 
 +[[http://home.gna.org/oomadness/en/soya3d/|Soya]]. I had persisted with the 
 +OGRE implementation until this time because I thought the efficiency of the 
 +graphical display would be one of the limiting factors. 
 + 
 +[ explain fractal dimension / lyapunov somewhere before this paragraph ] 
 + 
 +Implementing the Soya render was quite quick, but revealed the unfortunate 
 +observation that the strange attractor which I had been mapping until this 
 +point was not particularly interesting to look at, and was merely a wobbly 3D 
 +loop. This was possibly caused by using an automated search which only examined 
 +the fractal dimension as a selection criteria.  In my original applet (and the 
 +program developed in the CPiC) the Lyapanov exponent is also used. Rather than 
 +improve my automated searching algorithm, I decided to focus on providing an 
 +interface for manually navigating through the parameter space, relying on human 
 +aesthetic judgements and instincts over mathematical analysis. 
 + 
 +After experimenting with a number of methods for providing an interface to the 
 +potentially large number of parameters, I settled on making some small 
 +modifications to the Grid object provided by the 
 +[[http://www.wxpython.org/|wxWidgets]] library, which provides a rudimentary 
 +spread-sheet interface. I added the ability to 
 +incrementally modify the number in the current cell by scrolling with the mouse 
 +wheel. Different combinations of the Alt, Shift and Control keys change the amount by which the value is incremented. 
 + 
 +[ highf-grid.png ]
  
-[ optimisations (psyco, liboil, handcoded c) ] 
  
-[ dotplot renderer, interface ] 
  
 [ basin of attraction 0,0,0 assumption ]  [ basin of attraction 0,0,0 assumption ] 
  
-[ sprott mention of robustness ] +[ Sprott mention of robustness ] 
  
 ==== Solution/Results ==== ==== Solution/Results ====
  
-[ intial plots of basin of attraction (accidentally) .. ] +[ initial plots of basin of attraction (accidentally) .. ] 
  
 For historical value, below is the first map I rendered. Mistakenly, it was the For historical value, below is the first map I rendered. Mistakenly, it was the
Line 270: Line 395:
 became quite surprising. became quite surprising.
  
-[ desc of basin of attraction, why the factal dimension shouldn't change much ]+[ desc of basin of attraction, why the factual dimension shouldn't change much ]
  
 highf-100.png (accidental basin plot) highf-100.png (accidental basin plot)
 +
 +[ first dot plot: highf-dotplot.png ]
  
 [ low order ] [ low order ]
Line 281: Line 408:
  
 [ render errors? ] [ render errors? ]
 +
 +[ code ]
  
 ==== Discussion ==== ==== Discussion ====
Line 290: Line 419:
  
  
-i've yet to speak to anyone with a maths background to ask if this is of any relevance, or more realistically to find out that it is very boring mathematically. i can imagine that it might be considered a little boring because i am working with big complicated polynomials. most of the famous fractals are based on very simple equations.+I've yet to speak to anyone with a maths background to ask if this is of any relevance, or more realistically to find out that it is very boring mathematically. i can imagine that it might be considered a little boring because i am working with big complicated polynomials. most of the famous fractals are based on very simple equations.
  
  
Line 306: Line 435:
  
 ==== References ==== ==== References ====
- 
   * http://www.rawilson.net/chaos/lyapunov/index.html   * http://www.rawilson.net/chaos/lyapunov/index.html
- 
   * http://sprott.physics.wisc.edu/sa.htm   * http://sprott.physics.wisc.edu/sa.htm
   * http://ibiblio.org/e-notes/MSet/Logistic.htm   * http://ibiblio.org/e-notes/MSet/Logistic.htm
-  +  * images and animations at [[Pix Strange Attractor]]
-  * images and animations at  [[Pix Strange Attractor]]+
  
  
  

User Tools

Page Tools

Site Tools