Re: integral homology

Thanks, Surely and Watson. As either of you might have guessed, my context is integral homology of Bianchi orbifolds, hyperbolic 3 space modulo GL2 or SL2 if the ring of integers of an imaginary quadratic field. The matrix is very sparse but entries might be bigger than 1, eg the boundary if a triangle could be 3 times the same edge.

I don't need the basis now, just the structure.

As I said in my second post, all I need now is the SNF of one matrix. It does happen that large primes turn up 'at random' which is one point of doing the computation.

In a preprint of about a year ago, Gunnels, Yasaki et all did this for all fields of absolute discriminant upto 2100 for GL2 and 1250 for SL2. I have already independently verified all their results, with SL2 also up to 2100, and am currently seeing how far I can take it. Right now I have done most fields in the range 2100-2300.

John

On Thu, 21 Nov 2024, 10:22 Aurel Page, <aurel.page@normalesup.org> wrote:

Dear John,

There are several questions that influence the answer:
1/ do you only want the structure of the homology or also a basis?
2/ are your matrices sparse?

If you want a basis, the way I have implemented it is a variant of what you proposed:

Z = matker(D1); \\Q-kernel
Z = matrixqz(Z,-2); \\Z-kernel
if(n>0 && matsize(Z)[1]!=0,
D2 = matconcat([D2,vectorv(n)]); \\trick for matrices with 0 columns :-(
);
B = matsolve(Z,D2);
matsnf(B,4);

However, if you only want the structure, you don't need to compute the kernel. The structure of the torsion in the homology will be directly given by the SNF of the second differential, while the rank of the homology is simply the dimension of the middle space minus the sum of the ranks of the two differentials, so you only need one SNF and one rank computation, no integer kernel.

About sparseness: I have been playing around with an algorithm for computing homology of a complex with sparse matrices with most coefficients +-1 (the core algorithm is in the branch aurel-amt, but there is no documentation and it is still work in progress). It has been working well on my examples. For instance, the homology of an arithmetic hyperbolic 5-orbifold:
dimensions: [0, 15151, 251927, 1079420, 1887244, 1462440, 417840, 0]
number of nonzero coefs: [0, 503854, 3509856, 8426440, 8356800, 2924880, 0]
The structure of the entire homology over Z was computed in 5 minutes with 6.4GB of memory (single core on my laptop).

Best,
Aurel

On 18/11/2024 10:02, John Cremona wrote:

Well, I no longer need an answer to my question since it turned out that in my specific application, the matrix A10 was so simply structured that I could simply replace all of steps 1-3 by a new preliminary step which just deleted certain rows from A21 without having to do the HNF or matrix inversion steps.

It would still be nice to know if there is a better way to do the general case, For example, in the HNF computation of H and U from A10, I presume that a series of column operations are applied to A10, with U recording those operations; and then it would be easy to compute U^{-1} at the same time step by step, I think. In some of the examples I was having difficulty with where the dimensions n0, n1, n2 are 36,14219, and 24599, I was running out of memory even after setting PARISIZEMAX to 50000000000, i.e. 50G, and this occurred while in _ZM_inv_worker() so while inverting U.

John

On Fri, 15 Nov 2024 at 15:03, John Cremona <john.cremona@gmail.com> wrote:

I am computing some integral homology in a C++ program using libpari, and while what I have works fine it is possible that there is a better (simpler or faster) way to do this, possibly even a built-in function which I have not found which does what I want more simply.

I have Z-linear maps maps Z^n2 -> Z^n1 -> Z^n0 whose composite is 0 with integer matrices A10 (size n0 x n1) and A21 (size n1 x n2), so acting on column vectors on the right, and A10*A21=0. All I want is the abelian group structure of ker(A10)/im(A21). A rough sketch of what I do is this:

1. Find the HNF of A10, say H = A10*U with U in GL(n1,Z) representing a change of basis for the module in the middle.

2. Compute M = U^{-1}*A21, the new matrix of the second map.

3. Drop the last r rows of M, where r is the rank of H (also of A10).

4. Return the SNF of M.

Is there a better way?

John