How to improve sparse array indexed assignment in MATLAB?

2022 3 2
2 个回答
更新时间：2022 3 7
2 次查看（30 天）

0 个投票

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');

2 个评论
显示 无 隐藏 无

David Hill
David Hill 2022-3-2
In the example you create a 16x18 sparse array. Do not understand where to index your -1/+1 values into.
Nadatimuj
Nadatimuj 2022-3-3
编辑：Nadatimuj 2022-3-3
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

David Hill
David Hill 2022-3-3

1 个投票

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(:);

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Nadatimuj
Nadatimuj 2022-3-3
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
David Hill 2022-3-3
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
Nadatimuj 2022-3-3
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
David Hill 2022-3-3
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
Nadatimuj 2022-3-5
编辑：Nadatimuj 2022-3-7
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.

请先登录，再进行评论。

Matt J
Matt J 2022-3-3
编辑：Matt J 2022-3-3
Ran in:

0 个投票

Ran in:
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)

3 个评论
显示 1更早的评论 隐藏 1更早的评论

Nadatimuj
Nadatimuj 2022-3-3
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
Matt J 2022-3-3
编辑：Matt J 2022-3-3
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
Nadatimuj 2022-3-5
@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.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Logical 的更多信息

产品

版本

R2021b

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by