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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
