| 摘 要： | A PL homotopy algorithm is modified to yield a polynomial-time result on its computational complexity.We prove that the cost of locating all zeros of a polynomial of degree n to an accuracy of ε(measured by the number of evaluations of the polynomial)grows no faster than O(max{n~4,n~3log_2(n/ε)}).This work is in response to a question raised in a paper by S.Smale as to the efficiency of piecewise linear methods in solving equations.In comparison with a few results reported,the algorithm under discussion is the only one providing correct multiplicities and the only one employing vector labelling.
|
