Solving sparse linear systems of equations over finite fields using bit-flipping algorithm

Let F-q be the finite field with q elements. We give an algorithm for solving sparse linear systems of equations over F-q when the coefficient matrix of the system has a specific structure, here called relatively connected. This algorithm is based on a well-known decoding algorithm for low-density parity-check codes called bit-flipping algorithm. We modify and extend this hard decision decoding algorithm. The complexity of this algorithm is linear in terms of the number of columns n and the number of nonzero coefficients omega of the matrix per iteration. The maximum number of iterations is bounded above by m, the number of equations. (C) 2013 Elsevier Inc. All rights reserved.