[GAP Forum] running with grape package under windows 64

Bailey, Robert F. rbailey at grenfell.mun.ca
Thu Jul 7 21:54:43 BST 2016


Dear R.N.,

Some suggestions:

If you are using Linux, you can override GAP's default memory allocation when you launch it (see http://www.gap-system.org/Faq/faq.html#6.2 for a discussion of how to handle memory problems).

However, if the size of the adjacency matrix is the issue, you should consider an alternative way of constructing the graph in GRAPE.  In particular, as you say, because the graph is bipartite its adjacency matrix will have two massive all-zero blocks.  One idea would be to rewrite the adjacency function (i.e. replace the "function(x,y) return A[x][y]=1; end" part) to be based on entries of H rather than A: the edges of your graph are determined precisely from where the entries of H are 1.  That way, you avoid the need to construct A.

If the graph is really sparse, just listing all edges may possibly take up less memory than the matrix H anyway, and the adjacency function would only need to return [x,y] as an edge if [x,y] is in your list.

Regards,
Robert Bailey.

==============================
Dr. Robert Bailey
Division of Science (Mathematics)
Grenfell Campus
Memorial University of Newfoundland
Corner Brook, NL A2H 6P9, Canada

Office: AS 3022
Phone: +1 (709) 637-6293
Web: http://www2.grenfell.mun.ca/rbailey/

-----Original Message-----
From: forum-bounces at gap-system.org [mailto:forum-bounces at gap-system.org] On Behalf Of R.N. Tsai
Sent: July-07-16 5:28 PM
To: Alexander Konovalov <alexander.konovalov at st-andrews.ac.uk>
Cc: GAP Forum <forum at gap-system.org>
Subject: Re: [GAP Forum] running with grape package under windows 64

Dear Alexander and forum,
Thanks for your suggestion; it did in fact work, so now grape works with both gap32 and gap64.Performance under windows seems to get much worse as the size of the graph gets bigger. I movedto linux64 and the performance is much better there until gap runs out of memory.
I have some followup questions regarding memory management in gap and graph calculations with grapeor other packages : (the moderators of the forum can move to another topic if they think that's better).
(1)I'm using grape to calculate the girth of large graphs. These graphs are the "Tanner graphs" of low   density parity check (LDPC) codes. These type of graphs are frequently used in coding theory to analyze   the error correcting capability of the code. In particular, the length of the shortest cycles (girth) and   number of such cycles is important. I looked in the guava package which has some constructs for LDPC codes   ("QCLDPCCodeFromGroup" for example) but nothing specific for Tanner graphs.....
(2)Tanner graphs are easily described : take the parity check matrix of the code "H" of size mxn and form   A=(m+n)x(m+n) matrix defined as A=[0,H],[H',0]]; here H' is transpose. H is large (say 10K x 10K) binary   matrix (0,1 entries) but very sparse (percentage of 1's is <2%). Here's how I get "A" from "H" :
  dim:=DimensionsMat(H);m:=dim[1];n:=dim[2];  T:=H;  T1:=List([1..m],x->Concatenation(0*[1..m],T[x]));  T:=TransposedMat(H);
  T2:=List([1..n],x->Concatenation(T[x],0*[1..n]));  A:=Concatenation(T1,T2);
  This results in a large sparse matrix "A" which is >99% 0's. Is there a better way to define it?
(3)With the adjacency matrix "A" I define a graph "gamma" using grape's documentation :
   gamma:=Graph(Group(()),[1..n+m],OnPoints,function(x,y)return A[x][y]=1;end,true);
   by the construction of "A", it is known to be bipartite with the partition of vertices well   known, namely [1..m] and [m+1..m+n] but I don't know how to use this extra knowledge to help   grape work with the graph more efficiently.
(4)I get the girth through girth:=Girth(gamma); I would also like to get the number of cycles   with length=girth but I don't know how that's done.
(5)Finally, is there a way to "clear memory" within gap? I noticed that if I process H1 then   try to process H2 in the same gap session gap reports that the memory limit was exceeded, but   if I exit gap and start it again with H2, then it works. I don't save anything from the calculations   (I just print out the results) so I don't know what's using the memory. Here's an example :   gap>Process(H1); #finishes ok; no variables saved...   gap>Process(H2); #comes back with memory problem   if I exit gap and start again   gap>Process(H2); #now this works without memory problem.
Thanks for your help.
R.N.

      From: Alexander Konovalov <alexander.konovalov at st-andrews.ac.uk>
 To: R.N. Tsai <r_n_tsai at yahoo.com>
Cc: GAP Forum <forum at gap-system.org>
 Sent: Thursday, July 7, 2016 2:46 AM
 Subject: Re: [GAP Forum] running with grape package under windows 64


> On 7 Jul 2016, at 07:19, R.N. Tsai <r_n_tsai at yahoo.com> wrote:
>
> Dear GAP forum,I'm doing some calculations with gap+grape package under windows. Things work fine with the gap32 version, but grape doesn't seem to workwith gap64. The graphs I'm working with are very large and I would liketo run gap64 with 16GBytes memory. Is there a 64 bit version of grapeavailable somewhere?Thanks,R.N.

Dear R.N.,

Grape uses a stand-alone binary, so it can interact with 64-bit GAP version
even being 32-bit application. The problem is that GAP looks for the binary
for GRAPE using the architecture-dependent path which it assumes to be
'x86_64-unknown-cygwin-gcc-default64'. As a quick workaround, I suggest to
try this: in the 'bin' directory of your GRAPE installation, you should
have the directory 'i686-pc-cygwin-gcc-default32'. Copy it to the directory
'x86_64-unknown-cygwin-gcc-default64' and try to load GRAPE from 64-bit
version of GAP now. Please let me know if this helps!

Best wishes
Alexander



_______________________________________________
Forum mailing list
Forum at mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
This electronic communication is governed by the terms and conditions at http://www.mun.ca/cc/policies/electronic_communications_disclaimer_2011.php.


More information about the Forum mailing list