4
$\begingroup$

I have an application that basically reduces to testing whether a given function vanishes identically. The function is given symbolically, using unary and binary operators on complex numbers. For example, we might want to test the function $(z+1)^2-z^2-2z-1$. (It could be a function of more than one variable.)

The problem is known to be undecidable. However, there are reasonable heuristic approaches. The one I've been using involves numerical sampling. I just pick random complex values for $z$, and evaluate the function using machine-precision arithmetic. This works pretty well in most cases, and is efficient. If the function is known to be analytic, then the method would succeed with unit probability given infinite-precision arithmetic.

One could use a computer algebra system for this, but a CAS is computationally expensive and often will not reach any definite conclusion.

Although the numerical sampling heuristic generally works pretty well, it's not hard to come up with examples where it fails. For example, consider the function $z^{100}$. For almost any $|z|<1$, I get an underflow, and for almost any $|z|>1$, I get an overflow. Either way, the result is inconclusive. (An overflow doesn't automatically tell me the function is nonzero, because it could happen at some intermediate step in the computation.)

Can this heuristic be improved on? Using multiple-precision arithmetic rather than machine precision doesn't seem to be a big win. It's much more computationally expensive, and even if I take 100 digits of precision, it's still pretty easy to construct examples where it fails.

It seems like it might make sense to try some kind of adaptive algorithm in bad cases to search for regions of the complex plane that neither underflow nor overflow. Or more generally we could maintain error bounds, and search for regions where the error bounds do not make the result inconclusive.

Symbolic differentiation is cheap and doesn't fail, so I could also test whether the function's derivatives are zero. But this doesn't necessarily help for an example like $z^{100}$, unless I happen to get lucky and try the 100th derivative.

$\endgroup$
  • 1
    $\begingroup$ What are the class of operators that are permitted? If it's a polynomial (as in your example) then you can use polynomial identity testing. $\endgroup$ – D.W. May 22 '15 at 6:02
  • $\begingroup$ @D.W.: It's a pretty wide class of operators. There's documentation here lightandmatter.com/spotter/spotter.html , but it includes division, exponentiation, trig functions, ... In a lot of cases the function is nonanalytic in certain places, but is analytic almost everywhere. $\endgroup$ – Ben Crowell May 22 '15 at 13:28

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.