Inverses of many standard subspaces of one large matrix

i have a large rectangular invertible matrix M (about 5000x5000) and i have a loop in which i do the following for each iteration i (there are about 6000 iterations):

1. i am given a subspace S_i (which in my problem is always a subset of the standard basis; for example, "dimensions 3, and 300, and 3723"; these subspaces will consist of about 100 out of the original 5000 dimensions). I have no control over which subspace i will be given, and it is not random; some of the dimensions are more 'popular' than others and will tend to more frequently appear within S_i. In my problem, it is unlikely that S_i will happen to be an invariant subspace of M.
2. Compute the rectangular matrix N_i which is just the restriction of the matrix N_i to S_i (that is, start with M and then drop all of the rows and columns of the matrix except for those corresponding to the subspace; for example, drop all rows except for 3, 300, 3723 and drop all columns except for 3, 300, and 3723)
3. Take the inverse N_i^-1

For example, if the matrix M is:

1 2 3
4 0 6
7 8 9


and the subspace for some particular iteration is dimensions {1,2} (with one-based indexing), then N_i is:

1 2
4 0


and the desired inverse for this iteration is:

0    0.25
0.5 -0.125


i feel that perhaps, since i am taking the inverse of parts of the same original matrix M over and over again, and also because many some of the rows and columns are more frequently chosen than others, there could be some shared computation between these 6000 iterations, particularly in step 3 when the inverse is computed. Is there a more efficient way to do this?