I want to populate quite a large SparseArray(10^6 x10^6) efficiently. It is basically a spin system Hamiltonian with a constrained Hilbert space. Unlike the examples I have looked at in this forum this introduces a problem. On use of BitXor to emulate terms like $\sigma_x$ , in many cases it would yield a value which is not in the Hilbert space, which means I have to do a search in the basis to find the position it corresponds to before storing it in the sparsearray. Let me first show the code which I have written.
First to generate the constrained Hilbert space. I am not going to explain the constraint in detail because that may be confusing, but the following code generates it efficiently enough for me so one can assume this is the Hilbert space.
N1 =24;
X1 = Select[Range[0, 2^N1 - 1], BitAnd[#1, BitShiftLeft[#1, 1]] == 0 & ];
X1 = Select[X1, BitGet[#1, 0]*BitGet[#1, N1 - 1] == 0 & ];
len=Length[X1];
X1 stores the allowed basis vectors and len stores the length of X1. Now the Hamiltonian term which I want to calculate is $\sigma_x$ or in terms of creation and annihilation operators is $\tau \sum_l^{N_1} (d_l^{\dagger}+d_l)$. To generate this I wrote the following code,
SetAttributes[f, Listable];
Needs["Combinatorica`"];
g[j_,k_] := BinarySearch[X1, BitXor[X1[[j]], 2^k]];
f[i_] := (s1 = Mod[i, len] + 1; s2 = IntegerPart[i/len]; k1 = g[s1, s2];
If[IntegerQ[k1], {s1, k1} -> \[Tau]]);
Print[AbsoluteTiming[Q1 = SparseArray[DeleteCases[f[Range[0, len*N1 - 1]],
Null]]; ]];
This takes approximately 217 seconds in my i7 machine. However a similar code written in normal loop constructs in FORTRAN takes a second to evaluate. Now my experience tells me while Mathematica will take more than a second of course because it is not a low level programming language, but the time taken being almost two orders of magnitude higher indicates there is a faster way of doing this. Can anyone help me find it?
I actually need to go to sizes an order of magnitude higher than in the example, hence I need a speedup, plus while I can generate this data via FORTRAN and import to MATHEMATICA from a file, I want to do that as a last resort after exhausting all possibilities of speedup here.
Edit:- In the slow code snippet I want to do the following, I take a basis vector, then operate a BitXor gate one by one on all the bit positions, i.e. from 0 to N1-1. Each would give me a new integer, which may or may not be present in the Hilbert space. I check whether it is present and also its position in the basis vector array by using BinarySearch, once I do that I create a list like {x1,x2}->\tau where x1 is position the basis vector which I started with and x2 is position of the basis vector I get after the operation. If it is not present a "Null" is returned which I delete from the SparseArray. This operation is tried to be made listable using the function "f". Where using "Range" I try to generate both the basis vector positions as well as the bit position using one value to vectorized the code. The "Mod" and "IntegerPart" operation then splits it up to basis vector position and bit position inside the function f.