search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.32k stars 451 forks source link

Request: Cythonize `dhsw_snf` #38028

Open sweeneyde opened 3 months ago

sweeneyde commented 3 months ago

Problem Description

The dhsw_snf function in matrix_utils.py seems to be the bottleneck in some chain complex integral homology computations that I'm running. I'm working with matrices roughly of the shape Matrix(ZZ, 500, 500, sparse=True).

Here's an example benchmark:

data = {(0,0):1,(0,4):1,(0,12):-1,(0,36):1,(1,1):1,(1,3):1,(1,13):-1,(1,37):1,(2,2):1,(2,5):1,(2,6):1,(2,7):1,(2,8):3,(2,14):-1,(2,38):1,(3,13):1,(3,39):1,(4,12):1,(4,40):1,(5,14):1,(5,15):1,(5,16):1,(5,17):3,(5,41):1,(6,15):-1,(6,25):-3,(6,42):1,(7,16):-1,(7,26):-3,(7,43):1,(8,17):-1,(8,25):1,(8,26):1,(8,44):1,(9,9):1,(9,27):1,(9,30):1,(9,39):-1,(10,10):1,(10,28):1,(10,31):1,(11,11):1,(11,29):1,(11,32):1,(11,33):1,(11,34):1,(11,35):3,(12,12):1,(12,40):1,(13,13):1,(13,39):1,(14,14):1,(14,41):1,(14,42):1,(14,43):1,(14,44):3,(15,15):1,(15,42):-1,(15,52):-3,(16,16):1,(16,43):-1,(16,53):-3,(17,17):1,(17,44):-1,(17,52):1,(17,53):1,(18,18):1,(18,45):1,(18,54):1,(18,58):1,(18,75):3,(19,19):1,(19,46):1,(19,55):1,(19,57):1,(19,76):3,(20,20):1,(20,47):1,(20,56):1,(20,59):1,(20,60):1,(20,61):1,(20,62):3,(20,77):3,(21,21):1,(21,48):1,(21,63):1,(21,66):1,(21,78):3,(22,22):1,(22,49):1,(22,64):1,(22,67):1,(22,79):3,(23,23):1,(23,50):1,(23,65):1,(23,68):1,(23,69):1,(23,70):1,(23,71):3,(23,80):3,(24,24):1,(24,51):1,(24,72):1,(24,73):1,(24,74):3,(25,25):1,(25,52):1,(26,26):1,(26,53):1,(27,82):1,(27,84):1,(27,90):-1,(27,117):1,(27,121):1,(27,252):1,(27,256):1,(27,271):1,(28,85):1,(28,91):-1,(28,118):1,(28,253):1,(29,86):1,(29,87):1,(29,88):1,(29,89):3,(29,92):-1,(29,119):1,(29,254):1,(30,90):1,(30,273):1,(31,91):1,(31,274):1,(32,92):1,(32,96):1,(32,97):1,(32,98):3,(32,275):1,(33,96):-1,(33,106):-3,(33,276):1,(34,97):-1,(34,107):-3,(34,277):1,(35,98):-1,(35,106):1,(35,107):1,(35,278):1,(36,108):1,(36,112):1,(36,120):-1,(36,243):1,(37,109):1,(37,111):1,(37,121):-1,(37,244):1,(38,110):1,(38,113):1,(38,114):1,(38,115):1,(38,116):3,(38,122):-1,(38,245):1,(39,121):1,(39,246):1,(40,120):1,(40,247):1,(41,122):1,(41,123):1,(41,124):1,(41,125):3,(41,248):1,(42,123):-1,(42,133):-3,(42,249):1,(43,124):-1,(43,134):-3,(43,250):1,(44,125):-1,(44,133):1,(44,134):1,(44,251):1,(45,126):1,(45,135):1,(45,139):1,(45,156):3,(45,261):1,(46,127):1,(46,136):1,(46,138):1,(46,157):3,(46,262):1,(47,128):1,(47,137):1,(47,140):1,(47,141):1,(47,142):1,(47,143):3,(47,158):3,(47,263):1,(48,129):1,(48,144):1,(48,147):1,(48,159):3,(48,264):1,(49,130):1,(49,145):1,(49,148):1,(49,160):3,(49,265):1,(50,131):1,(50,146):1,(50,149):1,(50,150):1,(50,151):1,(50,152):3,(50,161):3,(50,266):1,(51,132):1,(51,153):1,(51,154):1,(51,155):3,(51,267):1,(52,133):1,(52,268):1,(53,134):1,(53,269):1,(54,166):1,(54,174):-1,(54,225):-3,(55,165):1,(55,175):-1,(55,226):-3,(56,167):1,(56,168):1,(56,169):1,(56,170):3,(56,176):-1,(56,227):-3,(57,165):-1,(57,175):1,(57,228):-3,(58,166):-1,(58,174):1,(58,229):-3,(59,167):-1,(59,176):1,(59,177):1,(59,178):1,(59,179):3,(59,230):-3,(60,168):-1,(60,177):-1,(60,187):-3,(60,231):-3,(61,169):-1,(61,178):-1,(61,188):-3,(61,232):-3,(62,170):-1,(62,179):-1,(62,187):1,(62,188):1,(62,233):-3,(63,192):1,(63,198):-1,(63,234):-3,(64,193):1,(64,199):-1,(64,235):-3,(65,194):1,(65,195):1,(65,196):1,(65,197):3,(65,200):-1,(65,236):-3,(66,192):-1,(66,198):1,(66,237):-3,(67,193):-1,(67,199):1,(67,238):-3,(68,194):-1,(68,200):1,(68,204):1,(68,205):1,(68,206):3,(68,239):-3,(69,195):-1,(69,204):-1,(69,214):-3,(69,240):-3,(70,196):-1,(70,205):-1,(70,215):-3,(70,241):-3,(71,197):-1,(71,206):-1,(71,214):1,(71,215):1,(71,242):-3,(72,223):-3,(73,224):-3,(74,223):1,(74,224):1,(75,225):1,(75,229):1,(76,226):1,(76,228):1,(77,227):1,(77,230):1,(77,231):1,(77,232):1,(77,233):3,(78,234):1,(78,237):1,(79,235):1,(79,238):1,(80,236):1,(80,239):1,(80,240):1,(80,241):1,(80,242):3,(81,120):1,(81,247):1,(82,121):1,(82,246):1,(83,122):1,(83,248):1,(83,249):1,(83,250):1,(83,251):3,(84,82):1,(84,84):1,(84,117):1,(84,246):-1,(84,252):1,(84,256):1,(84,271):1,(84,273):1,(85,81):1,(85,247):-1,(85,255):1,(85,270):1,(86,83):1,(86,248):-1,(86,257):1,(86,258):1,(86,259):1,(86,260):3,(86,272):1,(87,123):1,(87,249):-1,(87,268):-3,(88,124):1,(88,250):-1,(88,269):-3,(89,125):1,(89,251):-1,(89,268):1,(89,269):1,(90,90):1,(90,273):1,(91,91):1,(91,274):1,(92,92):1,(92,275):1,(92,276):1,(92,277):1,(92,278):3,(93,93):1,(93,273):-1,(93,279):1,(93,282):1,(94,94):1,(94,274):-1,(94,280):1,(94,283):1,(95,95):1,(95,275):-1,(95,281):1,(95,284):1,(95,285):1,(95,286):1,(95,287):3,(96,96):1,(96,276):-1,(96,295):-3,(97,97):1,(97,277):-1,(97,296):-3,(98,98):1,(98,278):-1,(98,295):1,(98,296):1,(99,99):1,(99,288):1,(99,297):1,(99,301):1,(99,318):3,(100,100):1,(100,289):1,(100,298):1,(100,300):1,(100,319):3,(101,101):1,(101,290):1,(101,299):1,(101,302):1,(101,303):1,(101,304):1,(101,305):3,(101,320):3,(102,102):1,(102,291):1,(102,306):1,(102,309):1,(102,321):3,(103,103):1,(103,292):1,(103,307):1,(103,310):1,(103,322):3,(104,104):1,(104,293):1,(104,308):1,(104,311):1,(104,312):1,(104,313):1,(104,314):3,(104,323):3,(105,105):1,(105,294):1,(105,315):1,(105,316):1,(105,317):3,(106,106):1,(106,295):1,(107,107):1,(107,296):1,(108,324):1,(108,328):1,(108,351):1,(109,325):1,(109,327):1,(109,333):-1,(109,352):1,(110,326):1,(110,329):1,(110,330):1,(110,331):1,(110,332):3,(110,353):1,(111,333):1,(111,354):1,(112,334):1,(112,355):1,(113,335):1,(113,339):1,(113,340):1,(113,341):3,(113,356):1,(114,339):-1,(114,349):-3,(114,357):1,(115,340):-1,(115,350):-3,(115,358):1,(116,341):-1,(116,349):1,(116,350):1,(116,359):1,(117,333):1,(117,354):1,(118,334):1,(118,355):1,(119,335):1,(119,356):1,(119,357):1,(119,358):1,(119,359):3,(120,336):1,(120,354):-1,(120,360):1,(120,363):1,(121,337):1,(121,355):-1,(121,361):1,(121,364):1,(122,338):1,(122,356):-1,(122,362):1,(122,365):1,(122,366):1,(122,367):1,(122,368):3,(123,339):1,(123,357):-1,(123,376):-3,(124,340):1,(124,358):-1,(124,377):-3,(125,341):1,(125,359):-1,(125,376):1,(125,377):1,(126,342):1,(126,369):1,(126,378):1,(126,382):1,(126,399):3,(127,343):1,(127,370):1,(127,379):1,(127,381):1,(127,400):3,(128,344):1,(128,371):1,(128,380):1,(128,383):1,(128,384):1,(128,385):1,(128,386):3,(128,401):3,(129,345):1,(129,372):1,(129,387):1,(129,390):1,(129,402):3,(130,346):1,(130,373):1,(130,388):1,(130,391):1,(130,403):3,(131,347):1,(131,374):1,(131,389):1,(131,392):1,(131,393):1,(131,394):1,(131,395):3,(131,404):3,(132,348):1,(132,375):1,(132,396):1,(132,397):1,(132,398):3,(133,349):1,(133,376):1,(134,350):1,(134,377):1,(135,409):1,(135,417):-1,(135,468):-3,(136,408):1,(136,418):-1,(136,469):-3,(137,410):1,(137,411):1,(137,412):1,(137,413):3,(137,419):-1,(137,470):-3,(138,408):-1,(138,418):1,(138,471):-3,(139,409):-1,(139,417):1,(139,472):-3,(140,410):-1,(140,419):1,(140,420):1,(140,421):1,(140,422):3,(140,473):-3,(141,411):-1,(141,420):-1,(141,430):-3,(141,474):-3,(142,412):-1,(142,421):-1,(142,431):-3,(142,475):-3,(143,413):-1,(143,422):-1,(143,430):1,(143,431):1,(143,476):-3,(144,435):1,(144,441):-1,(144,477):-3,(145,436):1,(145,442):-1,(145,478):-3,(146,437):1,(146,438):1,(146,439):1,(146,440):3,(146,443):-1,(146,479):-3,(147,435):-1,(147,441):1,(147,480):-3,(148,436):-1,(148,442):1,(148,481):-3,(149,437):-1,(149,443):1,(149,447):1,(149,448):1,(149,449):3,(149,482):-3,(150,438):-1,(150,447):-1,(150,457):-3,(150,483):-3,(151,439):-1,(151,448):-1,(151,458):-3,(151,484):-3,(152,440):-1,(152,449):-1,(152,457):1,(152,458):1,(152,485):-3,(153,466):-3,(154,467):-3,(155,466):1,(155,467):1,(156,468):1,(156,472):1,(157,469):1,(157,471):1,(158,470):1,(158,473):1,(158,474):1,(158,475):1,(158,476):3,(159,477):1,(159,480):1,(160,478):1,(160,481):1,(161,479):1,(161,482):1,(161,483):1,(161,484):1,(161,485):3,(162,162):1,(162,405):1,(162,486):1,(162,490):1,(162,498):-1,(162,522):1,(162,675):3,(163,163):1,(163,406):1,(163,487):1,(163,489):1,(163,499):-1,(163,523):1,(163,676):3,(164,164):1,(164,407):1,(164,488):1,(164,491):1,(164,492):1,(164,493):1,(164,494):3,(164,500):-1,(164,524):1,(164,677):3,(165,165):1,(165,408):1,(165,499):1,(165,525):1,(165,678):3,(166,166):1,(166,409):1,(166,498):1,(166,526):1,(166,679):3,(167,167):1,(167,410):1,(167,500):1,(167,501):1,(167,502):1,(167,503):3,(167,527):1,(167,680):3,(168,168):1,(168,411):1,(168,501):-1,(168,511):-3,(168,528):1,(168,681):3,(169,169):1,(169,412):1,(169,502):-1,(169,512):-3,(169,529):1,(169,682):3,(170,170):1,(170,413):1,(170,503):-1,(170,511):1,(170,512):1,(170,530):1,(170,683):3,(171,171):1,(171,414):1,(171,495):1,(171,513):1,(171,516):1,(171,525):-1,(171,684):3,(172,172):1,(172,415):1,(172,496):1,(172,514):1,(172,517):1,(172,685):3,(173,173):1,(173,416):1,(173,497):1,(173,515):1,(173,518):1,(173,519):1,(173,520):1,(173,521):3,(173,686):3,(174,174):1,(174,417):1,(174,498):1,(174,526):1,(174,687):3,(175,175):1,(175,418):1,(175,499):1,(175,525):1,(175,688):3,(176,176):1,(176,419):1,(176,500):1,(176,527):1,(176,528):1,(176,529):1,(176,530):3,(176,689):3,(177,177):1,(177,420):1,(177,501):1,(177,528):-1,(177,538):-3,(177,690):3,(178,178):1,(178,421):1,(178,502):1,(178,529):-1,(178,539):-3,(178,691):3,(179,179):1,(179,422):1,(179,503):1,(179,530):-1,(179,538):1,(179,539):1,(179,692):3,(180,180):1,(180,423):1,(180,504):1,(180,531):1,(180,540):1,(180,544):1,(180,561):3,(180,693):3,(181,181):1,(181,424):1,(181,505):1,(181,532):1,(181,541):1,(181,543):1,(181,562):3,(181,694):3,(182,182):1,(182,425):1,(182,506):1,(182,533):1,(182,542):1,(182,545):1,(182,546):1,(182,547):1,(182,548):3,(182,563):3,(182,695):3,(183,183):1,(183,426):1,(183,507):1,(183,534):1,(183,549):1,(183,552):1,(183,564):3,(183,696):3,(184,184):1,(184,427):1,(184,508):1,(184,535):1,(184,550):1,(184,553):1,(184,565):3,(184,697):3,(185,185):1,(185,428):1,(185,509):1,(185,536):1,(185,551):1,(185,554):1,(185,555):1,(185,556):1,(185,557):3,(185,566):3,(185,698):3,(186,186):1,(186,429):1,(186,510):1,(186,537):1,(186,558):1,(186,559):1,(186,560):3,(186,699):3,(187,187):1,(187,430):1,(187,511):1,(187,538):1,(187,700):3,(188,188):1,(188,431):1,(188,512):1,(188,539):1,(188,701):3,(189,189):1,(189,432):1,(189,567):1,(189,571):1,(189,594):1,(189,702):3,(190,190):1,(190,433):1,(190,568):1,(190,570):1,(190,576):-1,(190,595):1,(190,703):3,(191,191):1,(191,434):1,(191,569):1,(191,572):1,(191,573):1,(191,574):1,(191,575):3,(191,596):1,(191,704):3,(192,192):1,(192,435):1,(192,576):1,(192,597):1,(192,705):3,(193,193):1,(193,436):1,(193,577):1,(193,598):1,(193,706):3,(194,194):1,(194,437):1,(194,578):1,(194,582):1,(194,583):1,(194,584):3,(194,599):1,(194,707):3,(195,195):1,(195,438):1,(195,582):-1,(195,592):-3,(195,600):1,(195,708):3,(196,196):1,(196,439):1,(196,583):-1,(196,593):-3,(196,601):1,(196,709):3,(197,197):1,(197,440):1,(197,584):-1,(197,592):1,(197,593):1,(197,602):1,(197,710):3,(198,198):1,(198,441):1,(198,576):1,(198,597):1,(198,711):3,(199,199):1,(199,442):1,(199,577):1,(199,598):1,(199,712):3,(200,200):1,(200,443):1,(200,578):1,(200,599):1,(200,600):1,(200,601):1,(200,602):3,(200,713):3,(201,201):1,(201,444):1,(201,579):1,(201,597):-1,(201,603):1,(201,606):1,(201,714):3,(202,202):1,(202,445):1,(202,580):1,(202,598):-1,(202,604):1,(202,607):1,(202,715):3,(203,203):1,(203,446):1,(203,581):1,(203,599):-1,(203,605):1,(203,608):1,(203,609):1,(203,610):1,(203,611):3,(203,716):3,(204,204):1,(204,447):1,(204,582):1,(204,600):-1,(204,619):-3,(204,717):3,(205,205):1,(205,448):1,(205,583):1,(205,601):-1,(205,620):-3,(205,718):3,(206,206):1,(206,449):1,(206,584):1,(206,602):-1,(206,619):1,(206,620):1,(206,719):3,(207,207):1,(207,450):1,(207,585):1,(207,612):1,(207,621):1,(207,625):1,(207,642):3,(207,720):3,(208,208):1,(208,451):1,(208,586):1,(208,613):1,(208,622):1,(208,624):1,(208,643):3,(208,721):3,(209,209):1,(209,452):1,(209,587):1,(209,614):1,(209,623):1,(209,626):1,(209,627):1,(209,628):1,(209,629):3,(209,644):3,(209,722):3,(210,210):1,(210,453):1,(210,588):1,(210,615):1,(210,630):1,(210,633):1,(210,645):3,(210,723):3,(211,211):1,(211,454):1,(211,589):1,(211,616):1,(211,631):1,(211,634):1,(211,646):3,(211,724):3,(212,212):1,(212,455):1,(212,590):1,(212,617):1,(212,632):1,(212,635):1,(212,636):1,(212,637):1,(212,638):3,(212,647):3,(212,725):3,(213,213):1,(213,456):1,(213,591):1,(213,618):1,(213,639):1,(213,640):1,(213,641):3,(213,726):3,(214,214):1,(214,457):1,(214,592):1,(214,619):1,(214,727):3,(215,215):1,(215,458):1,(215,593):1,(215,620):1,(215,728):3,(216,216):1,(216,459):1,(216,648):1,(216,652):1,(216,669):3,(217,217):1,(217,460):1,(217,649):1,(217,651):1,(217,670):3,(218,218):1,(218,461):1,(218,650):1,(218,653):1,(218,654):1,(218,655):1,(218,656):3,(218,671):3,(219,219):1,(219,462):1,(219,657):1,(219,660):1,(219,672):3,(220,220):1,(220,463):1,(220,658):1,(220,661):1,(220,673):3,(221,221):1,(221,464):1,(221,659):1,(221,662):1,(221,663):1,(221,664):1,(221,665):3,(221,674):3,(222,222):1,(222,465):1,(222,666):1,(222,667):1,(222,668):3,(223,223):1,(223,466):1,(224,224):1,(224,467):1,(225,225):1,(225,468):1,(225,679):1,(225,687):-1,(226,226):1,(226,469):1,(226,678):1,(226,688):-1,(227,227):1,(227,470):1,(227,680):1,(227,681):1,(227,682):1,(227,683):3,(227,689):-1,(228,228):1,(228,471):1,(228,678):-1,(228,688):1,(229,229):1,(229,472):1,(229,679):-1,(229,687):1,(230,230):1,(230,473):1,(230,680):-1,(230,689):1,(230,690):1,(230,691):1,(230,692):3,(231,231):1,(231,474):1,(231,681):-1,(231,690):-1,(231,700):-3,(232,232):1,(232,475):1,(232,682):-1,(232,691):-1,(232,701):-3,(233,233):1,(233,476):1,(233,683):-1,(233,692):-1,(233,700):1,(233,701):1,(234,234):1,(234,477):1,(234,705):1,(234,711):-1,(235,235):1,(235,478):1,(235,706):1,(235,712):-1,(236,236):1,(236,479):1,(236,707):1,(236,708):1,(236,709):1,(236,710):3,(236,713):-1,(237,237):1,(237,480):1,(237,705):-1,(237,711):1,(238,238):1,(238,481):1,(238,706):-1,(238,712):1,(239,239):1,(239,482):1,(239,707):-1,(239,713):1,(239,717):1,(239,718):1,(239,719):3,(240,240):1,(240,483):1,(240,708):-1,(240,717):-1,(240,727):-3,(241,241):1,(241,484):1,(241,709):-1,(241,718):-1,(241,728):-3,(242,242):1,(242,485):1,(242,710):-1,(242,719):-1,(242,727):1,(242,728):1}
from sage.homology.matrix_utils import dhsw_snf
matrix = Matrix(ZZ, 243, 729, data)

from time import perf_counter as now
t0 = now()
dhsw_snf(matrix)
t1 = now()
print(f"dhw_snf took {t1 - t0} seconds")

This takes about 0.2 seconds on my machine, but I'm running millions of these, indirectly via some_chain_complex.homology(algorithm='dhsw'). I benchmarked that this dhsw_snf() function takes roughly 80% of the runtime of my program.

Proposed Solution

To speed up these computations, one solution might be to cythonize this module.

Alternatives Considered

A pure-python version of dhws_snf() with types specialized to the types that I'm using and with the all the dynamic methods inlined, might speed things up a bit, but I'm guessing that would be less clean and less performant than cythonizing.

Additional Information

There's already this comment in the file:

https://github.com/sagemath/sage/blob/ffbbea9cb2360340f1c5517b590883fdaf02575c/src/sage/homology/matrix_utils.py#L18-L19

I personally don't have much experience with cythonizing, or the sage philosophy around how/when precisely to do it.

Is there an existing issue for this?

gmou3 commented 3 months ago

I attempted a trivial cythonization with no benefit.

I have the impression that this should be available and optimized from some external package (maybe GAP?). How does algorithm='pari' perform?

gmou3 commented 3 months ago

@jhpalmieri maybe you can provide some insight.

jhpalmieri commented 3 months ago

For benchmarking, I would use %timeit or %time. Here is what I see:

sage: data = {(0,0):1,(0,4):1,(0,12):-1,(0,36):1,(1,1):1,(1,3):1,(1,13):-1,(1,37):1,(2,2):1,(2,5):1,(2,6):1,(2,7):1,(2,8):3,(2,14):-1,(2,38):1,(3,13):1,(3,39):1,(4,12):1,(4,40):1,(5,14):1,(5,15):1,(5,16):1,(5,17):3,(5,41):1,(6,15):-1,(6,25):-3,(6,42):1,(7,16):-1,(7,26):-3,(7,43):1,(8,17):-1,(8,25):1,(8,26):1,(8,44):1,(9,9):1,(9,27):1,(9,30):1,(9,39):-1,(10,10):1,(10,28):1,(10,31):1,(11,11):1,(11,29):1,(11,32):1,(11,33):1,(11,34):1,(11,35):3,(12,12):1,(12,40):1,(13,13):1,(13,39):1,(14,14):1,(14,41):1,(14,42):1,(14,43):1,(14,44):3,(15,15):1,(15,42):-1,(15,52):-3,(16,16):1,(16,43):-1,(16,53):-3,(17,17):1,(17,44):-1,(17,52):1,(17,53):1,(18,18):1,(18,45):1,(18,54):1,(18,58):1,(18,75):3,(19,19):1,(19,46):1,(19,55):1,(19,57):1,(19,76):3,(20,20):1,(20,47):1,(20,56):1,(20,59):1,(20,60):1,(20,61):1,(20,62):3,(20,77):3,(21,21):1,(21,48):1,(21,63):1,(21,66):1,(21,78):3,(22,22):1,(22,49):1,(22,64):1,(22,67):1,(22,79):3,(23,23):1,(23,50):1,(23,65):1,(23,68):1,(23,69):1,(23,70):1,(23,71):3,(23,80):3,(24,24):1,(24,51):1,(24,72):1,(24,73):1,(24,74):3,(25,25):1,(25,52):1,(26,26):1,(26,53):1,(27,82):1,(27,84):1,(27,90):-1,(27,117):1,(27,121):1,(27,252):1,(27,256):1,(27,271):1,(28,85):1,(28,91):-1,(28,118):1,(28,253):1,(29,86):1,(29,87):1,(29,88):1,(29,89):3,(29,92):-1,(29,119):1,(29,254):1,(30,90):1,(30,273):1,(31,91):1,(31,274):1,(32,92):1,(32,96):1,(32,97):1,(32,98):3,(32,275):1,(33,96):-1,(33,106):-3,(33,276):1,(34,97):-1,(34,107):-3,(34,277):1,(35,98):-1,(35,106):1,(35,107):1,(35,278):1,(36,108):1,(36,112):1,(36,120):-1,(36,243):1,(37,109):1,(37,111):1,(37,121):-1,(37,244):1,(38,110):1,(38,113):1,(38,114):1,(38,115):1,(38,116):3,(38,122):-1,(38,245):1,(39,121):1,(39,246):1,(40,120):1,(40,247):1,(41,122):1,(41,123):1,(41,124):1,(41,125):3,(41,248):1,(42,123):-1,(42,133):-3,(42,249):1,(43,124):-1,(43,134):-3,(43,250):1,(44,125):-1,(44,133):1,(44,134):1,(44,251):1,(45,126):1,(45,135):1,(45,139):1,(45,156):3,(45,261):1,(46,127):1,(46,136):1,(46,138):1,(46,157):3,(46,262):1,(47,128):1,(47,137):1,(47,140):1,(47,141):1,(47,142):1,(47,143):3,(47,158):3,(47,263):1,(48,129):1,(48,144):1,(48,147):1,(48,159):3,(48,264):1,(49,130):1,(49,145):1,(49,148):1,(49,160):3,(49,265):1,(50,131):1,(50,146):1,(50,149):1,(50,150):1,(50,151):1,(50,152):3,(50,161):3,(50,266):1,(51,132):1,(51,153):1,(51,154):1,(51,155):3,(51,267):1,(52,133):1,(52,268):1,(53,134):1,(53,269):1,(54,166):1,(54,174):-1,(54,225):-3,(55,165):1,(55,175):-1,(55,226):-3,(56,167):1,(56,168):1,(56,169):1,(56,170):3,(56,176):-1,(56,227):-3,(57,165):-1,(57,175):1,(57,228):-3,(58,166):-1,(58,174):1,(58,229):-3,(59,167):-1,(59,176):1,(59,177):1,(59,178):1,(59,179):3,(59,230):-3,(60,168):-1,(60,177):-1,(60,187):-3,(60,231):-3,(61,169):-1,(61,178):-1,(61,188):-3,(61,232):-3,(62,170):-1,(62,179):-1,(62,187):1,(62,188):1,(62,233):-3,(63,192):1,(63,198):-1,(63,234):-3,(64,193):1,(64,199):-1,(64,235):-3,(65,194):1,(65,195):1,(65,196):1,(65,197):3,(65,200):-1,(65,236):-3,(66,192):-1,(66,198):1,(66,237):-3,(67,193):-1,(67,199):1,(67,238):-3,(68,194):-1,(68,200):1,(68,204):1,(68,205):1,(68,206):3,(68,239):-3,(69,195):-1,(69,204):-1,(69,214):-3,(69,240):-3,(70,196):-1,(70,205):-1,(70,215):-3,(70,241):-3,(71,197):-1,(71,206):-1,(71,214):1,(71,215):1,(71,242):-3,(72,223):-3,(73,224):-3,(74,223):1,(74,224):1,(75,225):1,(75,229):1,(76,226):1,(76,228):1,(77,227):1,(77,230):1,(77,231):1,(77,232):1,(77,233):3,(78,234):1,(78,237):1,(79,235):1,(79,238):1,(80,236):1,(80,239):1,(80,240):1,(80,241):1,(80,242):3,(81,120):1,(81,247):1,(82,121):1,(82,246):1,(83,122):1,(83,248):1,(83,249):1,(83,250):1,(83,251):3,(84,82):1,(84,84):1,(84,117):1,(84,246):-1,(84,252):1,(84,256):1,(84,271):1,(84,273):1,(85,81):1,(85,247):-1,(85,255):1,(85,270):1,(86,83):1,(86,248):-1,(86,257):1,(86,258):1,(86,259):1,(86,260):3,(86,272):1,(87,123):1,(87,249):-1,(87,268):-3,(88,124):1,(88,250):-1,(88,269):-3,(89,125):1,(89,251):-1,(89,268):1,(89,269):1,(90,90):1,(90,273):1,(91,91):1,(91,274):1,(92,92):1,(92,275):1,(92,276):1,(92,277):1,(92,278):3,(93,93):1,(93,273):-1,(93,279):1,(93,282):1,(94,94):1,(94,274):-1,(94,280):1,(94,283):1,(95,95):1,(95,275):-1,(95,281):1,(95,284):1,(95,285):1,(95,286):1,(95,287):3,(96,96):1,(96,276):-1,(96,295):-3,(97,97):1,(97,277):-1,(97,296):-3,(98,98):1,(98,278):-1,(98,295):1,(98,296):1,(99,99):1,(99,288):1,(99,297):1,(99,301):1,(99,318):3,(100,100):1,(100,289):1,(100,298):1,(100,300):1,(100,319):3,(101,101):1,(101,290):1,(101,299):1,(101,302):1,(101,303):1,(101,304):1,(101,305):3,(101,320):3,(102,102):1,(102,291):1,(102,306):1,(102,309):1,(102,321):3,(103,103):1,(103,292):1,(103,307):1,(103,310):1,(103,322):3,(104,104):1,(104,293):1,(104,308):1,(104,311):1,(104,312):1,(104,313):1,(104,314):3,(104,323):3,(105,105):1,(105,294):1,(105,315):1,(105,316):1,(105,317):3,(106,106):1,(106,295):1,(107,107):1,(107,296):1,(108,324):1,(108,328):1,(108,351):1,(109,325):1,(109,327):1,(109,333):-1,(109,352):1,(110,326):1,(110,329):1,(110,330):1,(110,331):1,(110,332):3,(110,353):1,(111,333):1,(111,354):1,(112,334):1,(112,355):1,(113,335):1,(113,339):1,(113,340):1,(113,341):3,(113,356):1,(114,339):-1,(114,349):-3,(114,357):1,(115,340):-1,(115,350):-3,(115,358):1,(116,341):-1,(116,349):1,(116,350):1,(116,359):1,(117,333):1,(117,354):1,(118,334):1,(118,355):1,(119,335):1,(119,356):1,(119,357):1,(119,358):1,(119,359):3,(120,336):1,(120,354):-1,(120,360):1,(120,363):1,(121,337):1,(121,355):-1,(121,361):1,(121,364):1,(122,338):1,(122,356):-1,(122,362):1,(122,365):1,(122,366):1,(122,367):1,(122,368):3,(123,339):1,(123,357):-1,(123,376):-3,(124,340):1,(124,358):-1,(124,377):-3,(125,341):1,(125,359):-1,(125,376):1,(125,377):1,(126,342):1,(126,369):1,(126,378):1,(126,382):1,(126,399):3,(127,343):1,(127,370):1,(127,379):1,(127,381):1,(127,400):3,(128,344):1,(128,371):1,(128,380):1,(128,383):1,(128,384):1,(128,385):1,(128,386):3,(128,401):3,(129,345):1,(129,372):1,(129,387):1,(129,390):1,(129,402):3,(130,346):1,(130,373):1,(130,388):1,(130,391):1,(130,403):3,(131,347):1,(131,374):1,(131,389):1,(131,392):1,(131,393):1,(131,394):1,(131,395):3,(131,404):3,(132,348):1,(132,375):1,(132,396):1,(132,397):1,(132,398):3,(133,349):1,(133,376):1,(134,350):1,(134,377):1,(135,409):1,(135,417):-1,(135,468):-3,(136,408):1,(136,418):-1,(136,469):-3,(137,410):1,(137,411):1,(137,412):1,(137,413):3,(137,419):-1,(137,470):-3,(138,408):-1,(138,418):1,(138,471):-3,(139,409):-1,(139,417):1,(139,472):-3,(140,410):-1,(140,419):1,(140,420):1,(140,421):1,(140,422):3,(140,473):-3,(141,411):-1,(141,420):-1,(141,430):-3,(141,474):-3,(142,412):-1,(142,421):-1,(142,431):-3,(142,475):-3,(143,413):-1,(143,422):-1,(143,430):1,(143,431):1,(143,476):-3,(144,435):1,(144,441):-1,(144,477):-3,(145,436):1,(145,442):-1,(145,478):-3,(146,437):1,(146,438):1,(146,439):1,(146,440):3,(146,443):-1,(146,479):-3,(147,435):-1,(147,441):1,(147,480):-3,(148,436):-1,(148,442):1,(148,481):-3,(149,437):-1,(149,443):1,(149,447):1,(149,448):1,(149,449):3,(149,482):-3,(150,438):-1,(150,447):-1,(150,457):-3,(150,483):-3,(151,439):-1,(151,448):-1,(151,458):-3,(151,484):-3,(152,440):-1,(152,449):-1,(152,457):1,(152,458):1,(152,485):-3,(153,466):-3,(154,467):-3,(155,466):1,(155,467):1,(156,468):1,(156,472):1,(157,469):1,(157,471):1,(158,470):1,(158,473):1,(158,474):1,(158,475):1,(158,476):3,(159,477):1,(159,480):1,(160,478):1,(160,481):1,(161,479):1,(161,482):1,(161,483):1,(161,484):1,(161,485):3,(162,162):1,(162,405):1,(162,486):1,(162,490):1,(162,498):-1,(162,522):1,(162,675):3,(163,163):1,(163,406):1,(163,487):1,(163,489):1,(163,499):-1,(163,523):1,(163,676):3,(164,164):1,(164,407):1,(164,488):1,(164,491):1,(164,492):1,(164,493):1,(164,494):3,(164,500):-1,(164,524):1,(164,677):3,(165,165):1,(165,408):1,(165,499):1,(165,525):1,(165,678):3,(166,166):1,(166,409):1,(166,498):1,(166,526):1,(166,679):3,(167,167):1,(167,410):1,(167,500):1,(167,501):1,(167,502):1,(167,503):3,(167,527):1,(167,680):3,(168,168):1,(168,411):1,(168,501):-1,(168,511):-3,(168,528):1,(168,681):3,(169,169):1,(169,412):1,(169,502):-1,(169,512):-3,(169,529):1,(169,682):3,(170,170):1,(170,413):1,(170,503):-1,(170,511):1,(170,512):1,(170,530):1,(170,683):3,(171,171):1,(171,414):1,(171,495):1,(171,513):1,(171,516):1,(171,525):-1,(171,684):3,(172,172):1,(172,415):1,(172,496):1,(172,514):1,(172,517):1,(172,685):3,(173,173):1,(173,416):1,(173,497):1,(173,515):1,(173,518):1,(173,519):1,(173,520):1,(173,521):3,(173,686):3,(174,174):1,(174,417):1,(174,498):1,(174,526):1,(174,687):3,(175,175):1,(175,418):1,(175,499):1,(175,525):1,(175,688):3,(176,176):1,(176,419):1,(176,500):1,(176,527):1,(176,528):1,(176,529):1,(176,530):3,(176,689):3,(177,177):1,(177,420):1,(177,501):1,(177,528):-1,(177,538):-3,(177,690):3,(178,178):1,(178,421):1,(178,502):1,(178,529):-1,(178,539):-3,(178,691):3,(179,179):1,(179,422):1,(179,503):1,(179,530):-1,(179,538):1,(179,539):1,(179,692):3,(180,180):1,(180,423):1,(180,504):1,(180,531):1,(180,540):1,(180,544):1,(180,561):3,(180,693):3,(181,181):1,(181,424):1,(181,505):1,(181,532):1,(181,541):1,(181,543):1,(181,562):3,(181,694):3,(182,182):1,(182,425):1,(182,506):1,(182,533):1,(182,542):1,(182,545):1,(182,546):1,(182,547):1,(182,548):3,(182,563):3,(182,695):3,(183,183):1,(183,426):1,(183,507):1,(183,534):1,(183,549):1,(183,552):1,(183,564):3,(183,696):3,(184,184):1,(184,427):1,(184,508):1,(184,535):1,(184,550):1,(184,553):1,(184,565):3,(184,697):3,(185,185):1,(185,428):1,(185,509):1,(185,536):1,(185,551):1,(185,554):1,(185,555):1,(185,556):1,(185,557):3,(185,566):3,(185,698):3,(186,186):1,(186,429):1,(186,510):1,(186,537):1,(186,558):1,(186,559):1,(186,560):3,(186,699):3,(187,187):1,(187,430):1,(187,511):1,(187,538):1,(187,700):3,(188,188):1,(188,431):1,(188,512):1,(188,539):1,(188,701):3,(189,189):1,(189,432):1,(189,567):1,(189,571):1,(189,594):1,(189,702):3,(190,190):1,(190,433):1,(190,568):1,(190,570):1,(190,576):-1,(190,595):1,(190,703):3,(191,191):1,(191,434):1,(191,569):1,(191,572):1,(191,573):1,(191,574):1,(191,575):3,(191,596):1,(191,704):3,(192,192):1,(192,435):1,(192,576):1,(192,597):1,(192,705):3,(193,193):1,(193,436):1,(193,577):1,(193,598):1,(193,706):3,(194,194):1,(194,437):1,(194,578):1,(194,582):1,(194,583):1,(194,584):3,(194,599):1,(194,707):3,(195,195):1,(195,438):1,(195,582):-1,(195,592):-3,(195,600):1,(195,708):3,(196,196):1,(196,439):1,(196,583):-1,(196,593):-3,(196,601):1,(196,709):3,(197,197):1,(197,440):1,(197,584):-1,(197,592):1,(197,593):1,(197,602):1,(197,710):3,(198,198):1,(198,441):1,(198,576):1,(198,597):1,(198,711):3,(199,199):1,(199,442):1,(199,577):1,(199,598):1,(199,712):3,(200,200):1,(200,443):1,(200,578):1,(200,599):1,(200,600):1,(200,601):1,(200,602):3,(200,713):3,(201,201):1,(201,444):1,(201,579):1,(201,597):-1,(201,603):1,(201,606):1,(201,714):3,(202,202):1,(202,445):1,(202,580):1,(202,598):-1,(202,604):1,(202,607):1,(202,715):3,(203,203):1,(203,446):1,(203,581):1,(203,599):-1,(203,605):1,(203,608):1,(203,609):1,(203,610):1,(203,611):3,(203,716):3,(204,204):1,(204,447):1,(204,582):1,(204,600):-1,(204,619):-3,(204,717):3,(205,205):1,(205,448):1,(205,583):1,(205,601):-1,(205,620):-3,(205,718):3,(206,206):1,(206,449):1,(206,584):1,(206,602):-1,(206,619):1,(206,620):1,(206,719):3,(207,207):1,(207,450):1,(207,585):1,(207,612):1,(207,621):1,(207,625):1,(207,642):3,(207,720):3,(208,208):1,(208,451):1,(208,586):1,(208,613):1,(208,622):1,(208,624):1,(208,643):3,(208,721):3,(209,209):1,(209,452):1,(209,587):1,(209,614):1,(209,623):1,(209,626):1,(209,627):1,(209,628):1,(209,629):3,(209,644):3,(209,722):3,(210,210):1,(210,453):1,(210,588):1,(210,615):1,(210,630):1,(210,633):1,(210,645):3,(210,723):3,(211,211):1,(211,454):1,(211,589):1,(211,616):1,(211,631):1,(211,634):1,(211,646):3,(211,724):3,(212,212):1,(212,455):1,(212,590):1,(212,617):1,(212,632):1,(212,635):1,(212,636):1,(212,637):1,(212,638):3,(212,647):3,(212,725):3,(213,213):1,(213,456):1,(213,591):1,(213,618):1,(213,639):1,(213,640):1,(213,641):3,(213,726):3,(214,214):1,(214,457):1,(214,592):1,(214,619):1,(214,727):3,(215,215):1,(215,458):1,(215,593):1,(215,620):1,(215,728):3,(216,216):1,(216,459):1,(216,648):1,(216,652):1,(216,669):3,(217,217):1,(217,460):1,(217,649):1,(217,651):1,(217,670):3,(218,218):1,(218,461):1,(218,650):1,(218,653):1,(218,654):1,(218,655):1,(218,656):3,(218,671):3,(219,219):1,(219,462):1,(219,657):1,(219,660):1,(219,672):3,(220,220):1,(220,463):1,(220,658):1,(220,661):1,(220,673):3,(221,221):1,(221,464):1,(221,659):1,(221,662):1,(221,663):1,(221,664):1,(221,665):3,(221,674):3,(222,222):1,(222,465):1,(222,666):1,(222,667):1,(222,668):3,(223,223):1,(223,466):1,(224,224):1,(224,467):1,(225,225):1,(225,468):1,(225,679):1,(225,687):-1,(226,226):1,(226,469):1,(226,678):1,(226,688):-1,(227,227):1,(227,470):1,(227,680):1,(227,681):1,(227,682):1,(227,683):3,(227,689):-1,(228,228):1,(228,471):1,(228,678):-1,(228,688):1,(229,229):1,(229,472):1,(229,679):-1,(229,687):1,(230,230):1,(230,473):1,(230,680):-1,(230,689):1,(230,690):1,(230,691):1,(230,692):3,(231,231):1,(231,474):1,(231,681):-1,(231,690):-1,(231,700):-3,(232,232):1,(232,475):1,(232,682):-1,(232,691):-1,(232,701):-3,(233,233):1,(233,476):1,(233,683):-1,(233,692):-1,(233,700):1,(233,701):1,(234,234):1,(234,477):1,(234,705):1,(234,711):-1,(235,235):1,(235,478):1,(235,706):1,(235,712):-1,(236,236):1,(236,479):1,(236,707):1,(236,708):1,(236,709):1,(236,710):3,(236,713):-1,(237,237):1,(237,480):1,(237,705):-1,(237,711):1,(238,238):1,(238,481):1,(238,706):-1,(238,712):1,(239,239):1,(239,482):1,(239,707):-1,(239,713):1,(239,717):1,(239,718):1,(239,719):3,(240,240):1,(240,483):1,(240,708):-1,(240,717):-1,(240,727):-3,(241,241):1,(241,484):1,(241,709):-1,(241,718):-1,(241,728):-3,(242,242):1,(242,485):1,(242,710):-1,(242,719):-1,(242,727):1,(242,728):1}
sage: matrix = Matrix(ZZ, 243, 729, data)
sage: C = ChainComplex({1: matrix})
sage: %timeit C.homology(algorithm='pari')
350 ms ± 1.72 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit C.homology(algorithm='dhsw')
371 ms ± 3.13 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

There is a little bit of caching going on, so a single timing may be more informative than %timeit, which runs the same thing multiple times. %time just runs it once:

sage: C = ChainComplex({1: matrix})
sage: %time C.homology(algorithm='dhsw')
CPU times: user 394 ms, sys: 9.41 ms, total: 403 ms
Wall time: 403 ms
{1: Z^545, 2: Z^59 x C3}
sage: C = ChainComplex({1: matrix})
sage: %time C.homology(algorithm='pari')
CPU times: user 360 ms, sys: 8.78 ms, total: 369 ms
Wall time: 369 ms
{1: Z^545, 2: Z^59 x C3}