Removing the column(s) from matrices in a fast way C++

Question

Suppose that we have matrix A (m*n) stored in packed form (1-d array of size m*n - with leading dimension - columns). I need to get reduced matrices A(S) - which are resulted from deletion of 1 or more columns from A. I can easily to this by hand in the loops, but there is another approach - using selection matrices I(S) which are the identity matrices (all zeros but 1s on diagonal) with 1 or more column removed. Then, e.g. if I need to remove 3-rd row from A, I need to form I(3) - identity without 3rd column and then A(3)=A*I(S). And since I'd need many variations of A, I would need all different identity matrices I(S) with different columns removed.

I'm thinking of this way because I use Intel Math Kernel Library - which is extremely efficient for matrix multiplications.

So the question is what do you think the fastest way of forming new matrix A(S): by hand, directly working with A or first forming I(S) - and the question is how to quickly form these matrices - and then multiplying A*I(S) or you can suggest any other fast solution.

To illustrate suppose that we have the matrix A:

It is stored in array A=[1,4,7,2,5,8,3,6,9]. Suppose I need to formA(2)` that is remove 2nd column. I need to have on output:

which is stored in C++ as A_S=[1,4,7,3,6,9]. This can be done directly on matrix A, which would take O(n^2) time and not efficient for large matrices. Or we can form I(2):

stored in c++ as I_S = [1,0,0,0,1,0]. Then A(2) = A*I(2)

Do you actually need a result of that specific matrix datatype (or otherwise need to modify the matrix)? Because otherwise it seems to me like the most efficient way to do this could be writing a matrix_view class, which acts like a normal matrix, but modifies the indices on access in order to omit the columns, as this would free you from actually performing a copy. — Grizzly

taocp taocp · Accepted Answer · 2013-04-23T17:50:04

I think you should be careful to use I if you mean identity matrix. Identity matrix are generally square matrix, while you are using is usually not square matrix since you removed column(s) from the original matrix. Let me call the transformation matrix as T, instead of I.

Now I am trying to answer your question:

the question is how to quickly form these matrices

so based on above assumption, T(2) should be:

1  0
0  0
0  1

since

1   2  3       1  0     1  3
4   5  6   *   0  0  =  4  6
7   8  9       0  1     7  9

You can compare the T(2) with original I(3) (here it is identity matrix) based on the situation that you are removing the second column.

      1  0  0
I(3)  0  1  0
      0  0  1

Since you know which column to remove, you will know the index range of the 1D array that you used to store I(3), in this case, it is: A_I(3) = [1 0 0 0 1 0 0 0 1]; you know that index [3,5] are second column, you just need to remove those 3 values, you will get T(2) as in above example, which is A_T(2) = [ 1 0 0 0 0 1]. So the idea is that if you know which column of original matrix to remove, you just remove the values from the 1D array that stores identity matrix within the index range that the original column maps to. In this example, you remove values from [3,5] which 2nd column of original matrix maps to.

Now you can use your Matrix library to multiply A and A_T(2) and get the result matrix.

Removing the column(s) from matrices in a fast way C++

1 Answers