On a non-archimedean broyden method

Xavier Dahan, Tristan Vaccon

TL;DR

This paper introduces a non-archimedean adaptation of Broyden's method, a popular quasi-Newton technique for solving nonlinear equations. The authors demonstrate that this new method converges at least Q-linearly and R-superlinearly, offering a valuable tool for exact computations in fields like p-adic analysis and power series.

What Problem Does This Paper Address?

Newton's method is a cornerstone for solving nonlinear equations, but its non-archimedean counterpart (e.g., for p-adic numbers or power series) has some unique advantages, like efficient Jacobian evaluation and inherent quadratic convergence. However, Broyden's method, a widely used alternative that approximates the Jacobian, has historically been difficult to adapt to non-archimedean settings due to challenges like the absence of inner products and more subtle arithmetic precision management. This paper aims to bridge this gap by developing and analyzing a non-archimedean Broyden's method.

Methods

The core of the paper is the adaptation of Broyden's method to a general non-archimedean setting. This involves:

  • Adapting the update rule: The standard Broyden update rule, which relies on specific vector norms and inner products, is modified to be compatible with the ultrametric norms prevalent in non-archimedean fields. This includes careful handling of vector norms and the definition of update vectors ($u_n$).
  • Sherman-Morrison Formula: The paper leverages the Sherman-Morrison formula to efficiently update the inverse of the approximate Jacobian matrix.
  • Convergence Analysis: The authors rigorously analyze the Q- and R-convergence of their adapted method. They prove Q-linear convergence and R-superlinear convergence with an order of $2^m$ in dimension $m$.
  • Finite Precision Implementation: A significant portion of the paper is dedicated to discussing how to implement this method efficiently in finite precision arithmetic, a crucial aspect for practical applications. This involves adaptive precision management and careful handling of potential precision loss during computations.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical examples rather than large-scale datasets.

Key Insights and Ideas

  • Non-archimedean Broyden is possible: The paper demonstrates that Broyden's method, despite its reliance on inner products in the archimedean world, can be successfully adapted to non-archimedean fields.
  • R-superlinear convergence is achievable: A key theoretical result is the proof of R-superlinear convergence, which is a strong indicator of practical efficiency.
  • Finite precision is crucial: The paper highlights the importance of careful precision management for implementing non-archimedean methods, especially Broyden's, which can be more sensitive to precision than Newton's method.
  • Newton's method still has an edge for polynomials: While the non-archimedean Broyden method is a valuable theoretical and practical tool, the authors acknowledge that for polynomial systems in high dimensions, Newton's method might still offer a better cost-precision trade-off due to its inherent quadratic convergence and efficient Jacobian evaluation in this context.

Key Results

  • The proposed non-archimedean Broyden method converges at least Q-linearly.
  • The method achieves R-superlinear convergence with an order of $2^m$ in dimension $m$.
  • The paper provides a detailed framework for implementing the method with adaptive finite precision, crucial for practical computations.
  • Numerical experiments with polynomial systems show the method's behavior, with plots illustrating the convergence of the valuation of $f(x_k)$ and an estimation of the Q-convergence order.

Limitations and Future Work

  • Q-superlinear convergence conjecture: While the paper proves R-superlinear convergence, it conjectures that the method also achieves Q-superlinear convergence, similar to its archimedean counterpart. Proving this remains an open question.
  • Comparison with Newton's method: The authors note that for high-dimensional polynomial systems, Newton's method might still be more efficient due to its faster convergence rate and specialized evaluation techniques in non-archimedean settings. Further investigation into the exact conditions where Broyden's method outperforms Newton's is suggested.
  • Generalization: The authors believe their approach can be expanded to a broader variety of quasi-Newton methods.
  • Practical applications: The paper mentions potential applications in solving ODEs with parameters and in situations where direct Jacobian computation is difficult, suggesting avenues for future research.

Summary updated

Abstract

Newton's method is an ubiquitous tool to solve equations, both in the archimedean and non-archimedean settings -- for which it does not really differ. Broyden was the instigator of what is called "quasi-Newton methods". These methods use an iteration step where one does not need to compute a complete Jacobian matrix nor its inverse. We provide an adaptation of Broyden's method in a general non-archimedean setting, compatible with the lack of inner product, and study its Q and R convergence. We prove that our adapted method converges at least Q-linearly and R-superlinearly with R-order $2^{\frac{1}{2m}}$ in dimension m. Numerical data are provided.
BibTeX
@inproceedings{dahan2020non,
  author = {Xavier Dahan and Tristan Vaccon},
  title = {{On a non-archimedean broyden method}},
  booktitle = {Issac},
  year = {2020},
  doi = {10.1145/3373207.3404045},
}
Figure