How to improve sparse array indexed assignment in MATLAB?

Hi, how can I improve indexed assignment to a sparse matrix? Please refer to line 29 and 31 of the attached code that is simply trying to read the attached txt file and put +1 for positive values and -1 for negative values and generate a matrix. How can I speed it up? Thanks.

An example function call will be: A= cnf_to_A('quinn.txt');

[David Hill]

In the example you create a 16x18 sparse array. Do not understand where to index your -1/+1 values into.

[Nadatimuj]

sorry for not being clearer. This is a SAT solver CNF format.

The following lines are just comments:

c quinn.cnf

c

p cnf 16 18

This last line indicates the size of the matrix 18 by 16

Then the follwoing lines correspond to the matrix rows:

1 2 0

-2 -4 0

3 4 0

-4 -5 0

5 -6 0

6 -7 0

6 7 0

7 -16 0

8 -9 0

-8 -14 0

9 10 0

9 -10 0

-10 -11 0

10 12 0

11 12 0

13 14 0

14 -15 0

15 16 0

where, the 0 at the end of each line indicates end of line. Take the 2nd line as an example, -2 -4 0 which indicates that the 2nd and 4th element of the 2nd row should be -1.

another example is the 17th line, where 14 -15 0 means the 14th and 15th element of 17th row should be +1 and -1.

Thanks for your help.

Answer 1

[David Hill]

s=readmatrix('quinn.txt','Range','C3:D3');
r=readmatrix('quinn.txt','NumHeaderLines',3);
X=sparse(s(2),s(1));
ra=abs(r(:,1:2));
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*[1 1];
X(linIndex(:))=rv(:);

[Nadatimuj]

Thank you very much, this is wonderful. But can we generalize that?

For example, here is another example 'irregular.txt' file attached, where the row elements are irregular. Also, we don't know exactly which line contains the dimension but we know that the line starts with 'p'. Actually, the reason I wanted to improve speed is I will have to handle much larger files like these. I am sorry if I am wasting your time but I greatly appreaciate your help. Thanks.

[David Hill]

fid=fopen('quinn.txt');
count=1;
while ~feof(fid)
    tline = fgetl(fid);
    tline = strtrim(tline);
    if (tline(1)=='p' || tline(1)=='P')
        fclose(fid);
        break;
    end
    count=count+1;
end
    

s=readmatrix('quinn.txt','Range',sprintf('C%d:D%d',count,count));
r=readmatrix('quinn.txt','NumHeaderLines',count);
X=sparse(s(2),s(1));
ra=abs(r(:,1:2));
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*[1 1];
X(linIndex(:))=rv(:);

[Nadatimuj]

Thanks again, it works fine with the quinn. We are converging. However, I think you have missed the irregular.txt file that I have attached. Can we have irregular matrix in MATLAB? probably no?

Note: What I am trying to generate is a 'Boolean Satisfiability DIMACS/ CNF' to 'MATLAB Adjacency Matrix' Reader file. The CNF file format is also called DIMACS which is widely used in SAT competitions and SAT benchmarking and can be a very useful MATLAB tool.

https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/SATLINK____DIMACS#:~:text=DIMACS%20format%20is%20a%20standard,input%20format%20is%20as%20follows.

https://satcompetition.github.io/2020/downloads.html

https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html

p cnf 8 12 
c Factors encoded in variables 1-4 and 5-8
c Target number: 143
3 2 0
2 6 0
1 0
-3 -2 0
8 0
-2 -7 -6 0
4 0
-3 -2 -6 0
5 0
-2 -6 0
-3 -7 0
3 7 0

[David Hill]

Try this:

File='irregular.txt';

fid=fopen(File);
count=1;
while ~feof(fid)
    tline = fgetl(fid);
    tline = strtrim(tline);
    if (tline(1)=='p' || tline(1)=='P')
        c=count;
    elseif (tline(1)=='c' || tline(1)=='C')
        cc=count;
    end
    count=count+1;
end
fclose(fid);
    
s=readmatrix(File,'Range',sprintf('C%d:D%d',c,c));
r=readmatrix(File,'NumHeaderLines',max(c,cc));
X=sparse(s(2),s(1));
ra=abs(r);
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*ones(1,size(ra,2));
linIndex=linIndex(linIndex>0);
rv=rv(~isnan(r)&r~=0);
X(linIndex)=rv;

[Nadatimuj]

This is an edited response: It still takes long time (~140 s) for the last line for ULTRA large instances (please see attched competion.zip file for example which is a 2020 SAT competition instance). My original version took 127s. I think as @Matt J suggested, we must create the sparse matrix from the scratch with indices, otherwise it is not making it faster.

One minor comment, someone should initialize cc= 0 because come CNF files do not have comment lines.

function [A] = cnf_to_A(cnffile, varargin)

fid=fopen(cnffile);
count=1;
cc=0;
while ~feof(fid)
    tline = fgetl(fid);
    tline = strtrim(tline);
    if (tline(1)=='p' || tline(1)=='P')
        c=count;
    elseif (tline(1)=='c' || tline(1)=='C')
        cc=count;
    end
    count=count+1;
end
fclose(fid);
    
s=readmatrix(cnffile,'FileType','text','Range',sprintf('C%d:D%d',c,c));
r=readmatrix(cnffile,'FileType','text','NumHeaderLines',max(c,cc));
A=sparse(s(2),s(1));
ra=abs(r);
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*ones(1,size(ra,2));
linIndex=linIndex(linIndex>0);
rv=rv(~isnan(r)&r~=0);
A(linIndex)=rv;

end

Thanks.

Answer 2

[Matt J]

Assigning into an existing sparse matrix is fundamentally a slow thing. If you are creating a matrix from scratch, use the sparse() command, not assignment:

Jdata=[
  1    2  0
 -2   -4  0
  3    4  0
 -4   -5  0
  5   -6  0
  6   -7  0
  6    7  0
  7  -16  0
  8   -9  0
 -8  -14  0
  9   10  0
  9  -10  0
-10  -11  0
 10   12  0
 11   12  0
 13   14  0
 14  -15  0
 15   16  0];

N=size(Jdata,1);

rows=(1:N)'; 

I=[rows,rows];
J=abs(Jdata(:,1:2));
S=sign(Jdata(:,1:2));


A=sparse(I,J,S);

spy(A)

[Nadatimuj]

Thank you very much. This code is giving me error:

Error using sparse
Vectors must be the same length.

Also, as I am discussing with @David Hill above, the data is not always regular like this, it can be irregular too:

p cnf 8 12 
c Factors encoded in variables 1-4 and 5-8
c Target number: 143
3 2 0
2 6 0
1 0
-3 -2 0
8 0
-2 -7 -6 0
4 0
-3 -2 -6 0
5 0
-2 -6 0
-3 -7 0
3 7 0

[Matt J]

Thank you very much. This code is giving me error:

I fixed it.

Also, as I am discussing with @David Hill above, the data is not always regular like this, it can be irregular too:

That's not really an important aspect. You would need to build I,J,S differently in the irregular case, but the point about avoiding assignment is the same.

[Nadatimuj]

@Matt J Yes now I understand that the real point is to have the row and column indices and create the sparse matrix later. Thank you very much.