computing determinants efficiently

[Luke Oeding]

Does anyone know of a faster implementation of determinant? In the
example below, I was not able to compute the determinant of a 9x9
matrix, much less compute all 9x9 minors of a 9x12 matrix. On the
other hand, Maple can quickly compute these things - I guess by using
row reduction. I would like to be able to make polynomials as
determinants in M2, and not have to copy and paste from Maple. Any
suggestions?

R = ZZ/2[Z000, Z100, Z200, Z010, Z110, Z210, Z020, Z120, Z220, Z001,
Z101, Z201, Z011, Z111, Z211, Z021, Z121, Z221, Z002, Z102, Z202,
Z012, Z112, Z212, Z022, Z122, Z222, Z003, Z103, Z203, Z013, Z113,
Z213, Z023, Z123, Z223]

A=matrix{{Z000, Z001, Z002, Z003}, {Z010, Z011, Z012, Z013}, {Z020,
Z021, Z022, Z023}}

B=matrix{{Z100, Z101, Z102, Z103}, {Z110, Z111, Z112, Z113}, {Z120,
Z121, Z122, Z123}}

C=matrix{{Z200, Z201, Z202, Z203}, {Z210, Z211, Z212, Z213}, {Z220,
Z221, Z222, Z223}}

Z=matrix{{0_R,0,0,0},{0,0,0,0},{0,0,0,0}}

M=(Z|(-1*C)|B)||(C|Z|(-1*A))||((-1*B)|A|Z)

determinant submatrix(M,,{1,2,3,5,6,7,9,10,11})

J=minors(9,M);

Best,
Luke

Luke Oeding
RTG Postdoctoral Fellow
Department of Mathematics
University of California, Berkeley

Office: 887 Evans Hall
Phone: (510) 643-8125

[Michael Stillman]

Luke,

The default Strategy for computing determinants over the ring R that you have is "Bareiss", which basically does a fraction free Gaussian elimination. The other strategy is "Cofactor", which is used over quotient rings as the default, since the Bareiss method is not correct for non-domains. Over RR or CC, a different method is used, basically Gaussian elimination with pivots.

In this case, the Cofactor strategy does much better:

M1 = submatrix(M,,{1,2,3,5,6,7,9,10,11})

determinant(M1, Strategy=>Cofactor) -- this one takes about .4 seconds on my macbook pro.

time J=minors(9,M, Strategy=>Cofactor); -- this one takes somewhat less than two minutes, average of .5 sec per det)

It is true that determinants need to be made faster in Macaulay2. Anyone interested in helping?

Best,

Mike

> --
> You received this message because you are subscribed to the Google Groups "Macaulay2" group.
> To post to this group, send email to maca...@googlegroups.com.
> To unsubscribe from this group, send email to macaulay2+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/macaulay2?hl=en.
>

[Michael Stillman]

Here is another suggestion. Pack monomials in your ring, using MonomialSize=>8 (this means that the maximum exponent of any variable is 127, above that, one gets an error). This increases the speed by roughly a factor of 3 in this example.

R = ZZ/2[Z000, Z100, Z200, Z010, Z110, Z210, Z020, Z120, Z220, Z001,
Z101, Z201, Z011, Z111, Z211, Z021, Z121, Z221, Z002, Z102, Z202,
Z012, Z112, Z212, Z022, Z122, Z222, Z003, Z103, Z203, Z013, Z113,

Z213, Z023, Z123, Z223, MonomialSize=>8]

Then, the first determinant (using Strategy=>Cofactor, as in my last post), takes .1 seconds, and all 220 determinants (again, with Cofactor) takes 45 seconds (on my 2 year old macbookpro, running M2 version 1.4.0.1 -- the trunk version).

-- Mike

On Dec 15, 2011, at 3:24 PM, Luke Oeding wrote: