ChainComplex() runs 24 times slower than homology()

asked 2018-10-28 09:55:39 +0200

Leon
99 ●2 ●6 ●10

I load a list of matrices bdrs representing a chain complex, their dimensions are {1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1}, and the largest has density 3.91*10^-6. In total they take up 50MB of disk space. This finishes in 63sec.

When I run chcx=ChainComplex(bdrs,base_ring=GF(2)), it takes 7hrs20min, but chcx.homology() finishes in only 18min. Why does it take so long to just store a few matrices? At first I thought that ChainComplex() also does some simplifications/reductions, but [chcx.free_module_rank(i) for i in range(0,21)] shows the original dimensions of matrices :/.

Is there a faster way to compute the homology of a chain complex (over $\mathbb{Z}$ or $\mathbb{Z}_p$)?

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2018-10-28 10:51:41 +0200

rburing

10644 ●4 ●77 ●211 https://www.rburing.nl/

According to the documentation of ChainComplex there is an optional argument

check – boolean (optional, default True). If True, check that each consecutive pair of differentials are composable and have composite equal to zero.

I can imagine this takes a while. How fast is it with check=False?

edit flag offensive delete link

Comments

Aaah, you're right, with check=False, it only takes 3sec. Sorry for not noticing this option in the documentation, and thank you for your help!

Leon ( 2018-10-28 15:42:00 +0200 )edit

add a comment

answered 2018-10-28 12:15:18 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

Apparently (unfortunately), there is no way to specify/detect that your objects are sparse when defining the chain complex.

You could try to enforce that by giving as few choice as possible to the ChainComplex by defining bdrs to be sparse matrices explicitely defined over GF(2).

Please tell us if is works. Otherwise, could you please provide your code so that we can handle a concrete example and see what is going on ?

edit flag offensive delete link

Comments

Surely, ChainComplex() detects that these are sparse matrices, otherwise I wouldn't have enough RAM to store $10^6\times10^6=10^{12}$ entries... But still, thank you for your help!

Leon ( 2018-10-28 15:45:02 +0200 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

ChainComplex() runs 24 times slower than homology()

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

ChainComplex() runs 24 times slower than homology() edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

ChainComplex() runs 24 times slower than homology()