Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision Next revisionBoth sides next revision | ||
research_report_pix [2008-03-02 11:52] – created 83.60.175.159 | research_report_pix [2008-03-11 10:14] – 195.53.62.237 | ||
---|---|---|---|
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 | + | evaluating |
inputs for the next evaluation. | inputs for the next evaluation. | ||
- | of results produced by succesive | + | of results produced by successive |
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 " | region of number space is called an attractor. The complete term " | ||
- | attractor" | + | attractor" |
CaTSA p127). | CaTSA p127). | ||
Line 118: | Line 118: | ||
The terms a< | The terms a< | ||
- | define a particular attractor. When I refer to " | + | define a particular attractor. When I refer to " |
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< | + | 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 183: | Line 183: | ||
[ display issues ... when did i switch to soya? .. not documented, just before | [ display issues ... when did i switch to soya? .. not documented, just before | ||
- | getting the dotplot | + | getting the dot-plot |
My early plans were to make a neat, self contained application, | My early plans were to make a neat, self contained application, | ||
Line 195: | Line 195: | ||
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:// |
+ | interface programming ([[http:// | ||
[ summary of the problem? ] | [ summary of the problem? ] | ||
Line 217: | Line 218: | ||
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 | + | somewhat |
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 | ||
Line 226: | Line 227: | ||
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 |
- | 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 |
- | conditions for which the succesive | + | starting |
- | 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 |
- | iteration causes the values to spin off towards infinity. The different colours | + | successive |
- | 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 246: | ||
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 | + | which are possibly not visible in the rendered region, |
- | 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. | ||
- | [ optimisations (psyco, liboil, handcoded c) ] | + | 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. | ||
- | [ dotplot | + | The first optimisation was to make use of |
+ | [[http:// | ||
+ | This required some changes in my code to avoid particular | ||
+ | [[http:// | ||
+ | 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). | ||
+ | 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 | ||
+ | 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. | ||
+ | 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:// | ||
+ | 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, | ||
+ | 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, | ||
+ | implementation, | ||
+ | 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:// | ||
+ | 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, | ||
+ | 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, | ||
+ | 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 | ||
+ | |||
+ | 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, | ||
+ | lingering problems persisted, most of them relating to the interaction between | ||
+ | C++ libraries (such as OGRE) and Python. | ||
+ | lack of progress, and eventually decided to implement the dot-plot renderer | ||
+ | using a Python game-development library called | ||
+ | [[http:// | ||
+ | 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. | ||
+ | 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:// | ||
+ | spread-sheet display of a grid of numbers. I added the ability to easily | ||
+ | incrementally modify the number in the current cell by scrolling with the mouse | ||
+ | wheel. | ||
[ basin of attraction 0,0,0 assumption ] | [ basin of attraction 0,0,0 assumption ] | ||
- | [ sprott | + | [ Sprott |
==== Solution/ | ==== Solution/ | ||
- | [ intial | + | [ initial |
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 368: | ||
became quite surprising. | became quite surprising. | ||
- | [ desc of basin of attraction, why the factal | + | [ desc of basin of attraction, why the factual |
highf-100.png (accidental basin plot) | highf-100.png (accidental basin plot) | ||
+ | |||
+ | [ first dot plot ] | ||
[ low order ] | [ low order ] | ||
Line 281: | Line 381: | ||
[ render errors? ] | [ render errors? ] | ||
+ | |||
+ | [ code ] | ||
==== Discussion ==== | ==== Discussion ==== | ||
Line 290: | Line 392: | ||
- | 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. |