Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are there any non-trivial parallel algorithms to find the optimum (local or global) of polynomials? By trivial, I mean something which is an obvious application of a serial algorithm. For example, one trivial way to parallelize the search for a global optimum would be to partition the space and then search for a global optimum amongst all the partitions in parallel.

share|cite|improve this question

To the best of my knowledge, parallelization of this problem is not done as you suggested, i.e., searching in parallel the whole space to determine extremal points. A much faster parallelization method for multi-variate polynomials (when appropriate) may be based on the use of parallel automatic differentiation, the (parallel) solution of the resulting system of equations and finally the study of the related Hessian.

However, you may consider non trivial the paper "Polynomial Optimization via Recursions and Parallel Computing", which deals with the problem of finding the global minimum for a special class of dominated real valued polynomials.

"A Parallel-Computing Solution for Optimization of Polynomials" provides a parallel algorithm for determining polynomial positivity.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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