𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by H. Haramoto; M. Matsumoto

Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
270 KB
Volume
225
Category
Article
ISSN
0377-0427

No coin nor oath required. For personal study only.

✦ Synopsis

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(n 4 (log n) 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.

πŸ“œ SIMILAR VOLUMES

A fast algorithm for the inversion of ge
A fast algorithm for the inversion of general Toeplitz matrices
✍ P.G. Martinsson; V. Rokhlin; M. Tygert πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 590 KB

we propose a "fast" algorithm for the construction of a data-sparse inver'~ of a general Toeplitz matrix. The computational cost for inverting an N Γ— N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(Nlog2N) cost of previously published

The Group Ring of SL2(pf) over p-adic In
The Group Ring of SL2(pf) over p-adic Integers for p Odd
✍ Gabriele Nebe πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 234 KB

Let p ) 2 be a prime, R s β€«ήšβ€¬ , K s ‫ޑ‬ , and G s SL p . The p p y1 p p y1 2 group ring RG is calculated nearly up to Morita equivalence: The projections of RG into the simple components of KG are given explicitly and the endomorphism rings and homomorphism bimodules between the projective indecompo