<< Chapter < Page Chapter >> Page >

The lindsey-fox program can be outlined by:

Stage one: the grid search for prospective zeros

  1. Construct a polar coordinate grid on the complex plane with spacing derived from the degree of the polynomial being factored
  2. Use the FFT to evaluate the polynomial at each node along the concentric circles of the grid.
  3. Search over each 3x3 set of values for relative minima. If the center value is less than the edge values, it is a prospective zero by the Minimum Modulus Theorem of complex analysis.

Stage two: polish the prospective zeros

  1. Apply Laguerre’s algorithm to each prospective zero, correcting it to a better approximation of the “true” zero of the polynomial
  2. Test the set of polished zeros for uniqueness and discard any duplicates to give a set of candidate zeros

Stage three: Unfactor, perhaps deflate, and verify

  1. Unfactor the polished zeros i.e., reconstruct a candidate polynomial in coefficient form from the polished candidate zeros
  2. If the degree of the reconstructed polynomial is the same as that of the original polynomial and differences in their coefficients are small, the factoring is successful and finished
  3. If some zeros were missed, deflate and factor the quotient polynomial. If that does not find all of the missed zeros, deflate and factor again until all are found or until no new ones are found
  4. If deflation finds all the zeros that it can, and it still has not found them all, design a new grid with a finer spacing and return to stage one. If four restarts do not find them all and/or the reconstruction error is not small, declare failure.

Description of the three stages

Stage one is the reason this algorithm is so efficient and is what sets it apart from most other factoring algorithms. Because the FFT (fast Fourier transform) is used to evaluate the polynomial, a fast evaluation over a dense grid in the complex plane is possible. In order to use the FFT, the grid is structured in polar coordinates. In the first phase of this stage, a grid is designed with concentric circles of a particular radius intersected by a set of radial lines. The positions and spacing of the radial lines and the circles are chosen to give a grid that will hopefully separate the expected roots. Because the zeros of a polynomial with random coefficients have a fairly uniform angular distribution and are clustered close to the unit circle, it is possible to design an evaluation grid that fits the expected root density very well. In the second phase of this stage, the polynomial is evaluated at the nodes of the grid using the fast Fourier transform (FFT). It is because of the extraordinary efficiency and accuracy of the FFT that a direct evaluation is possible. In the third phase of this first stage, a search is conducted over all of the 3 by 3 node cells formed in the grid. For each 3 by 3 cell (see Figure below), if the value of the polynomial at the center node of the cell (the "x") is less than the values at all 8 of the nodes on the edges of the cell (the "o's"), the center is designated a candidate zero. This rule is based on the “Minimum Modulus Theorem” which states that if a relative minimum of the absolute value of an analytic function over an open region exists, the minimum must be a zero of the function. Finally, this set of prospective zeros is passed to the second stage. The number is usually slightly larger than the degree because some were found twice or mistakes were made. The number could be less if some zeros were missed.

Questions & Answers

what is Nano technology ?
Bob Reply
write examples of Nano molecule?
The nanotechnology is as new science, to scale nanometric
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
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.
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
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?