Newton’s Method

The Newton’s Method is the useful way to approximate the value of root of function. Even though it contains the calculation of the derivative of the function, the speed of the calculation is faster than the other methods, for instance, Bisection Method. Before we describe the Newton’s Method, first let us know about the Newton’s operator.

Suppose that we have a polynomial f\in \mathbf{k}[x] where \mathbf{k} is a field. Then, we can define Newton’s operator like the following:

N_f:\mathbf{k}[x]\rightarrow \mathbf{k},~~ N_f(x)=x-\frac{f(x)}{f'(x)}.

Now, we need to decide an initial approximation x_0. Then, by this x_0, we have the next approximation x_1 where x_1=N_f(x_0). Repeatedly, we can get the approximation \{x_n\} which, hopefully, converges to the root of f.

Newton'sMethodProof_gr_17.gif

We can extend Newton’s method to the multivariate case. That is, if we have \mathbf{f} is a polynomial system (i.e. \mathbf{f}\in \mathbf{k}[x]^n), then we can define the Newton’s operator of \mathbf{f} like the following:

N_{\mathbf{f}}(x)=x-\left(\frac{\partial \mathbf{f}}{\partial x}(x)\right)^{-1}\mathbf{f}(x).

We can use the Newton’s Method if each approximation x_n satisfies \det\left(\frac{\partial \mathbf{f}}{\partial x}(x_n)\right)\ne0. In other words, if the solution is regular, then we can use the Newton’s Method.

However, we have a problem when the Jacobian matrix \frac{\partial \mathbf{f}}{\partial x} is not square, especially, when we have fewer variables than polynomials. Now, we will consider the way to “squaring up” the Jacobian matrix \frac{\partial \mathbf{f}}{\partial x}.

Suppose that we have n variables and m polynomials with m>n. First, in order to square up the matrix, we may “add” m-n more variables. However, then the determinant of the new matrix is clearly zero. Thus, it does not satisfy the regularity condition.

Secondly, we may think about the random linear combinations of the polynomials. In other words, consider the matrix A\in \mathbf{k}^{n\times m} and calculate A\mathbf{f}. Then, we have the square system A\mathbf{f}\in \mathbf{k}[x]^n. Moreover, we can verify the property that \mathbb{V}(\mathbf{f})\subset \mathbb{V}(A\mathbf{f}).

We will check the simple example about these problems.

Consider the polynomial system \mathbf{f}=(x^2~y^2~xy) in \mathbb{Q}[x]. Then,

(1) find the multiplicity of (0,0)

(2) does “squaring up” change the multiplicity of (0,0)?

In here, the multiplicity is defined by the number of elements in \mathbb{Q}[x]/\left<x^2, y^2,xy\right>.

3

From the figure above, we know that the multiplicity is 3.

Now, we will take any 2 linear combinations of x^2, y^2 and xy.

5.jpg

When we calculate the Gröbner basis for the ideal generated by randomly obtained 2 polynomials, we know that the leading terms are xy, x^2 and y^3. Therefore, the multiplicity is changed from 3 to 4.

Advertisements

GitHub

What is GitHub?  If you are like me and have very little experience with computers, aside from email, then you probably don’t know what GitHub is.  I found this post to be very helpful in explaining what it is and why we would care to use it.  In short, GitHub is a version control system, it is open source, user-friendly, and we need it for our summer project.

Clear and easy to follow directions on how to set up an account and get started are available on Anton’s wiki.  Once you create an account, you would want to go to your settings and then choose the SSH and GPG Keys link from the left-hand tab (see below).

Screen Shot 2016-05-18 at 6.08.08 PM

Next, you would need to generate an SSH Key, following the instructions here. A link to these is also available on Anton’s wiki.

Once you have completed this part, open Aquamacs, if you are working on MacOSX, or Emacs for Windows OS.  Find/open the file named init.m2 in Aquamacs or Emacs; you can reference this post on where to look for the initialization file.  Once you have located the initialization file, you would want to redirect the path highlighted in the screenshot below.

Screen Shot 2016-05-18 at 9.52.27 PM.png

Replace the highlighted path with
-- path = {"< ~ >/M2/M2/Macaulay2/packages/"} | path.

This allows you to pull the Macaulay2 packages from the repository you cloned from GitHub.

Installing Macaulay2 on Microsoft-Windows

Macaulay2 would be the most important computer program that we may use. It is a useful calculation program especially for Algebraic Geometry field. There are lots way to run Macaulay2, but we will use the editor GNU Emacs. Since Macaulay2 can be supported by MacOSX and Linux, it may be not that problematic to install Macaulay2 for Mac, Linux users. However, Macaulay2 for Microsoft-Windows is not yet compiled and so, it may be a bit hard to start Macaulay for Windows users. Thus, in this post I will briefly introduce the way to install Macaulay2 on Windows environment.

Actually.. It can be a little personal.

First, the main instruction for the installation is here (Professor Anton’s website). To launch Macaulay2, we first need to make an environment of Linux-Ubuntu. In order to run Ubuntu on Windows, we use the Virtual Machine(VM), for instance, Virtualbox. Since Anton’s instruction and attached files provide whole method and conditions for installing Macaulay2 on Linux-Ubuntu. Thus, if you download Virtualbox, then you can just run the attached file on Anton’s instruction. Then, you may easily launch Emacs and Macaulay2 at there.

However, in my computer (I use Microsoft Surface pro 2, actually which is not that good machine on 2016) Anton’s attached file doesn’t work. So we selected the other way. We downloaded Ubuntu directly and made a new virtual system by using that. Now, what should we do is installing Emacs and Macaulay2. Our instruction for this issue was in the official page for Macaulay2. First by clicking ctrl+alt+t, we can open the terminal. Then, by using command sudo emacs /etc/apt/sources.list we can install the Emacs. After that we should add the line deb http://www.math.uiuc.edu/Macaulay2/Repositories/Ubuntu xenial main in the file  /etc/apt/sources.list (You may use Emacs for this).  Then, back to terminal and enter the public key sudo apt-key adv –keyserver hkp://keys.gnupg.net –recv-key CD9C0E09B0C780943A1AD85553F8BD99F40DCB31 for Macaulay2. And then the last things to do is installing Macaulay2 by using the following commands.

sudo apt-get update -q
sudo apt-get install -y -q macaulay2

You may need to download some files first (the files on the first part of the instruction for installing Macaulay2).

 

Now, it is  time to run Macaulay2 on Emacs.

First, enter alt+x and enter M2. Then, we can start Macaulay2.

1

We can make a temporary file to make a script file or load the exist script file. The content of the script can be calculated by f112.jpg

Numerical Algebraic Geometry

First Post!

We are a group of mathematicians from Georgia Tech: one professor – Anton Leykin, and three students: Tim, Cvetelina, & Kisun.  During the summer semester of 2016 we will be studying Numerical Algebraic Geometry; we will use this blog as the framework for this course/project.  Our main goals are listed below.

  • Create a knowledge base for Numerical Algebraic Geometry
    • Create a database of entries containing notes, problems, examples, etc.
  • Documentation of NumericalAlgebraicGeometry Package for Macaulay2
    • NumericalAlgebraicGeometry is a package used in Macaulay2, which is a software system used primarily in algebraic geometry and commutative algebra.  A description of this package is described here.  Our goal is to refine the documentation, provide appropriate examples, and relevant explanations.
  • Create a library of examples
    • Test the code from the NumericalAlgebraicGeometry package against this library of examples for efficiency.

In addition to three main goals listed above, collaboration is another component in our project.  We will welcome several visitors during the month of June whose work ranges from theory to applications in various fields, such as biology and computer vision.