Processor efficient parallel solution of linear systems over an abstract field

Publisher Website
Google Scholar
Abstract
Parallel randomized algorithms are presented that solve n-dimensional systems of linear equations and compute inverses of n x n non-singular matrices over a field in O((log n)z) time, where each time unit represents an arithmetic operation in the field generated by the matrix entries. The algorithms utilize within a O(log n) factor as many processors as are needed to multiply two n x n matrices. The algorithms avoid zero divisions with controllably high probability provided the O(n) random elements used are selected uniformly from a sufficiently large set. For fields of small positive characteristic, the processor count measures of our solutions are somewhat higher.

This publication has 0 references indexed in Scilit: