Project

General

Profile

Slug #691

Matrix determinant over ZZ

Added by John Abbott almost 9 years ago. Updated over 4 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Improving
Start date:
29 Apr 2015
Due date:
% Done:

100%

Estimated time:
1.33 h
Spent time:

Description

I tried computing the following:
M := Mat(ZZ,[[random(-9,9) | i in 1..500] | j in 1..500]);
D := det(M); // how much time?

Which is faster?
  • A CoCoA-5.1.2 + CoCoALib 0.99536 on 2.4GHz Intel Core 2 duo
  • B CoCoA-4.5 on 1.07GHz PowerPC G4

Answer: they took about the same time!


Related issues

Related to CoCoALib - Slug #1110: Determinant of matrix over QQ (whose entries are actually integers)Closed2017-10-25

Related to CoCoALib - Feature #11: Bareiss algorithmClosed2011-10-20

Related to CoCoALib - Feature #1278: Port old "clever" code for matrix determinant over ZZ to CoCoALibNew2019-05-03

History

#1 Updated by John Abbott almost 9 years ago

What?!? My dad's ancient iBook G4 is just as fast as my much newer MacBook Pro???

Something must be seriously wrong!

#2 Updated by John Abbott almost 9 years ago

I've just tried a 1000x1000 matrix: the old G4 took about 550s, my newer MacBook Pro took 1400s. Embarrassing!

NOTE CoCoA-4.7.6 on MacBook Pro took about 220s

#3 Updated by John Abbott almost 9 years ago

Just as a speed comparison reference I computed 3^(3^17) on both machines:
  • old G4 took about 50s (on battery power)
  • new MacBook Pro took 2.8s (on mains)

Of course the underlying version of GMP is not the same, but I suspect that they are fairly similar for power/product of integers. So the newer machine is about 20 times faster than the old one.

#4 Updated by John Abbott almost 9 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

Hint: DenseMatrix.C:462 the dispatch function DenseMatImpl::myDet does not handle matrices over ZZ specially -- they are just passed to a Bareiss impl.

#5 Updated by John Abbott over 6 years ago

  • Related to Slug #1110: Determinant of matrix over QQ (whose entries are actually integers) added

#6 Updated by John Abbott almost 6 years ago

CoCoALib currently uses DetByCRT rather than the "clever" algorithms used in CoCoA-4.7. This issue should be about porting that old code to CoCoALib.

Anyway, the times on my Linux laptop are now about 75s for a 1000x1000 matrix, and about 4.5s for a 500x500 matrix.

#7 Updated by John Abbott almost 5 years ago

  • Status changed from In Progress to Closed
  • Assignee set to John Abbott
  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99700
  • % Done changed from 10 to 100
  • Estimated time set to 1.33 h

I think this was resolved some time ago when I arranged for the code to recognise the case that the entries are all integers. Anyway, this improved code is acceptably fast (for the time being).

Closing, but will create a new issue to port the old "clever" CoCoA-4 code to CoCoALib.

#8 Updated by John Abbott almost 5 years ago

#9 Updated by John Abbott almost 5 years ago

  • Related to Feature #1278: Port old "clever" code for matrix determinant over ZZ to CoCoALib added

#10 Updated by Anna Maria Bigatti over 4 years ago

  • Target version changed from CoCoALib-0.99700 to CoCoALib-0.99650 November 2019

Also available in: Atom PDF