Error-Free Parallel High-Order Convergent Iterative Matrix Inversion Based on p-ADIC Approximation.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1982
- Accession Number
- ADA128418
Entities
People
- E. V. Krishnamurthy
Organizations
- University of Maryland