As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence:

$\qquad f_{p_0} = 0\\ \qquad p_0 = 2\\ \qquad \displaystyle f_{p_n}(x) = f_{p_{n-1}}(x) + \prod_{k=2}^{p_{n-1}} (-\cos(2\pi(x+k-1)/p_{n-1}) + 1)\\ \qquad \displaystyle p_n = \min\left\{ x > p_{n-1} \mid f_{p_n}(x) = 0\right\}$

Playing with this system a bit over on Wolfram|Alpha, it seems I can get specific answers to the recurrence from their computer algebra system. Unfortunately, I can find no specific documentation on the methods they're using to solve my equations.

My question, then:

What methods (and what time and space complexities) do computer algebra systems use to solve these forms of equations? I suspect the Gröbner basis is commonly used, but I could be very wrong.

  • 2
    $\begingroup$ Good question! If you don't get an answer here, your might want to visit mathematica.SE. Please wait a few days, though, because crossposting is generally frowned upon. $\endgroup$
    – Raphael
    Commented May 28, 2012 at 9:57
  • 1
    $\begingroup$ There are open source computer algebra packages around, like maxima.sourceforge.net. One possible technique is to just express everything in terms of $\tan \theta$, which reduces trignometric expressions to a "simple" algebraic problem to munge. $\endgroup$
    – vonbrand
    Commented Jan 28, 2013 at 23:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.