3
$\begingroup$

Let $\Delta$ be a standard $k$-simplex, and let $f:\Delta\to\mathbb R^N$ be a polynomial map with known numerical coefficients. What sort of practical computational algorithms can be used to investigate whether $f$ has self-intersections, or, the limiting case of self-intersection, points $x\in\Delta$ where the derivative $f'(x):\mathbb R^k\to\mathbb R^n$ has rank less than $k$? I'm not interested in the location of the points, and my wish is for a Yes/No answer.

However, one can't hope for a Yes/No answer. For example, if one is looking at real curves in $\mathbb R^3$, then changing one of the coefficients slightly will convert a near miss into an intersection, and floating point error will raise its ugly head. But one could hope for Yes/No/Near. It seems that one could do a brute force search, but this might take a long time. Can one do better than using one of the optimizing procedures for more general functions? I know little about this, but these general methods can miss the points one is looking for. Is there a method that takes advantage of the polynomial nature of $f$ to work faster and/or give better information? It seems fairly obvious that a brute force method could give a guaranteed Yes/No/Near answer, where Near means to within a given $\varepsilon$.

I'm mainly thinking of low degree polynomials, for example total degree 3, but I'm not interested in total degree 1, for which the answers are trivial. Even so, there can be a lot of coefficients, depending on the sizes of $k$ and $N$. I would like to implement something (or preferably use someone else's code) that works reasonably for $k\le10$, or even $k\le5$, and $N\le 50$. I'm also interested in a theoretical algorithm for the general case, without restrictions on $k$ and $N$, together with complexity estimates.

$\endgroup$
1
$\begingroup$

I am curious what you have tried, since writing the question as

$$\mathbf{f}(t) - \mathbf{f}(s) = \mathbf{w},$$ With $t, s$ constrained to lie in the simplex and $w$ constrained to have norm smaller than $\epsilon$ (for your favorite $\epsilon$ defining proximity) defines a perfectly pleasant semi-algebraic set, and Cylindrical Algebraic Decomposition (CAD) should tell you if it has any real points. You can do Reduce[] in Mathematica, just to see how far it goes before blowing up, or use more specialized tools such as qepcad (available through Sage) or in CGAL.

$\endgroup$
  • $\begingroup$ You can also solve the exact problem, assuming $f$ has rational or algebraic coefficients, using CAD (or other quantifier elimination algorithms). Since these algorithms are algebraic, you do not need to worry about floating point issues, but on the other hand the run time can be really bad. $\endgroup$ – Noah Stein Oct 24 '14 at 17:13
  • $\begingroup$ Useful answers, as I didn't know about these algorithms for semi-algebraic set. Igor's formulation is not quite right because if $t$ is near $s$, then $w$ will always exist. I'll rely on whatever Mathematica does about floating point error, applied to Igor's formula with $w=0$, $s\neq t$. I'll try to see if there are solutions for various small $\varepsilon$ using Reduce on $(s-t)^2=0$ and $s=t+\varepsilon$, though this might be too simple to fool Mathematica. $\endgroup$ – David Epstein Oct 27 '14 at 15:54
  • $\begingroup$ Can anyone give comparative timings for C/C++ vs Mathematica on CAD? I was wondering about the immersion part of my question. It seems that Row Echelon Form would be the way to go, combined with Reduce or CAD. Comments? $\endgroup$ – David Epstein Oct 27 '14 at 16:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.