Indeed the determinant code in matrix2.pyx is a huge mess. Some
dispatch is unavoidable but many specialized matrix implement
their own determinant function:
matrix_complex_ball_dense.pyx
matrix_double_dense.pyx
matrix_gap.pyx
matrix_integer_dense.pyx
matrix_mod2_dense.pyx
matrix_modn_sparse.pyx
matrix_mpolynomial_dense.pyx
matrix_rational_dense.pyx
Because of this, I wonder if some of the dispatch could simply
be avoided in the generic matrix2.pyx.
Also, since for the symbolic ring, since there is a class
matrix_symbolic_dense.pyx the code dedicated to this case would
better go there.
Vincent
Le 16/03/2019 à 10:38, 'Martin R' via sage-devel a écrit :
I think the problem is that it computes the characteristic polynomial and
then takes the constant term. That seems a bit wasteful, no?
c = self.charpoly(var, algorithm="df")[0]
Martin
Am Freitag, 15. März 2019 23:07:04 UTC+1 schrieb Dima Pasechnik:
On Fri, Mar 15, 2019 at 02:59:05PM -0700, Kwankyu Lee wrote:
If the determinant is obviously zero, then you don't need to run the
computation. If a preprocessing to check zero rows or columns is added,
then the determinant computation would become slower for usual
nontrivial
cases.
I would not be so categorical here. It makes a perfect sense to add a
parameter to the determinant function that would switch such a check on.
Similarly, one can think of adding a check for rows with just one non-0,
as they can be used for a very effcient reduction...
Dima
Cheers.
On Saturday, March 16, 2019 at 2:15:06 AM UTC+9, Maximilian Jaroschek
wrote:
Hello,
I'm using the current developer version of sage and noticed that when
computing determinants of matrices over polynomial rings and rational
functions, cases where the determinant is easily seen to be zero due
to
zero rows or columns can take an unreasonable long time to compute. I
compared the timings with the same computation over other domains.
sage: L.<x>=PolynomialRing(QQ)
sage: MS=MatrixSpace(L,100)
sage: time _=MS.zero().determinant()
CPU times: user 13.4 s, sys: 19.6 ms, total: 13.5 s
Wall time: 13.5 s
sage: MS=MatrixSpace(L.fraction_field(),100)
sage: time _=MS.zero().determinant()
CPU times: user 200 ms, sys: 0 ns, total: 200 ms
Wall time: 200 ms
sage: MS=MatrixSpace(ZZ,100)
sage: time _=MS.zero().determinant()
CPU times: user 563 盜, sys: 5 盜, total: 568 盜
Wall time: 573 盜
sage: MS=MatrixSpace(L,40)
sage: M=MS.random_element(3)
sage: M=M.with_rescaled_row(0,0)
sage: M.rows()[0]==0
True
sage: time _=M.determinant()
CPU times: user 35.2 s, sys: 8.06 ms, total: 35.2 s
Wall time: 35.2 s
sage: MS=MatrixSpace(L.fraction_field(),10)
sage: M=MS.random_element(3)
sage: M=M.with_rescaled_row(0,0)
sage: M.rows()[0]==0
True
sage: time _=M.determinant()
CPU times: user 1min 56s, sys: 300 ms, total: 1min 56s
Wall time: 1min 56s
sage: MS=MatrixSpace(ZZ,500)
sage: M=MS.random_element(2^40)
sage: M=M.with_rescaled_row(0,0)
sage: M.rows()[0]==0
True
sage: time _=M.determinant()
CPU times: user 67.6 ms, sys: 0 ns, total: 67.6 ms
Wall time: 67.9 ms
sage:
Probably a preprocessing step could help that looks for zero rows or
columns before running the actual algorithm.
Best,
Maximilian
--
You received this message because you are subscribed to the Google
Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to sage-devel+...@googlegroups.com <javascript:>.
To post to this group, send email to sage-...@googlegroups.com
<javascript:>.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
