Ryan Nikin-Beers
DIMACS Research Student
Mentor: Dr. Bahman Kalantari
Contact: rnikinbeers@gmail.com

Exploring Polynomiography and Its Applications

Introduction

As described by Dr. Kalantari in his book Polynomial Root-Finding and Polynomiography, polynomiography is the "art and science of visualization in the approximation of roots of polynomials." Some polynomiographs can be made by starting with a polynomial and an area of the complex plane that is split up into a certain number of points. For each point, an iterative method for approximation of a root is applied until the method outputs a point which is within some interval of a root of the polynomial. Different colors are assigned depending on which root the method gave from that particular starting point. Shading is determined by the number of iterations of the method it took to get to the root. White is used when the method does not approximate close enough to a root after a certain number of iterations. For some of Dr. Kalantari's polynomiographs, Newton's method has been used as the iterative method. However, due to a recent discovery by Dr. Kalantari, he wants to investigate the polynomiographs that might be created using a different iterative method. I have been asked to implement a program that will produce polynomiographs using this new method, which we will call the Ellipsoid-Newton method.

Week 1: I met with Dr. Kalantari and he explained the new iterative method that I would be using to create polynomiographs. I implemented a basic polynomiography program in Mathematica using Newton's method as the iterative method for root approximation. This was done to familiarize myself with polynomiography.

Week 2: I presented an outline of what I will be doing over the course of my time at the REU. I reviewed some properties of ellipses, and figured out the basic steps I will need to go through to implement the Ellipsoid-Newton method.

Week 3: I figured out how to make my Newton's method program run faster so that I would understand how to implement the Ellipsoid-Newton method program. I produced a visual representation of the steps that the Ellipsoid-Newton method goes through using Mathematica.

Week 4: I implemented a program that produced a polynomiograph using the Ellipsoid-Newton method. However, the image appeared to be random chaos. This may have happened because there was something wrong with my program or because that is just what this method produces. Dr. Kalantari suggested I use a combination of Newton's method and the Ellipsoid-Newton method so that an image with a pattern can be produced.

Week 5: I was able to produce some images that did not appear to be random chaos, but Dr. Kalantari was reluctant to accept them as what the Ellipsoid-Newton method produced because there was not symmetry where there should have been. I had to go back and rethink the way I was coloring the pixels to produce an image that appeared to be correct.

Week 6: I found some issues with my program that involved the Newton's direction and the proper way of cutting an ellipse in the Ellipsoid method. There was also an issue with the original matrix B that I was using to create the initial ellipse in the method. After fixing these issues, I was able to produce images that were absolutely correct, although they had to use a combination of the Ellipsoid method and Newton's method, whereas we want to produce images using solely the Ellipsoid method. I also did some side work on a project involving polynomiography and cryptography. It involved computing Hausdorff distances between sets of roots of polynomials.

Week 7: I made my final presentation describing what I accomplished over the summer and showing the polynomiographs I produced. I also worked on implementing the original Ellipsoid-Newton method, rather than a combination with Newton's method.

Week 8: I summarized my work over the summer in a paper written for DIMACS. I was able to implement the original Ellipsoid-Newton method as we Dr. Kalantari first described it.