<< Chapter < Page Chapter >> Page >
Section of the polar coordinate grid showing a 3 node by 3 node cell

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

Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
what school?
biomolecules are e building blocks of every organics and inorganic materials.
anyone know any internet site where one can find nanotechnology papers?
Damian Reply
sciencedirect big data base
Introduction about quantum dots in nanotechnology
Praveena Reply
what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
how to know photocatalytic properties of tio2 nanoparticles...what to do now
Akash Reply
it is a goid question and i want to know the answer as well
characteristics of micro business
for teaching engĺish at school how nano technology help us
Do somebody tell me a best nano engineering book for beginners?
s. Reply
there is no specific books for beginners but there is book called principle of nanotechnology
what is fullerene does it is used to make bukky balls
Devang Reply
are you nano engineer ?
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
what is the actual application of fullerenes nowadays?
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
what is the Synthesis, properties,and applications of carbon nano chemistry
Abhijith Reply
Mostly, they use nano carbon for electronics and for materials to be strengthened.
is Bucky paper clear?
carbon nanotubes has various application in fuel cells membrane, current research on cancer drug,and in electronics MEMS and NEMS etc
so some one know about replacing silicon atom with phosphorous in semiconductors device?
s. Reply
Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.
Do you know which machine is used to that process?
how to fabricate graphene ink ?
for screen printed electrodes ?
What is lattice structure?
s. Reply
of graphene you mean?
or in general
in general
Graphene has a hexagonal structure
On having this app for quite a bit time, Haven't realised there's a chat room in it.
what is biological synthesis of nanoparticles
Sanket Reply
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Factoring polynomials of high degree. OpenStax CNX. Apr 01, 2012 Download for free at http://cnx.org/content/col10494/1.9
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Factoring polynomials of high degree' conversation and receive update notifications?