Differences

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

--- research_report_pix [2008-03-02 11:52] – created 83.60.175.159
+++ research_report_pix [2008-03-09 13:44] – 88.6.21.0
@@ Line 1: / Line 1: @@
 ==== An Aesthetic Exploration of Multivariate Polynomial Maps ====
@@ Line 129: / Line 130: @@
 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
-(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
@@ Line 230: / Line 231: @@
 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 succesive 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
+sucessive 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
@@ Line 245: / Line 246: @@
 Secondly, while not technically representing attractors themselves, the shape
 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 accomodate 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.
+The first optimisation was to make use of
+[[http://psyco.sourceforge.net|Psyco]], a specializing 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.
+[ # 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 intial
+implemenation 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
+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 and access functions and 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.
 [ dotplot renderer, interface ]
 [ basin of attraction 0,0,0 assumption ]