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+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. -- 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.
