Iterative root approximation in p-adic numerical analysis
The standard way to compute a p-adic zero alpha of a univariate polynomial f is to use Newton's method. In classical (real and complex) numerical analysis, however, one often prefers other algorithms, because they avoid derivatives or use fewer iterations. our goal is to initiate the systematic study of these other algorithms in the p-adic context. We determine explicit convergence regions for the secant method and Halley's method. We also investigate the computational cost of refining a root to precision m, under the simplifying assumption that both p and the degree off are large. We show that both of these methods can be implemented so that their cost matches that of Newton's method. Finally, we show that none of these three methods is optimal, by exhibiting two methods with lower asymptotic cost. (C) 2009 Elsevier Inc. All rights reserved.
polynomial zeros p-adic analysis