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.
