Iterative root approximation in pp-adic numerical analysis

The standard way to compute a pp-adic zero αα of a univariate polynomial ff 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 pp-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 mm, under the simplifying assumption that both pp and the degree of ff 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.