1
$\begingroup$

I want to find the square root of a polynomial by the following process:

  1. Compute the N-element DFT of its coefficients, maybe padded with zeros.
  2. Compute the complex square root of each of the N elements of the DFT.
  3. Take the inverse DFT of the resulting array.

For the time being, I am assuming that the polynomial is a perfect square, so that it will have a polynomial as its square root. I have checked that the foregoing process works fine in some cases.

My problem is that there are two choices (+/-) for each of the N square roots. Only if I make correct choices will I get the correct phase spectrum so that the IDFT will give me the correct polynomial as solution.

  • How can I correctly choose the sign of each square root, other than (for example) by working through the 2^N possibilities until I find one that gives a polynomial as the result?

I have tried making use of the fact that the DFT should be 'smooth' if N is large relative to the order of the polynomial, but without getting anywhere.

[An example: if the polynomial has coefficients (1,2,3,4,3,2,1), its square root polynomial will have coefficients (1,1,1,1)]

Added

(1) I wonder if the problem can be solved by something analogous to the spectral factorization method used to find a minimum phase signal having a given autocorrelation function?

(2) The square root of a polynomial can be found without using the DFT, by long division. Algorithm for finding the square root of a polynomial…

$\endgroup$
  • $\begingroup$ Are the coefficients of the original polynomial real-valued? $\endgroup$ – Juancho May 15 '19 at 23:50
  • $\begingroup$ For the time being I am working with polynomials with real-valued (not necessarily integer) coefficients. If there were a solution for polynomials with complex valued coefficients, that would be even better. $\endgroup$ – Martin A May 17 '19 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.