Calculate a subset of matrix multiplication

Question

When I have two non-sparse matrices A and B , is there a way to efficiently calculate C=ATdot(B) when I only need a subset of the elements of C ? I have the desired C indices stored in the CSC format that is listed here .

Answer 1

If you know in advance which parts of C you want, and some of these parts are adjacent and rectangular areas *, then you can use the rules of matrix algebra associated with multiplying broken matrices ( 1 ) or multiplying matrix matrix ( 2 ) to speed up some from these calculations. So, for example, you can use the same basic logic @GaryBishop, but instead of having a list of elements "i" and "j", you have a list (or array) of four tuples i_start, i_end and j_start, j_end that define the C submatrices, you can use these indexes (although the rules set in these links) to determine the A and B submatrices that you need to solve for the desired C blocks.

For a simple example. Let's say you only need the middle block C, so we split C into C1, C2 and C3 line by line, and all we care about is C2. If A ^ {T} is similarly divided into three sets of lines A1, A2, A3, then C2 = A2 * B. The idea generalizes to rectangles of any shape, it just requires a separate partition of A and B. The idea is the same.

• -This is trivially true, but you will only save time if there are more regions than individual elements.

Answer 2

Instead of iterating over the coordinates using Python (GaryBishop answer), you can have numpy do the loop, which is a significant acceleration (timing below):

 def sparse_mult(a, b, coords) : rows, cols = zip(*coords) rows, r_idx = np.unique(rows, return_inverse=True) cols, c_idx = np.unique(cols, return_inverse=True) C = np.dot(a[rows, :], b[:, cols]) return C[r_idx, c_idx] >>> A = np.arange(12).reshape(3, 4) >>> B = np.arange(15).reshape(3, 5) >>> np.dot(AT, B) array([[100, 112, 124, 136, 148], [115, 130, 145, 160, 175], [130, 148, 166, 184, 202], [145, 166, 187, 208, 229]]) >>> sparse_mult(AT, B, [(0, 0), (1, 2), (2, 4), (3, 3)]) array([100, 145, 202, 208]) 

sparse_mult returns a flattened array of values ​​in the coordinates that you specify as a list of tuples. I am not very good at sparse matrix formats, so I don’t know how to determine CSC from the above data, but the following work:

 >>> coords = [(0, 0), (1, 2), (2, 4), (3, 3)] >>> sparse.coo_matrix((sparse_mult(AT, B, coords), zip(*coords))).tocsc() <4x5 sparse matrix of type '<type 'numpy.int32'>' with 4 stored elements in Compressed Sparse Column format> 

This is a time of various alternatives:

 >>> import timeit >>> a = np.random.rand(2000, 3000) >>> b = np.random.rand(3000, 5000) >>> timeit.timeit('np.dot(a,b)[[0, 0, 1999, 1999], [0, 4999, 0, 4999]]', 'from __main__ import np, a, b', number=1) 5.848562187263569 >>> timeit.timeit('sparse_mult(a, b, [(0, 0), (0, 4999), (1999, 0), (1999, 4999)])', 'from __main__ import np, a, b, sparse_mult', number=1) 0.0018596387374678613 >>> np.dot(a,b)[[0, 0, 1999, 1999], [0, 4999, 0, 4999]] array([ 758.76351111, 750.32613815, 751.4614542 , 758.8989648 ]) >>> sparse_mult(a, b, [(0, 0), (0, 4999), (1999, 0), (1999, 4999)]) array([ 758.76351111, 750.32613815, 751.4614542 , 758.8989648 ]) 

Answer 3

Ignoring the CSC business and possibly the answer to a simpler question than you ask. Here's how I would calculate a subset of C elements given a list of tuples of values ​​for index C.

Since you evaluate C = ATdot (B), you multiply columns A by columns B. So,

 for i, j in indexList: C[i, j] = np.dot(A[:,i], B[:,j]) 

I assume this is not what you are looking for, but I find that a simple answer sometimes helps clarify the question.