A polynomial homotopy is a family of polynomial systems, typically in one parameter. Given a polynomial homotopy and an isolated solution, the nearest singular solution in this homotopy can be computed via application of the ratio theorem of Fabry. This application requires the computation of power series and the solution of a lower triangular block Toeplitz system. The first block in this Toeplitz system is the Jacobian matrix while the other blocks collect the information of the higher-order derivatives with respect to the parameter in the homotopy. For Newton's method to converge to accurate values of the higher-order coefficients of the series, multiprecision arithmetic is needed. As multiprecision arithmetic leads to a significant overhead in the computational cost, deciding the right level of precision depends on the computed number of terms in the series and the proximity to the nearest singular solution. For higher precision, multiple double arithmetic is applied. A multiple double is an unevaluated sum of hardware doubles. If the result can be represented exactly by the leading double(s), then the trailing double represents the error on the result. This property of multiple doubles, combined with the freedom to multiply the parameter in the homotopy with a nonzero constant, leads to an adaptive Newton method to accurately compute the coefficients of power series solutions of polynomial homotopies.
SIAM LA 2024, 17 May 2024, Paris, France.