DocumentCode :
941172
Title :
Solving sparse linear equations over finite fields
Author :
Wiedemann, Douglas H.
Volume :
32
Issue :
1
fYear :
1986
fDate :
1/1/1986 12:00:00 AM
Firstpage :
54
Lastpage :
62
Abstract :
A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all require 
field operations, where 
is the maximum dimension of the coefficient matrix, 
is approximately the number of field operations required to apply the matrix to a test vector, and the value of 
depends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.
field operations, where is the maximum dimension of the coefficient matrix, is approximately the number of field operations required to apply the matrix to a test vector, and the value of depends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.Keywords :
Sparse matrices; Computational complexity; Difference equations; Galois fields; Linear systems; Polynomials; Sparse matrices; Testing; Vectors;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1986.1057137
Filename :
1057137
Link To Document :
