0.5 Mathematical principles for the lf algorithm

Addendum: mathematical principles

The mathematical principles at the core of the Lindsey-Fox algorithm for polynomial factoring are given here.

An $N^{th}$ degree polynomial is denoted by

or

where $k=1,2,\cdots ,N$ or

where $m=1,2,\cdots ,Q$ and $N={\sum }_m{M}_m$ . And $a_n$ is the $n^{th}$ coefficient, $z_k$ is the $k^{th}$ zero or root, $N$ is the degree of the polynomial, $M_m$ is the multiplicity of the $m^{th}$ zero, and $Q$ is number of distinct roots or zeros.

The fundamental theorem of algebra states that an $N^{th}$ degree polynomial has $N$ zeros.

The length- $L$ discrete Fourier transform (DFT) of the $N$ coefficients of a polynomial $P\left(z\right)$ with $L\ge N$ are the $L$ equally spaced samples of the polynomial evaluated on the unit circle of the complex plane.

for $k=0,1,2,\cdots ,L-1$

If the coefficients are multiplied by a geometric sequence, $r^n$ , the DFT of this modulated set of coefficients are the $L$ equally spaced samples of the polynomial evaluated on a circle of radius $r$ in the complex plane.

for $k=0,1,2,\cdots ,L-1$

Using Horner's method, the number of multiplications and additions necessary to directly calculate $N$ equally spaced values of a degree $N$ polynomial on the unit circle is proportional to $N^2$ . If evaluated with the DFT, it is also proportional to $N^2$ . If evaluated with the FFT, it is proportional to $Nlog\left(N\right)$ .

If the roots of a polynomial are at $z$ , the roots of the same polynomial with the sequence of coefficients reversed (“flipped"), are at $1/z$ .

The “Minimum Modulus Theorem" can be stated several ways. A way most applicable to our test of the 3 node by 3 node cells is: If the minimum of an analytic function of a complex variable occurs in the interior of an open set, the minimum must in fact be a zero of the function.

If Newton's algorithm is applied to a polynomial and is started sufficiently close to a zero, it will quadratically converge to that zero if the zero is simple. If the zero is multiple, it still converges but only linearly. If Laguarre's algorithm is applied to a polynomial and is started sufficiently close to a zero, it will cubically converge to that zero if the zero is simple. If the zero is multiple, it still converges but only linearly.