Skip to main content

performance tuning - How to speed up band matrix-matrix multiplication?


I have a band matrix


$HistoryLength = 0;
n = 10000;
b = 300;

k = 300;
a = SparseArray[Flatten[#, 1] &@Table[{i, Mod[i + j, n, 1]}, {i, n}, {j, -b, b}] ->
     RandomComplex[{-1 - I, 1 + I}, n (2 b + 1)]];

and a dense matrix


u = RandomComplex[{-1 - I, 1 + I}, {n, k}];

I want to multiply them as fast as possible


v = a.u; // AbsoluteTiming



{6.748518, Null}



Visual representation of this multiplication:


draw = ArrayPlot[#[[;; ;; 30, ;; ;; 30]], ImageSize -> {Automatic, 200}] &;
Row@{draw[v], " = ", draw[a].draw[u]}

enter image description here


This problem usually comes up when you want to multiply a Hamiltonian by a set of wavefunctions (in a certain basis).


Why I expect a possibility of speeding up? When you multiply dense matrices you can use algorithms like Strassen algorithm and use the processor cache to operate with small blocks. The matrix a have a dense band. This knowledge can increase performance in contradiction to the sparse matrix of a general form.





Comments

Post a Comment