CODEWITHSUNDEEP
matlabsparse-matrixmatrix-multiplication
Marco
Marco

Reputation: 61

Computing only necessary rows of a matrix product

Suppose I have a large (but possibly sparse) matrix A, which is K-by-K in dimension. I have another K-by-1 vector, b.

Let Ax=b. If I am only interested in the first n rows, where n < K, of x, then one way of dealing with this in MATLAB is to calculate x=A\b and take the first n elements.

If the dimension K is so large that the entire computation infeasible, is there any other way to get these elements?

Upvotes: 4

Views: 92

Answers (2)

Florian
Florian

Reputation: 1824

Just an idea: You could try to use Block Matrix inversion: if you block your matrix into A = [A11, A12;A21, A22], where A11 is n x n, you can compute the blocks of its inverse B = inv(A) = [B11, B12;B21, B22] via Block Matrix Inversion. There are different versions of it, you could use the one where the Schur complement you use is only of size n x n. I'm not quite sure whether it is possible to avoid any inversion that scales with K, but you could look into it.

Your solution is then x(1:n) = [B11, B12]*b. It saves you from ever computing B21, B22. Still, I'm not sure if it is worth it. Depends on the dimensions I guess.

Here is one version, though this still needs the inverse of A22 which is (K-n)x(K-n):

K = 100;
n = 10;
A = randn(K,K);
b = randn(K,1);
% reference version: full inverse
xfull = inv(A)*b;

% blocks of A
A11 = A(1:n,1:n);A12 = A(1:n,n+1:K);A21 = A(n+1:K,1:n);A22 = A(n+1:K,n+1:K);
% blocks of inverse
A22i = inv(A22);                % not sure if this can be avoided
B11 =  inv(A11 - A12*A22i*A21);
B12 = -B11*A12*A22i;

% solution
x_n = [B11,B12]*b;

disp(x_n - xfull(1:n))

edit: Of course, this computes the inverse "explicitly" and as such is probably much slower than just solving the LSE. It could be worth it, if you had several vectors b you want to fit for a fixed A.

Upvotes: 1

bremen_matt
bremen_matt

Reputation: 7349

I guess one way would be to rearrange the columns of A and rows of x so that the elements you are interested in occur at the end of x. Then you would reduce [A,b] to row echelon form. Finally, to get the components you are after, you take the lower right hand nxn submatrix of the modified A (let's call it An) and you solve the reduced system An * xn = bn, where xn denotes the submarine of x that you are interested in, and bn denotes the last n rows of b after the row echelon reduction.

I mean, the conversion here to echelon form is still expensive, but you don't need to solve for the rest of the components in x, which can save you time.

Upvotes: 1

Related Questions