Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
research_report_pix [2008-03-09 13:44] – 88.6.21.0research_report_pix [2013-08-22 10:28] (current) – [References] nik
Line 1: Line 1:
- 
  
 ==== An Aesthetic Exploration of Multivariate Polynomial Maps ==== ==== An Aesthetic Exploration of Multivariate Polynomial Maps ====
Line 15: 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 119: 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 145: 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 182: 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 196: 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 218: 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. 
Line 234: Line 258:
 pixel in the image represents a unique starting value which is fed into an pixel in the image represents a unique starting value which is fed into an
 iterative equation. The black region in the centre of the image are those iterative equation. The black region in the centre of the image are those
-starting conditions for which the succesive values produced by the iteration+starting conditions for which the successive values produced by the iteration
 stay close to their initial value, and define the Mandelbrot set proper. The stay close to their initial value, and define the Mandelbrot set proper. The
 coloured bands surrounding this region represent starting values for which coloured bands surrounding this region represent starting values for which
-sucessive iteration causes the values to spin off towards infinity. The+successive iteration causes the values to spin off towards infinity. The
 different colours represent the number of iterations required for the values to different colours represent the number of iterations required for the values to
 cross some arbitrary threshold. cross some arbitrary threshold.
Line 253: Line 277:
 number space. The two-dimensional nature of Computer screens lend themselves number space. The two-dimensional nature of Computer screens lend themselves
 predictably to the direct represention of two-dimensional data. It is possible predictably to the direct represention of two-dimensional data. It is possible
-to stretch this situation to accomodate one more dimension by making+to stretch this situation to accommodate one more dimension by making
 animations, essentially mapping a new dimension (and hence a parameter) to animations, essentially mapping a new dimension (and hence a parameter) to
 time. The resulting animations are made with a sequences of parallel slices time. The resulting animations are made with a sequences of parallel slices
Line 264: Line 288:
  
 The first optimisation was to make use of The first optimisation was to make use of
-[[http://psyco.sourceforge.net|Psyco]], a specializing compiler for Python.+[[http://psyco.sourceforge.net|Psyco]], a specialising compiler for Python.
 This required some changes in my code to avoid particular This required some changes in my code to avoid particular
 [[http://psyco.sourceforge.net/psycoguide/unsupported.html|structures that [[http://psyco.sourceforge.net/psycoguide/unsupported.html|structures that
Line 274: Line 298:
 being used resulted in a further 25% speed increase. being used resulted in a further 25% speed increase.
  
-[ # should this data heavy optimisation stuff appear in results? ] 
  
 Performance gains from each progressive optimisation were decreasing, and I was Performance gains from each progressive optimisation were decreasing, and I was
 considering some other avenues for increasing performance. Initially I had considering some other avenues for increasing performance. Initially I had
 chosen to use Python as the language of implementation as it has many language 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 intial +features that make it comfortable to use when sketching out the initial 
-implemenation of an algorithm.  Now that the algorithm was becoming quite +implementation of an algorithm.  Now that the algorithm was becoming quite 
-settled, I decided to reimplement it in C, to get an idea of the differences in+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 efficiency between the two languages. I was assuming that the matrix functions
 provided by SciPy were reasonably efficient, and that the performance increases provided by SciPy were reasonably efficient, and that the performance increases
Line 288: Line 311:
  
 Creating a C implementation was also an excuse for me to try using a library I 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+had discovered called [[http://liboil.freedesktop.org|liboil]]. LibOIL is a
 library of optimised functions for performing simple instructions across large library of optimised functions for performing simple instructions across large
 sets of data. Most modern processor designs are able to efficiently perform sets of data. Most modern processor designs are able to efficiently perform
Line 307: Line 330:
 discovered [[http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/|Pyrex]]. 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 Pyrex is a meta-language for writing Python modules. It is very similar to
-Python, with the exception that it can use and access functions and data from C+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 libraries. With Pyrex I was able to integrate my C evaluation code into my
 existing Python code. Following this integration, the result was slightly existing Python code. Following this integration, the result was slightly
Line 318: Line 341:
 compiler. compiler.
  
-[ dotplot renderer, interface ]+[ 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 ]
  
  
Line 324: Line 381:
 [ 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 338: 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 349: Line 408:
  
 [ render errors? ] [ render errors? ]
 +
 +[ code ]
  
 ==== Discussion ==== ==== Discussion ====
Line 358: 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 374: 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