News: Did you know ? you can use LaTex inside Postings on fractalforums.com!

## The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

 Pages: [1] 2 3 ... 6   Go Down
 Author Topic: The Mandelbrot Polynomial Roots Challenge  (Read 12093 times) Description: 0 Members and 1 Guest are viewing this topic.
bugman
Conqueror

Posts: 122

 « on: January 02, 2010, 06:15:03 PM »

The quadratic Mandelbrot set is defined by iterating the following function:
f(z) = z² + c

For example, the 2nd level Mandelbrot polynomial is given by:
F(z) = f(f(z)) = (z² + c)² + c

Now, suppose we arbitrarily choose a "seed" value of z = 0 and solve for the roots of c such that:
F(0) = 0

Here is a plot of the roots of the 12th level Mandelbrot polynomial. Altogether, there are 2048 roots. This may not look like much, but it was fairly difficult to calculate. I found these roots using the Durand-Kerner method. Total runtime was 4 hours, 45 minutes, although I think it could be made much faster:
http://en.wikipedia.org/wiki/Durand-Kerner_method

For those of you computer math wizards out there, I challenge you to find more roots than this. The first one to find 1 million roots wins!

Of course, this is still a far cry from the inverse Julia set pruning methods which can probe hundreds or even thousands of levels deep. Unfortunately, I don't know of any similar way to prune Mandelbrot set roots.
 Mandelbrot-inverse.jpg (15.81 KB, 280x280 - viewed 3558 times.) « Last Edit: January 02, 2010, 10:48:46 PM by bugman » Logged
bugman
Conqueror

Posts: 122

 « Reply #1 on: January 02, 2010, 06:15:36 PM »

The way I found the roots was by first solving the roots of a lower level Mandelbrot polynomial, and then making an array containing 2 duplicates of each of those roots and plugging this new array back in as my initial guess before trying to solve the higher degree polynomial (for stability, I had to slightly perturb the duplicated roots so there would be no duplicates in my intial guess). The convergence time varied depending on how much I perturbed the duplicated roots, but in the better scenarios, I found that this accelerated my overall convergence time by a factor of 40. I stopped calculating when the solution stopped changing by any more than 10^-7.

I understand Steven Fortune has a program called Eigensolve that can find the roots of high order polynomials very quickly:
http://ect.bell-labs.com/who/sjf/eigenvalueiterexamples.html

He told me his program wasn't too much faster, because convergence time increases by roughly 10x for each level. However, I still suspect that in the specific case of solving Mandelbrot polynomials, it might be 30 to 120 times faster than my program if the same approach is used.
 « Last Edit: January 02, 2010, 10:51:27 PM by bugman » Logged
bugman
Conqueror

Posts: 122

 « Reply #2 on: January 02, 2010, 06:24:32 PM »

What about the triplex roots of the Mandelbulb polynomial? Well, I tried that but convergence was way too slow. I couldn't even solve the roots of the 2nd level Mandelbulb polynomial.
 « Last Edit: January 02, 2010, 06:32:54 PM by bugman » Logged
Safarist

Posts: 85

 « Reply #3 on: January 06, 2010, 04:16:59 PM »

I tried to find the roots of the 2nd level Mandelbulb (degree 8) function by numerically finding roots starting from a whole mess of random seed points and then removing duplicate results. I got 64 unique answers, and they appear to be situated in a configuration that looks kinda like the Mandelbulb (see attached image below).

The coordinates of these 64 roots to double precision (rounded from higher precision) are:
Code:
{{-1., 0., 0.},
{-0.8117449009293668, -0.3909157412340149, -0.4338837391175581},
{-0.8117449009293668, -0.3909157412340149, 0.4338837391175581},
{-0.8117449009293668, 0.3909157412340149, -0.4338837391175581},
{-0.8117449009293668, 0.3909157412340149, 0.4338837391175581},
{-0.766044443118978, 0., -0.6427876096865394},
{-0.766044443118978, 0., 0.6427876096865394},
{-0.6234898018587335, -0.7818314824680298, 0.},
{-0.6234898018587335, 0.7818314824680298, 0.},
{-0.4776208980552355, -0.5989176626001069, -0.6427876096865394},
{-0.4776208980552355, -0.5989176626001069, 0.6427876096865394},
{-0.4776208980552355, 0.5989176626001069, -0.6427876096865394},
{-0.4776208980552355, 0.5989176626001069, 0.6427876096865394},
{-0.20048443395120957, -0.8783796973249267, -0.4338837391175581},
{-0.20048443395120957, -0.8783796973249267, 0.4338837391175581},
{-0.20048443395120957, -0.0965482148568969, -0.9749279121818236},
{-0.20048443395120957, -0.0965482148568969, 0.9749279121818236},
{-0.20048443395120957, 0.0965482148568969, -0.9749279121818236},
{-0.20048443395120957, 0.0965482148568969, 0.9749279121818236},
{-0.20048443395120957, 0.8783796973249267, -0.4338837391175581},
{-0.20048443395120957, 0.8783796973249267, 0.4338837391175581},
{-0.17364817766693036, 0., -0.984807753012208},
{-0.17364817766693036, 0., 0.984807753012208},
{-0.10826786788668456, -0.13576361217320798, -0.984807753012208},
{-0.10826786788668456, -0.13576361217320798, 0.984807753012208},
{-0.10826786788668456, 0.13576361217320798, -0.984807753012208},
{-0.10826786788668456, 0.13576361217320798, 0.984807753012208},
{-0.049515566048790434, -0.21694186955877906, -0.9749279121818236},
{-0.049515566048790434, -0.21694186955877906, 0.9749279121818236},
{-0.049515566048790434, 0.21694186955877906, -0.9749279121818236},
{-0.049515566048790434, 0.21694186955877906, 0.9749279121818236},
{0., 0., 0.},
{0.03864035467425736, -0.16929445530699877, -0.984807753012208},
{0.03864035467425736, -0.16929445530699877, 0.984807753012208},
{0.03864035467425736, 0.16929445530699877, -0.984807753012208},
{0.03864035467425736, 0.16929445530699877, 0.984807753012208},
{0.1387395330218428, -0.17397387167523584, -0.9749279121818236},
{0.1387395330218428, -0.17397387167523584, 0.9749279121818236},
{0.1387395330218428, 0.17397387167523584, -0.9749279121818236},
{0.1387395330218428, 0.17397387167523584, 0.9749279121818236},
{0.15645160204589237, -0.07534312061707779, -0.984807753012208},
{0.15645160204589237, -0.07534312061707779, 0.984807753012208},
{0.15645160204589237, 0.07534312061707779, -0.984807753012208},
{0.15645160204589237, 0.07534312061707779, 0.984807753012208},
{0.17046092493487977, -0.746838109568473, -0.6427876096865394},
{0.17046092493487977, -0.746838109568473, 0.6427876096865394},
{0.17046092493487977, 0.746838109568473, -0.6427876096865394},
{0.17046092493487977, 0.746838109568473, 0.6427876096865394},
{0.2225209339563144, -0.9749279121818236, 0.},
{0.2225209339563144, 0., -0.9749279121818236},
{0.2225209339563144, 0., 0.9749279121818236},
{0.2225209339563144, 0.9749279121818236, 0.},
{0.5617449009293668, -0.7044058256496909, -0.4338837391175581},
{0.5617449009293668, -0.7044058256496909, 0.4338837391175581},
{0.5617449009293668, 0.7044058256496909, -0.4338837391175581},
{0.5617449009293668, 0.7044058256496909, 0.4338837391175581},
{0.6901821946798448, -0.3323742273106898, -0.6427876096865394},
{0.6901821946798448, -0.3323742273106898, 0.6427876096865394},
{0.6901821946798448, 0.3323742273106898, -0.6427876096865394},
{0.6901821946798448, 0.3323742273106898, 0.6427876096865394},
{0.9009688679024191, -0.4338837391175581, 0.},
{0.9009688679024191, 0., -0.4338837391175581},
{0.9009688679024191, 0., 0.4338837391175581},
{0.9009688679024191, 0.4338837391175581, 0.}}
 lvl2deg8roots.gif (335.98 KB, 360x360 - viewed 3270 times.) Logged
kram1032
Fractal Senior

Posts: 1863

 « Reply #4 on: January 06, 2010, 06:22:21 PM »

could you look at those positions? Just thinking about the Mandelbrot set and looking at the two points in the center of the set lets me guess that those are exactly positions of minibulbs.
 Logged
bugman
Conqueror

Posts: 122

 « Reply #5 on: January 06, 2010, 07:10:51 PM »

Hey, that is really interesting BradC! This might prove useful for finding more Mandelbulb 3D orbits (so far I have only been able to find the main 3D cardioid):
http://www.fractalforums.com/theory/mandelbrot-pearls/msg11043/#msg11043

I am curious what method did you use to converge the random points and how long did it take to solve?
 « Last Edit: January 06, 2010, 09:46:55 PM by bugman » Logged
Safarist

Posts: 85

 « Reply #6 on: January 06, 2010, 09:22:49 PM »

I used FindRoot with two starting values for each variable, so Mathematica wouldn't try to take derivatives. It took about 10 minutes on my old P4. Two starting values for each of the three variables = 6 values total, I chose them all independently, uniformly distributed in (-1.5, 1.5). This strategy could probably be improved. It found most of the points fairly quickly, but then took a long time to find the last few values near the poles. Better starting values would probably help that.

Some other implementation details:
• WorkingPrecision everywhere is 4 \$MachinePrecision; then I used N[] at the very end to get doubles.
• I mapped all failed convergences to a special value so I could recognize and remove them at the end.
• I removed duplicates using Gather, considering two points to be equal if they were less than 10^-8 apart. This was smaller than necessary.
• FindRoot was sometimes calling my function with x=y=0, so I had to handle that case specially to avoid messages and Indeterminate values.
• I ran this procedure 1000 points at a time until the resulting solution set looked symmetrical and seemed to stop growing. It took 5 runs (5000 FindRoot calls).

With a real or complex polynomial of one variable, I think you can divide out zeros as you find them to avoid finding the same zero twice. I'm not sure how to do this with a function of more than one variable.

This approach probably wouldn't be able to realistically find all solutions for the 3rd level Mandelbulb or higher, but it should be able to find lots of solutions farily easily.
 « Last Edit: January 06, 2010, 09:25:55 PM by BradC » Logged
bugman
Conqueror

Posts: 122

 « Reply #7 on: January 07, 2010, 03:58:43 AM »

Triplex roots can also be found analytically:
http://www.fractalforums.com/theory/triplex-algebra/msg9477/#msg9477

There are 64 roots for the 8th order power formula. I wonder if this can be applied to exactly solve for the 64 points that you found.
 « Last Edit: January 07, 2010, 07:53:32 AM by bugman » Logged
kram1032
Fractal Senior

Posts: 1863

 « Reply #8 on: January 07, 2010, 09:50:47 PM »

only 64 roots?

I'd expect a triplex to have power³ roots which would be 512 for 8...
The number of roots would also increase per iterations, I guess?

And as the set fully includes the Mset of power, it should be fully including all the roots for power 8 too...

Or how's that 64 meant?
 Logged
knighty
Fractal Iambus

Posts: 819

 « Reply #9 on: May 26, 2013, 10:09:36 PM »

Sorry for bumping this old thread but:
For those of you computer math wizards out there, I challenge you to find more roots than this. The first one to find 1 million roots wins!
Ok! here is attached an evaldraw script that can compute 1 million roots (and maybe 2).
It uses some kind of interval arithmetics and a divide and conquere strategy.

BTW! The bottleneck with Durand-Kerner method comes the product in the denominators which makes it O(N²), the evaluation of the Mandelbrot polynomial itself is O(log(N)). It should be possible to transform the Durand-Kerner method to make it O(N E(N)) (where E(N) is the complexity of the polynomial evaluation) by using a Fast multipole method to compute the denominators. This is because the "potential" from a cluster of approximated roots that are far from the curent approximation root have a small magnitude and doesn't change too much in the vicinity of the current apprximation.

Because I'm not a math wizard, I challenge those of you computer math wizards to write such algorithm or prove me wrong (which is equally probable).
M Benesi
Fractal Schemer

Posts: 1075

 « Reply #10 on: May 27, 2013, 01:34:44 AM »

Are there roots at the center of each p/q bulb?  Then you could generate roots with (p/q is rational) -

$\Large {c_{\frac{p}{q}} = \frac{e^{2\pi i\frac pq}}2\left(1-\frac{e^{2\pi i\frac pq}}2\right)}$

From the wiki.
 Logged

knighty
Fractal Iambus

Posts: 819

 « Reply #11 on: May 27, 2013, 01:57:04 PM »

AFAIU, that formula gives the points of tangency of the disks with the main cardioid not roots.

Of course, each root of the N-th Mandelbrot polynomial is the center of an hyperbolic componenent. Because N is finite, There is a finite number of roots (2^(N-1) roots) so it's impossible to have the roots for all p/q which is infinite.

 Logged
M Benesi
Fractal Schemer

Posts: 1075

 « Reply #12 on: May 27, 2013, 07:45:02 PM »

</snip>

We could have $N\to\infty$.  Seems like the roots would tend to $\infty$ as well. </snip>

Could we follow the tangent out from the main Cardioid, determining the size of the bulb by the p/q ratio to find the approximate center....  and then do Newton's approx (or some other approximation function).

</snip>

This is sortof neat:
http://en.wikibooks.org/wiki/Fractals/Iterations_in_the_complex_plane/Mandelbrot_set#color_is_proportional_to_magnitude_of_zn

Above it is other info about the roots.
 « Last Edit: May 28, 2013, 06:29:25 AM by M Benesi » Logged

knighty
Fractal Iambus

Posts: 819

 « Reply #13 on: May 29, 2013, 05:13:56 PM »

Could we follow the tangent out from the main Cardioid, determining the size of the bulb by the p/q ratio to find the approximate center....  and then do Newton's approx (or some other approximation function).
Very nice idea and I think it's possible: There is a formula giving an estimation of the size of a mu-atom attached to a cardioid.
One have to be carful about the accuracy of floating number format used when solving for very small mu-atoms.

In the script I posted above, using double floats will probably miss some roots when the order of Mandelbrot polynomial is above 24 or so. Anyway, the script is limited to the 22th order because of the limitations to the size of the array storing the roots. Notice that the algorithm I used is naturally parallelizable so one can write a multithreaded application to speed up things. I'm wondering if it's possible to use cuda or opencl (with say, an implementation of double-double or quad-floats) in order to compute even more roots (maybe on billion  ).

It looks like Piers Lawrence have already computed more than 1 million roots. There is in particular, a nice animation of a kind of buddhabrot obtained from them.
M Benesi
Fractal Schemer

Posts: 1075

 « Reply #14 on: May 30, 2013, 07:30:02 AM »

At least it looks like he's trying for it:

Quote from: PiersLawrence

You know, that root animation on his main page begins to look like a 2d Mandelbulb towards the end.

And here is a bit of planetary buddhabrot nebulousness for you.
 « Last Edit: May 30, 2013, 07:34:18 AM by M Benesi » Logged

 Pages: [1] 2 3 ... 6   Go Down