Iterative and direct P;Adic algorithms for exact solution of numerical problems

Abstract

In this chapter, we have described an O(n³), 2 < P < 3 algorithm for inverting integer matrices using p-adic computations. Some of the important aspects of this method are: (a) Absence of any convergence problems – the initial approximation is chosen deterministically as the inverse of the given matrix modulo a prime p, and the iterative steps generate the successive p-adic digits. If the iterations are carried out a required number of times to uniquely recover the Farey rationals represented by the finite segment p-adic representation, the inversion procedure is complete, giving exact rational results. (b) Exact parallel computation – the rational elements of the inverse matrix are simultaneously determined in p-adic digit parallel fashion with a quadratic or higher rate. (c) Easy parallel realizations – since the procedure involves only recursive matrix multiplications (with no other manipulation), it is amenable for parallel computation.