A p-adic algorithm for computing the inverse of integer matrices

摘要

A method for computing the inverse of an (n×n) integer matrix A using p-adic approximation is given. The method is similar to Dixon’s algorithm, but ours has a quadratic convergence rate. The complexity of this algorithm (without using FFT or fast matrix multiplication) is O(n4(logn)2), the same as that of Dixon’s algorithm. However, experiments show that our method is faster. This is because our methods decrease the number of matrix multiplications but increase the digits of the components of the matrix, which suits modern CPUs with fast integer multiplication instructions.