On the complexity of matrix reduction over finite fields
Matrices over special rings (quaternions, finite fields, etc.) (15B33) Direct numerical methods for linear systems and matrix inversion (65F05) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
The authors study the complexity of matrix elimination over finite fields in terms of row operations.They present an algorithm called ``striped matrix elimination which is asymptotically faster than traditional Gauss-Jordan elimination. They present results of a large computational study of complexities for small matrices and fields.Finally they give a conjecture on the behaviour of a natural analogue of GLn for semifields and prove this for a certain class of semifields
- Some algorithms related to matrices with entries in a finite field
- Sparse Gaussian Elimination Modulo p: An Update
- Algebraic complexity theory. II: Tast matrix multiplication and combinatorics.
- On practical algorithms for accelerated matrix multiplication
- Fast rectangular matrix multiplication and applications
- A course in combinatorics.
- Diameters of finite simple groups: sharp bounds and applications
- Finite semifields and projective planes
- scientific article; zbMATH DE number 1645815 (Why is no real title available?)
- scientific article; zbMATH DE number 3956969 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1952951 (Why is no real title available?)
- scientific article; zbMATH DE number 2176112 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- On the Evaluation of Powers and Monomials
- On the interval containing at least one prime number
- Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
- Techniques for Enumerating Veblen-Wedderburn Systems
- The Factorization of the Ninth Fermat Number
- The minimum number of edges in graphs with prescribed paths
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Cutoff for a stratified random walk on the hypercube
- Uniquely pressable graphs: characterization, enumeration, and recognition
- An average John theorem
- Fast matrix decomposition in F₂
- Reducing the number of operations in certain finite- field transforms (Corresp.)
- Some algorithms related to matrices with entries in a finite field
- Smallest Reduction Matrix of Binary Quadratic Forms
- Cutoff for a stratified random walk on the hypercube
- Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields
- Reduction of matrices over orders of imaginary quadratic fields
- An algebraic formulation of Pauli flow, leading to faster flow-finding algorithms
- Mixing time of a matrix random walk generated by elementary transvections
- A hybrid algorithm for the regular syndrome decoding problem
- Cutoff for product replacement on finite groups
This page was built for publication: On the complexity of matrix reduction over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467342)
