a thoughtful web.
comment by wasoxygen
wasoxygen  ·  1053 days ago  ·  link  ·    ·  parent  ·  post: Roots, Roots!

I cannot do degree 25 or more, as I'm running out of memory

The image appears to have horizontal and vertical symmetry, but I haven't been able to have a good look at it without my browser overheating.

If it is symmetric, could you calculate one quadrant and then reflect it to build the whole image?

tvirlip  ·  1053 days ago  ·  link  ·

Well, the picture is symmetric. Vertical symmetry comes from the fact that if z is a root of a polynomial with real coefficients then the complex conjugate z' is also a root of the same polynomial (if z = a + bi then the complex conjugate z' is defined as z = a - bi). The horizontal symmetry comes from the fact that if z is a root of a polynomial, then -z is a root of polynomial which can be constructed by negating the sign of each coefficient next to each odd degree. As I'm looking at all polynomials with coefficients +1 or -1, for every root z of some polynomial I have a root -z for some other polynomial.

This indeed gives some possibilities:

- I can draw only 1/4 of the picture, and construct the result out of it

- I can store only 1/4 of all the roots (only top right quadrant, for example)

- I can do calculations for only 1/2 of all the polynomials (but I need some logic to keep track if I need to find the roots of the polynomial or not -- would be simple, though)

- I cannot calculate only half of the roots, because, as I've mentioned above, vertically symmetric roots are coming in pairs in the same polynomial, and the method used by GSL library for finding the roots does not produce roots one by one, instead calculating the whole set of roots at the same time.

All in all, these optimizations would save about 50% of the calculation time and about 75% of memory, also I'd be able to double the resolution. I should be able to do the power 25, and, maybe 26. But not 27. And I dream about doing 32, and increasing the resolution of the picture ten-fold. So I'll rather at first focus on doing the whole thing in more parallel manner, with results not being stored in memory -- but yes, symmetry-based optimization is definitely one of the things to do after that. Thanks for suggestion!