search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.42k stars 477 forks source link

k-regular-sequences guessing: make searching for inverse matrix more efficient #35748

Open dkrenn opened 1 year ago

dkrenn commented 1 year ago

Just noting that this here is quite inefficient: It would be more efficient to compute the row echelon form for as many columns as we need and extracting the information on the linearly independent columns from the row echelon form.

Keeping track of the row transformations would allow to add additional columns as needed.

I do not know whether such a variant of row echelon form is available in SageMath.

Furthermore, in verify_linear_combination, we could find out what column we need to add to get the next invertible submatrix.

Perhaps add some comment into the code, we do not want to delay this PR by rewriting everything.

_Originally posted by @cheuberg in https://github.com/sagemath/sage/pull/35682#discussion_r1208449176_

DaveWitteMorris commented 1 year ago

Please fix the typo in the title of this issue: "reguar" should be "regular". (The creator [and others with sufficient permissions] should have an "Edit" button to the right of the title.)