Skip to content

Actually avoid hermite_form in solve_right if possible #40497

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Aug 2, 2025
Merged

Actually avoid hermite_form in solve_right if possible #40497

merged 1 commit into from
Aug 2, 2025

Conversation

user202729
Copy link
Contributor

@user202729 user202729 commented Jul 28, 2025 •
edited
Loading

I tried to speed this up in #40276 , but there was some error in logic which makes it fail.

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

@user202729 user202729 mentioned this pull request Jul 28, 2025
Closed
user202729
user202729 commented Jul 28, 2025
View reviewed changes
src/sage/matrix/matrix2.pyx
@@ -901,7 +901,6 @@ cdef class Matrix(Matrix1):
sage: v = matrix.identity(QQ, 500).solve_right(vector(QQ, [1]*500), extend=False) # <1s
sage: matrix.identity(QQ, 500).hermite_form() # not tested (slow)
sage: v = (matrix.identity(ZZ, 500)*2).solve_right(vector(ZZ, [2]*500), extend=False) # <1s
sage: matrix.identity(ZZ, 500).hermite_form() # not tested (slow)
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This line was deleted because (surprisingly) it's actually fast. Only hermite_form of 2 × Id or something similar is slow.

@orlitzky
Copy link
Contributor

Before:

sage: m = matrix.identity(ZZ, 250).stack(matrix.identity(ZZ, 250))*2
sage: %timeit -c -n1 -r1 v = m.solve_right(vector(ZZ, [2]*500), extend=False)
2min 53s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
sage: %timeit -c -n1 -r1 v = m.solve_right(vector(ZZ, [2]*500), extend=False)
1min 25s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

After:

sage: m = matrix.identity(ZZ, 250).stack(matrix.identity(ZZ, 250))*2
sage: %timeit -c -n1 -r1 v = m.solve_right(vector(ZZ, [2]*500), extend=False)
1.98 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
sage: %timeit -c -n1 -r1 v = m.solve_right(vector(ZZ, [2]*500), extend=False)
1.62 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

Is the merge-fixes commit intentional? Otherwise LGTM, thanks.

@user202729 user202729 force-pushed the solve-right-avoid-hermite-2 branch from 727b7a0 to 7715d90 Compare July 28, 2025 23:43
@user202729
Copy link
Contributor Author

Indeed that's different issue, I moved that one to #40502 . (the rationale is explained there.)

@orlitzky
Copy link
Contributor

I'm fine with it as-is, but if the goal of these tests is to ensure that hermite_form() is avoided, you might be able to do something like the following instead:

sage: from sage.matrix.matrix_integer_dense import Matrix_integer_dense
sage: class MyMat(Matrix_integer_dense):
....:     def _solve_right_hermite_form(self, *args, **kwds):
....:         raise ValueError
....: 
sage: m = matrix.identity(ZZ, 250).stack(matrix.identity(ZZ, 250))*2
sage: m = MyMat(m.matrix_space(),m.list())
sage: v = m.solve_right(vector(ZZ, [2]*500), extend=False)  # works
sage: v = m._solve_right_hermite_form(vector(ZZ, [2]*500), extend=False)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[17], line 1
----> 1 v = m2._solve_right_hermite_form(vector(ZZ, [Integer(2)]*Integer(500)), extend=False)

Cell In[12], line 3, in MyMat._solve_right_hermite_form(self, *args, **kwds)
      2 def _solve_right_hermite_form(self, *args, **kwds):
----> 3     raise ValueError

ValueError:

You could then cut down the size of the examples from 500 to, say, 10. Which won't make a huge difference in speed but we'll actually be testing the thing we want to test.

@user202729
Copy link
Contributor Author

the goal is to make sure they're fast. the fact that it is implemented by avoiding computing the Hermite form of the matrix is only a implementation detail.

@vbraun vbraun merged commit fa83177 into sagemath:develop Aug 2, 2025
16 of 41 checks passed
@user202729 user202729 mentioned this pull request Aug 15, 2025
Open
5 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@user202729 @orlitzky @vbraun