Naïve endomorphism_algebra implementation gets slow for large dimensions

[mgkurtz]

For an algebra generated by several 50×50 matrices, say 40, computing the endomorphism_algebra consumes lots of memory and time. Precisely, time and memory goes into vcat and right_kernel (and there into rref) in the code snippet below:

Hecke.jl/src/AlgAssAbsOrd/Conjugacy/Conjugacy.jl

Lines 567 to 583 in bc4f3c4

	linind = transpose(LinearIndices((n,m)))
	zz = zero_matrix(FlintQQ, 0, n*m)
	for (A, B) in zip(As, Bs)
	z = zero_matrix(FlintQQ, n*m, n*m)
	for i in 1:m
	for j in 1:n
	for k in 1:n
	z[linind[i, j], linind[i, k]] += A[k, j]
	end
	for k in 1:m
	z[linind[i, j], linind[k, j]] -= B[i, k]
	end
	end
	end
	zz = vcat(zz, z)
	end
	r, K = right_kernel(zz)

This code builds a 40⋅50²×50² “dense” matrix with only two 50+50 non-zero entries per row. Using sparse matrices instead of dense ones, and adding the rows iteratively to a rref instead of building a giant matrix, should reduce memory and time consumption by a lot, I guess.

Additionally a comment, to explain the code, could help. I guess, the lines

Hecke.jl/src/AlgAssAbsOrd/Conjugacy/Conjugacy.jl

Lines 593 to 595 in bc4f3c4

	for i in 1:length(As)
	M * As[i] == Bs[i] * M
	end

should be assertions, which (if they were assertions) already helped explaining the code.

[thofma]

Yes and yes. I only used it for toying around so far, but your suggestions sound good.

[mgkurtz]

Seems, like I am bad at counting. There are actually n+m (here 100) entries per row. So, even with sparse matrices that can take some time. Anyway, there are more efficient algorithms out there. I will see, how far I come, with the tools Hecke or Oscar already include.