# 0.1 The lindsey-fox algorithm for factoring polynomials  (Page 3/3)

 Page 3 / 3

Stage two is more traditional than the other two. It “polishes” each of the prospective zeros found by the grid search. The first phase consists of applying an iterative algorithm to improve the accuracy of the location found by the grid search. In earlier versions of the program, Newton’s method was used but analysis and experiment showed that Laguerre’s method [18,19] was both more robust and more accurate. Even though it required more calculation than Newton’s method for each iteration, it converged in fewer iterations. The second phase of the second stage checks for duplications. A “fuzzy” uniqueness test is applied to each zero to eliminate any cases where on two or more prospective zeros, iterations converged to the same zero. If the number of unique, polished zeros is less than the degree of the polynomial, deflation later will be necessary. If the number is greater, some error has occurred. This stage consumes the largest part of the execution time of the total factorization, but it is crucial to the final accuracy of the roots. One of the two criteria for success in factoring a polynomial is that each root must have been successfully polished against the original polynomial.

Stage three has several phases and possible iterations or even restarting. The first phase of the third stage takes all of the unique, polished zeros that were found in the first two stages and multiplies them together into the coefficient form of a candidate polynomial (“unfactors” the zeros). If the degree of this reconstructed polynomial is the same as that of the original polynomial and if the difference in their coefficients is small, the factorization is considered successful. Often, however, several zeros were missed by the grid search and polish processes of stage one and two, or the uniqueness test discarded a legitimate zero (perhaps it is multiple), so the original polynomial is “deflated” (divided) by the reconstructed polynomial and the resulting (low degree) quotient is factored for the missing zeros. If that doesn’t find them all, the deflation process is repeated until they are all found. This allows the finding of multiple roots (or very tightly clustered roots), even if some of them were discarded earlier. If, in the unusual case, these further iterations of deflation do not find all of the missing zeros, a new, finer grid is constructed and the whole process started again at stage one. More details on the third stage are in another module.

Multiple order and clustered roots are unusual in random coefficient polynomials. But, if they happen or if factoring an ill-conditioned polynomial is attempted, the roots will be found with the Lindsey-Fox program in most cases but with reduced accuracy. If there are multiple order zeros (Mth order with M not too high), the grid search will find them, but with multiplicity one. The polishing will converge to the multiple order root but not as fast as to a distinct root. In the case of a cluster with Q zeros that fall within a single cell, they are erroneously identified as a single zero and the polishing will converge to only one of them. In some cases, two zeros can be close to each other in adjacent cells and polish to the same point. In all of these cases, after the uniqueness test and deflation, the quotient polynomial will contain a M-1 order zero and/or Q-1 zeros clustered together. Each of these zeros will be found after M-1 or Q-1 deflations. There can be problems here because Laguerre’s polishing algorithm is not as accurate and does not converge as fast for a multiple zero and it may even diverge when applied to tightly clustered zeros. Also, the condition of the quotient polynomial will be poorer when multiple and clustered zeros are involved. If multiple order zeros are extremely far from the unit circle, the special methods for handling multiple roots developed by Zhonggang Zeng [5] are used. Zeng’s method is powerful but slow, and hence only used in special cases [6]. References

Successful completion of the factoring of a polynomial requires matching zeros on the complex plane measured by the convergence of Laguerre’s algorithm on each of the zeros. It also requires matching the polynomial reconstructed from the found zeros with the original polynomial by measuring the maximum difference in each coefficient.

## Characteristics of the lindsey-fox algorithm

Because the FFT is such an efficient means of evaluating the polynomial, a very fine grid can be used which will separate all or almost all of the zeros in a reasonable time. And because of the fineness of the grid, the starting point is close to the actual zero and the polishing almost always converges in a small number of steps (convergence is often a serious problem in traditional approaches). And because the searching and polishing is done on the original polynomial, they can be done on each root simultaneously on a parallel architecture computer. Because the searching is done on a 3 by 3 cell of the grid, no more that three concentric circles of the grid need be kept in memory at a time, i.e., it is not necessary to have the entire grid in memory. And, some parallelization of the FFT calculations can be done.

Deflation is often a major source of error or failure in a traditional iterative algorithm. Here, because of the good starting points and the powerful polisher, very few stages of deflation are generally needed and they produce a low order quotient polynomial that is generally well-conditioned. Moreover, to control error, the unfactoring (multiplying the found roots together) is done in the FFT domain (for degree larger than 500) and the deflation is done partly in the FFT domain and partly in the coefficient domain, depending on a combination of stability, error accumulation, and speed factors.

For random coefficient polynomials, the number of zeros missed by the grid search and polish stages ranges from 0 to 10 or occasionally more. In factoring one 2 million degree polynomial, the search and polish stages found all 2 million zeros in one grid search and required no deflation which shows the power of the grid search on this class of polynomial. When deflation is needed, one pass is almost always sufficient. However, if you have a multiple zero or two (or more) very, very closely spaced zeros, the uniqueness test will discard a legitimate zero but it will be found by later deflation. Stage three has enough tests and alternatives to handle almost all possible conditions. But, by the very definition of random coefficients, it is hard to absolutely guarantee success.

The timings of the The Lindsey-Fox program can be found here and examples of root distributions of polynomials with random coefficients are here.

#### Questions & Answers

where we get a research paper on Nano chemistry....?
nanopartical of organic/inorganic / physical chemistry , pdf / thesis / review
Ali
what are the products of Nano chemistry?
There are lots of products of nano chemistry... Like nano coatings.....carbon fiber.. And lots of others..
learn
Even nanotechnology is pretty much all about chemistry... Its the chemistry on quantum or atomic level
learn
da
no nanotechnology is also a part of physics and maths it requires angle formulas and some pressure regarding concepts
Bhagvanji
hey
Giriraj
Preparation and Applications of Nanomaterial for Drug Delivery
revolt
da
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
ya I also want to know the raman spectra
Bhagvanji
I only see partial conversation and what's the question here!
what about nanotechnology for water purification
please someone correct me if I'm wrong but I think one can use nanoparticles, specially silver nanoparticles for water treatment.
Damian
yes that's correct
Professor
I think
Professor
Nasa has use it in the 60's, copper as water purification in the moon travel.
Alexandre
nanocopper obvius
Alexandre
what is the stm
is there industrial application of fullrenes. What is the method to prepare fullrene on large scale.?
Rafiq
industrial application...? mmm I think on the medical side as drug carrier, but you should go deeper on your research, I may be wrong
Damian
How we are making nano material?
what is a peer
What is meant by 'nano scale'?
What is STMs full form?
LITNING
scanning tunneling microscope
Sahil
how nano science is used for hydrophobicity
Santosh
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest. Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.? How this robot is carried to required site of body cell.? what will be the carrier material and how can be detected that correct delivery of drug is done Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
Anam
Any one who tell me about Preparation and application of Nanomaterial for drug Delivery
Hafiz
what is Nano technology ?
write examples of Nano molecule?
Bob
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
why we need to study biomolecules, molecular biology in nanotechnology?
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
why?
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
how did you get the value of 2000N.What calculations are needed to arrive at it
Privacy Information Security Software Version 1.1a
Good
Got questions? Join the online conversation and get instant answers!