Solving sparse linear equations over finite fields
1986
A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all require O(n_{1}(\omega + n_{1})\log^{k}n_{1}) field operations, where n_{1} is the maximum dimension of the coefficient matrix, \omega is approximately the number of field operations required to apply the matrix to a test vector, and the value of k 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:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
521
Citations
NaN
KQI