# Feasible way to find interpolating complex polynomial based on absolute value

Consider a complex degree-$$(n-1)$$ polynomial $$p(z) = \sum\limits_{i=0}^{n-1} a_i z^i$$.

1. Given a number $$0 < m < 2n$$ of positions in the complex plane with absolute value requirements, i.e. $$|p(z_j)| \overset{!}{=} b_j$$ (with $$b_j \geq 0$$), is there a practical algorithm to find the coefficients $$a_i$$ such that $$p(z)$$ satisfies those requirements? In other words, is there a way to solve a complex polynomial interpolation problem based only on given absolute values, leaving the argument (angle) of the polynomial completely arbitrary at any point?
2. How big can $$m$$ be for such an algorithm? In other words, how many degrees of freedom are gained by only specifying the absolute value instead of a "full" complex number consisting of an absolute value and an argument (angle)?
• I have never seen an exclamation point placed above an equality sign. What does this combination of symbols mean? In any case, have you tried writing your problem as a real system of non-linear equations for a small value of $n$? – Carl Christian Dec 10 '18 at 9:28
• @CarlChristian My bad. This is indeed pretty nonstandard notation. It's supposed to mean "has to be equal to". It's basically still just an equality. I have tried writing the equation system out for a small n. The equations are not at all straightforward to solve, which is why I asked the question here. The best algorithms I have found so far that can actually solve this in a practical way are optimization algorithms (differential evolution etc.). Since these generally have exponential complexity, they do not scale well. My n is usually something like 1024. – Lasse Dec 11 '18 at 12:53
• In truth, I do not see an alternative to doing a non-linear solve. I suspect that it will be important not to use square roots needlessly and solve $p_j \bar{p}_j = b_j^2$. It might be useful to know what your specific application is. – Carl Christian Dec 11 '18 at 15:48

Considering the simple case of $$n = 2$$, it turns out to be rather trivial to find $$m = 3$$ conditions $$|p(z_j)| \overset{!}{=} b_j$$ that no polynomial of degree $$1$$ can satisfy. Hence, $$m$$ can not be greater than $$n$$ in the general case. There are however some (not so rare) examples of conditions which can be satisfied.
For $$m \leq n$$, the polynomial can easily be found by choosing a random argument (angle) for each $$b_j$$ and then solving the resulting system of linear equations. Since a polynomial only exists in some special cases when $$m > n$$, an algorithm to find that polynomial for arbitrary conditions cannot exist. There still might be a way to determine the space of conditions that yield a polynomial and a corresponding algorithm, though.