How to fill up a huge/very large matrix, with elements from another matrix in a time efficient way?

조회 수: 33 (최근 30일)
Hi there,
I am doing some calculations for some graph/network with vertices that have certain connections/edges to each other.
My goal is to set-up a very large matrices with dimensions ranging from roughly 90000x300(works but already takes up ~4.6 seconds to create) up to 9,000,000 (9mln)x30000 elements in an efficient way, such that is does not take forever to fill up the matrix. Most elements are, however, zeros so I tried using sparse matrices, but sparse matrices are not suitable if you want to fill them up element-wise.
The size of the matrices depend on a discretization parameter(delta) that I choose, I need to make it as small as possible, down to 10^-4. My function is now as follows(I use Hungarian notation):
function mZ_j = createZ_j(iN, iP, iD_j, mX, vPA)
% Function that creates matrix Z_j.
% Dimensions: (n-p)x(p*d_j)+1, d_j can go up to 6, but is 2 on average
% input/starting parametes are:
% delta = 0.0001, s=0.5, T=900(15 min in seconds), d_j=2
iRows = iN-iP; % n:= T/delta, p:=s/delta
iCol = (iP*iD_j);
mZ_j = zeros(iRows,iCol); % (n-p)x(p*d_j) matrix
mX_j = mX(:,vPA); % matrix were elements will be taken from, vPA(size iD_j) has the column indexes
p = iP+1; % indicator for each row; it is an autoregressive process and each row you regress on p lags, but every row you take one next step in time
for i=1:iRows
for j=1:iP
iCStart = ((j-1)*iD_j)+1; iCEnd = j*iD_j;
mZ_j(i,iCStart:iCEnd) = mX_j(p-j,:);
end
p = p+1;
end
Does anyone see or know how I can assign the elements from mX_j more efficiently to mZ_j? The operations themselve do not take a lot time, it is just the amount of iterations that it has to do.
Thanks!
  댓글 수: 6
Jeroen
Jeroen 2019년 6월 27일
  • iN~T/delta=9000000(9m) and mX is iNx6. So yes they are related
Yes, I understand that it will take up a lot of memory and that I therefore need to use sparse matrices. But I do not now how to, I never worked with sparse matrices
Walter Roberson
Walter Roberson 2019년 6월 27일
Inverse of a sparse matrix is typically dense. Inverse of a nonsquare matrix is not defined. But perhaps you are doing something like A*A' that will be square but possibly large.
Inverse of a large matrix that is not just 0 and 1 will typically have terrible condition number and give numeric garbage. Don't use inv unless you are forced to by external requirements. Use other techniques such as \ instead.

댓글을 달려면 로그인하십시오.

채택된 답변

Steven Lord
Steven Lord 2019년 6월 26일
Your 90000-by-300 matrix isn't too big. If it's a full real double precision matrix, it'll take up a couple hundred MB of contiguous space.
Your 9 million by 30000 matrix better be sparse or you will need a computer with a very large amount of memory. One copy of a full real matrix that size will require just shy of 2 TB of contiguous space.
Rather than filling the sparse matrix one element at a time, build three vectors: one of row indices, one of column indices, and one of data values. Call sparse once at the very end to assemble the matrix from those three vectors. See the "Sparse Matrix of Nonzeros with Specified Size" example on the documentation page for the sparse function for an illustration of the technique. The "Accumulate Values into Sparse Matrix" example may also be of interest.
  댓글 수: 6
Steven Lord
Steven Lord 2019년 6월 27일
Here's a simple sparse example that you can use to try to determine how to build your sparse matrix. I'm going to build this matrix:
>> A = [1 0 0 0 6; 0 2 0 7 0; 0 0 11 0 0; 0 9 0 4 0; 10 0 0 0 5]
A =
1 0 0 0 6
0 2 0 7 0
0 0 11 0 0
0 9 0 4 0
10 0 0 0 5
First, for the main diagonal the elements are in rows 1:5, columns 1:5. The values are 1:5. Yes, I know the center element is 11 not 3. Wait for the next step.
v = (1:5).';
mainDiagonal = [v, v, v];
For the antidiagonal, the elements are in rows 1:5, columns 5:-1:1. The values are 6:10. When you specify multiple values for the same row and column indices in your vector, sparse accumulates them. So the 3 in position (3, 3) from the main diagonal and the 8 in position (3, 3) from the antidiagonal will add up to 11. [It's almost like I designed the example that way ;)]
antiDiagonal = [v, flip(v), v+5];
Let's assemble those into a matrix whose first column is row indices, whose second is column indices, and whose third is values.
allElements = [mainDiagonal; antiDiagonal];
Finally, build and compare
S = sparse(allElements(:, 1), allElements(:, 2), allElements(:, 3))
full(S)
In this case, S is dense enough (9/25 or 36% of the elements are nonzero) that it actually takes up more memory than A does. If you were to scale this up to something a bit larger:
v2 = (1:99).';
S2 = sparse([v2; v2], [v2; flip(v2)], [v2; v2+99]);
A2 = full(S2);
whos A2 S2
You'll see you save a bunch of memory (and typing; specifying all the 0's in A2 like I did in A would have been quite tedious and prone to misplacement.) In constructing S2, I needed to build three full matrices instead of just the one that I would have needed to build A2. However, the full matrices I used to build S2 are each 198-by-1 (597 elements total) while the full matrix A2 is 99-by-99 (9801 elements.) I used an odd size so the center element accumulates values from both the main and anti diagonals to demonstrate that capability.

댓글을 달려면 로그인하십시오.

추가 답변 (0개)

카테고리

Help CenterFile Exchange에서 Sparse Matrices에 대해 자세히 알아보기

제품


릴리스

R2019a

Community Treasure Hunt

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

Start Hunting!

Translated by