fractalforums.com - The Mandelbrot Polynomial Roots Challenge

bugman

Iterator

Posts: 122

The Mandelbrot Polynomial Roots Challenge

« 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! cool

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 503 times.)
« Last Edit: January 02, 2010, 10:48:46 PM by bugman »	Logged

bugman

Iterator

Posts: 122

Re: The Mandelbrot Polynomial Roots Challenge

« 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

Iterator

Posts: 122

Re: The Mandelbrot Polynomial Roots Challenge

« 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

BradC

Conqueror

Posts: 85

Re: The Mandelbrot Polynomial Roots Challenge

« 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 446 times.)
	Logged

kram1032

Fractal Schemer

Posts: 1017

Re: The Mandelbrot Polynomial Roots Challenge

« 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

Iterator

Posts: 122

Re: The Mandelbrot Polynomial Roots Challenge

« 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

BradC

Conqueror

Posts: 85

Re: The Mandelbrot Polynomial Roots Challenge

« 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

Iterator

Posts: 122

Re: The Mandelbrot Polynomial Roots Challenge

« 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 Schemer

Posts: 1017

Re: The Mandelbrot Polynomial Roots Challenge

« 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

Pages: [1] Go Down

« previous next »

	Author	Topic: The Mandelbrot Polynomial Roots Challenge (Read 1651 times)
		Description:
0 Members and 1 Guest are viewing this topic.

Related Topics
	Subject	Started by	Replies	Views	Last post
	Roots of real polynomial x²+x Mandelbrot & Julia Set	stigomaster	13	1192	February 09, 2010, 12:43:58 AM by Timeroot
	Polynomial Roots, degree 7, coeff {-10, -9, ..., 10} \ {0}, centered at 1i Images Showcase (Rate My Fractal)	johandebock	3	316	June 23, 2010, 09:01:17 PM by kram1032
	Tombraider - The Ultimate Challenge Mandelbulb3D Gallery	Madman	0	182	February 21, 2011, 09:17:50 PM by Madman
	Mandelbrot Challenge General Discussion	decayer	2	1332	August 17, 2011, 01:54:49 PM by decayer
	Challenge Of The Yin Yang Knot Mandelbulb3D Gallery	Sockratease	2	92	April 01, 2012, 12:50:44 AM by Sockratease

	Welcome, Guest. Please login or register., Guest. Please login or register.	May 24, 2012, 06:39:36 AM
		Login with username, password and session length