Ask Your Question

ChainComplex() runs 24 times slower than homology()

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

Leon gravatar image

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

2 Answers

Sort by » oldest newest most voted

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

rburing gravatar image

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 more



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 gravatar imageLeon ( 2018-10-28 15:42:00 +0200 )edit

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

tmonteil gravatar image

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 more



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 gravatar imageLeon ( 2018-10-28 15:45:02 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 318 times

Last updated: Oct 28 '18