On the complexity of matrix reduction over finite fields

DOI10.1016/J.AAM.2006.08.008MaRDI QIDQ2467342zbMATH OpenOpenAlexFDO

Authors Daniel Andrén, Lars Hellström, Klas Markström

Publication date 21 January 2008

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aam.2006.08.008

zbMATH Keywords

algorithmsemifieldsGauss-Jordan elimination

Mathematics Subject Classification ID

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) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Recommendations

• 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

Cites work

• 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?)
• A course in combinatorics.
• Diameters of finite simple groups: sharp bounds and applications
• Finite semifields and projective planes
• 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

Cited in

(11)

• Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields
• Reduction of matrices over orders of imaginary quadratic fields
• Reducing the number of operations in certain finite- field transforms (Corresp.)
• Smallest Reduction Matrix of Binary Quadratic Forms
• An average John theorem
• Cutoff for a stratified random walk on the hypercube
• Fast matrix decomposition in \(\mathbb F_2\)
• Some algorithms related to matrices with entries in a finite field
• Cutoff for product replacement on finite groups
• Cutoff for a stratified random walk on the hypercube
• Uniquely pressable graphs: characterization, enumeration, and recognition

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)