search

gap-system / gap

Main development repository for GAP - Groups, Algorithms, Programming, a System for Computational Discrete Algebra
https://www.gap-system.org
GNU General Public License v2.0
815 stars 161 forks source link

Faster `SwapMatrixRows` and `SwapMatrixColumns` for GF2 matrices #5837

Closed fingolfin closed 2 weeks ago

fingolfin commented 2 weeks ago

Before

gap> mat:=IdentityMat(10,GF(2));; ConvertToMatrixRep(mat);; mat;
<a 10x10 matrix over GF2>
gap> for i in [1..1000000] do SwapMatrixColumns(mat,1,2); od; time;
1020
gap> for i in [1..1000000] do SwapMatrixRows(mat,1,2); od; time;
167
gap> for i in [1..1000000] do tmp:=mat[1];mat[1]:=mat[2];mat[2]:=tmp; od; time;
85

After:

gap> mat:=IdentityMat(10,GF(2));; ConvertToMatrixRep(mat);; mat;
<a 10x10 matrix over GF2>
gap> for i in [1..1000000] do SwapMatrixColumns(mat,1,2); od; time;
135
gap> for i in [1..1000000] do SwapMatrixRows(mat,1,2); od; time;
77
gap> for i in [1..1000000] do tmp:=mat[1];mat[1]:=mat[2];mat[2]:=tmp; od; time;
87