Solving linear systems of determinant frequently zero over finite field GF(2)

DOI10.1016/0898-1221(89)90222-8MaRDI QIDQ1262699zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 1989

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(89)90222-8

zbMATH Keywords

algebraic linear codesalgorithmcomplexitydecodingfinite field GF(2)VLSI implementations

Mathematics Subject Classification ID

Finite fields and commutative rings (number-theoretic aspects) (11T99) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Direct numerical methods for linear systems and matrix inversion (65F05) Linear codes (general theory) (94B05)

Review text

The paper deals with the solution of linear systems of the form \(Ax=b\) over the finite field GF(2). The best known computational methods consider only systems with nonzero determinant. The purpose of the paper is to solve systems with \(\det (A)=0.\) The authors first compute the probability of \(\det (A)=0\) over GF(2), a question of interest in application to the decoding of algebraic linear codes over GF(2). Then an algorithm is proposed and tree data structure is given to accomplish the computational tasks of the algorithm, which takes 2n-1 systolic cycles, yielding time complexity O(n). Advantages and disadvantages of this algorithm for VLSI implementations are discussed, based on consideration of speed, chip area, and regularity. Finally, some comments on the extension to systems over GF(p) are given.

Recommendations

• Solving sparse linear equations over finite fields
• Solving linear equations over GF(2): Block Lanczos algorithm
• Rational solutions of singular linear systems
• Solving sparse linear systems of equations over finite fields using bit-flipping algorithm
• scientific article; zbMATH DE number 1256710

Cites work

• How often do determinants over finite fields vanish?
• scientific article; zbMATH DE number 3318360 (Why is no real title available?)
• scientific article; zbMATH DE number 3336895 (Why is no real title available?)
• scientific article; zbMATH DE number 3373921 (Why is no real title available?)
• Transform Techniques for Error Control Codes

This page was built for publication: Solving linear systems of determinant frequently zero over finite field GF(2)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262699)