DIMACS
DIMACS REU 2014

General Information

me
Student: Eric Hans Lee
Office: 434 CoRE
School: UC Berkeley
E-mail: ericlee0803@yahoo.com
Project: Solving Systems of Polynomials and Polynomiography in Multiple Dimensions

Project Description

This summer, I am working with Dr. Kalantari on Solving Systems of (complex valued) Polynomials as well as visualization of these processes via Polynomiography. Solving systems of polynomials is a very general but difficult problem.


Weekly Log

Week 1:
Read some material, attended orientation and other first-week events, and got situated in my new office. Met with my mentor and discussed out a variation of the Generalized Newton's Method that doesn't require invertibility of the Jacobian. Built a working version with visualization from the ground up. We also discussed transforming single complex polynomials into systems of polynomials: Transforming the Roots of Unity
Week 2:
Cyclic Newton's Method is the variation of the Generalized Newton's Method that Dr. Kalantari and I are working on. It essentially takes a one-dimensional newton step in the direction of each variable (i.e. a newton step in the direction x, then a newton step in the direction y, and so on and so forth). However, I discovered that the dynamics of the iterative method have, for the most part, cyclic orbits around roots, therefore preventing convergence. I implemented a heuristic that perturbs the orbits in an attempt to induce convergence. I also visualized this method as well as Generalized Newton's Method, adding color and shading, by taking the polynomiograph of monovariate "slices" of a multivariate polynomial system.
The polynomiograph for the square polynomial system { x^3-3xy^2-1, 3x^2y-y^3 } (this is the system equivalent to z^3-1), taking the vertical slice y=1.

The polynomiograph for the square polynomial system { x^3-3xy^2-2x+2, 3x^2y-y^3-y } (this is the system equivalent to Smale's Polynomial, z^3-2z+2), taking the vertical slice y=1.
Week 3:
Bounds for the modulus of the roots of a polynomial system are unknown. The most basic bounds stem from systematic elimination of variables in a multivariate system, leading to a monovariate system whose roots contain the roots of the original polynomial system. Since bounds for the modulus of the roots of a single polynomial are well-known (Dr. Kalantari has some of the best ones), we simply apply them to obtain a rough estimate. The problem with this method is simply that elimination is too computationally difficult, and if we were to do all the computation to find the bounds, we might as well find all the roots. It is therefore not very useful to consider these very basic bounds. I also coded up some more variations of Cyclic Iteration, including one that uses the basic family (a family of higher order iteration functions) instead of Newton's Method. I then tested various polynomial systems on the methods created so far. Interestingly, these methods solved linear systems incredibly fast (linear systems too are polynomial systems) in MATLAB- around 10 times faster. Whether or not this extends in generality is unknown.
Week 4:
Factoring is the process of representing a monovariate polynomial as products of linear equations, the solutions of which correspond to the zeroes of the monovariate polynomial. The question is, what is factoring for polynomial systems? In Non-linear algebra, taught by Bernd Sturmfels at UC Berkeley, we learned that Primary Decomposition is the generalization of factoring. On another note, I read a paper Dr. Kalantari sent me about representing Shidoku (and Sudoku, it's 9 by 9 cousin) as systems of polynomials. Namely, that there exists a one-to-one correspondence between solutions of Shidoku/Sudoku and zeroes of specially constructed polynomial systems. The paper: Groebner Bases and Shidoku. For example, in Shidoku, the specially constructed polynomial system has 40 equations in 16 variables.
Week 5:
Solving the large polynomial system coming from Shidoku via Cyclic Newton's Method was incredibly quick. I believe this is due to fact that the system looks very similar to a linear system with extra monovariate polynomials, along with the symmetry of the system. I did polynomiography, looking at the first two variables with real initial guesses. However, the image that came out was very odd:

Dr. Kalantari suggested that instead of looking at two real variables in R2, I look at one variable in C1 instead. The image that came out looked much more like a polynomiograph (in fact, it looks very similar to the Newton Fractal of z^4-1):

I also tried something akin to 3D polynomiography, pdf here
Week 6:
Another algorithm suggested for solving polynomial systems is a variation of the Ellipsoid method in linear programming, coined "Newton Ellipsoid Method". The idea is to cutting a search space into smaller and smaller pieces in an attempt to localize the root, akin to the bisection method / binary search. Reference is here. I tried generalizing the method to higher dimensions. While the generalized method works fine in the monovariate polynomials, it fails to yield results for multivariate polynomials. Here are some polynomiographs for monovariate polynomials using the Generalized Newton Ellipsoid method:

Presentations


Some pretty pictures I've made so far: