Error-Free Parallel High-Order Convergent Iterative Matrix Inversion Based on p-ADIC Approximation.

摘要

The Newton-Schultz iterative scheme is reformulated in an algebraic setting to compute the exact inverse of a matrix (or the solution of a linear system of equations) over the ring of integers, with a high order or convergence, by using a finite segment p-adic representation of a rational. This method is divergence-free; it starts with the inverse of a given matrix over a finite field (called the priming step) and then iterates successively to construct, in parallel, the p-adic approximants (Hensel Codes) of the rational elements of the inverse matrix. The p-adic approximant is then converted back to the equivalent rational using the extended Euclidean algorithm. The method involves only parallel matrix multiplications and complementations and has a quadratic convergence rate. Extension to achieve higher order convergence is straightforward if parallel matrix arithmetic facilities for higher precision operands (in a prime base system) are available. (Author)