Super-linear convergence in the p-adic QR-algorithm

Abstract

The QR-algorithm is one of the most important algorithms in linear algebra. Its several variants make feasible the computation of the eigenvalues and eigenvectors of a numerical real or complex matrix, even when the dimensions of the matrix are enormous. The first adaptation of the QR-algorithm to local fields was given by the first author in 2019. However, in this version the rate of convergence is only linear and in some cases the decomposition into invariant subspaces is incomplete. We present a refinement of this algorithm with a super-linear convergence rate in many cases.

Keywords:

• QR-algorithm
• symbolic-numeric
• p-adic approximation
• pnumerical linear algebra

2010 Mathematics Subject Classifications:

• 15A18 (primary)
• 11S05 (secondary)

Acknowledgments

The authors would like to thank the mathematics department at TU Kaiserslautern for sponsoring the visit of the second author. We would also like to thank Eran Assaf and John Voight for their especially insightful comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Avinash Kulkarni has been supported by the Simons Collaboration on Arithmetic Geometry, Number Theory, and Computation (Simons Foundation grant 550033) and by the Forschungsinitiative on Symbolic Tools at TU Kaiserslautern.