Computation time depends on the matrix elements!

Question

Consider these two lists of matrices, matrix and matrix2:

n = 150;
m = 50;
matrix = Table[1.0*Sin[i*j*k], {i, 1, n}, {j, 1, n}, {k, 1, n}];
matrix2 = Table[Sin[RandomReal[{0, 1}, {n, n}]], {i, 1, n}];

<< Developer`

PackedArrayQ[matrix]

(*False*)

PackedArrayQ[matrix2]

(*False*)

vector = {IdentityMatrix[n][[1]]}\[Transpose];


Do[
  x1 = Table[#1\[ConjugateTranspose].(matrix[[#2]].#1) &[vector, 
      i], {i, 1, n}];

  , {iterator1, 1, m}] // AbsoluteTiming
(*{1.060000, Null}*)



Do[
  x1 = Table[#1\[ConjugateTranspose].(matrix2[[#2]].#1) &[vector, 
      i], {i, 1, n}];

  , {iterator1, 1, m}] // AbsoluteTiming
(*{0.170000, Null}*)

Why does using matrix2 give the fastest computation time?

Does the speed of matrix multiplication depend on the value of the matrices involved?

Answer 1

First load up the lists of matrices as you define them:

n = 150;
m = 50;
matrix = Table[1.0*Sin[i*j*k], {i, 1, n}, {j, 1, n}, {k, 1, n}];
matrix2 = Table[Sin[RandomReal[{0, 1}, {n, n}]], {i, 1, n}];

Now let's check the sizes:

ByteCount[matrix]
(* 83174488 *)

ByteCount[matrix2]
(* 27024088 *)

Very different! Now...

<<Developer`
matrix3 = ToPackedArray@matrix;
ByteCount[matrix3]
(* 27000160 *)

matrix4 = ToPackedArray@matrix2;
ByteCount[matrix3]
(* 27000160 *)

So now they're the same size in terms of bytes, but is that the end of the story? No, as we can see from a timing comparison:

<< GeneralUtilities`
Do[x1 = Table[#1\[ConjugateTranspose].(matrix[[#2]].#1) &[vector, 
      i], {i, 1, n}];, {iterator1, 1, m}] // AccurateTiming

(* 1.148 seconds *)

Do[x1 = Table[#1\[ConjugateTranspose].(matrix2[[#2]].#1) &[vector, 
      i], {i, 1, n}];, {iterator1, 1, m}] // AccurateTiming

(* 0.1814 seconds *)

Do[x1 = Table[#1\[ConjugateTranspose].(matrix3[[#2]].#1) &[vector, 
      i], {i, 1, n}];, {iterator1, 1, m}] // AccurateTiming

(* 0.3711 seconds *)

Do[x1 = Table[#1\[ConjugateTranspose].(matrix4[[#2]].#1) &[vector, 
      i], {i, 1, n}];, {iterator1, 1, m}] // AccurateTiming

(* 0.3087 seconds *)

matrix2 is still the fastest! The same result can be achieved by doing the following, i.e. packing each sub-matrix within the larger list.

matrix5 = ToPackedArray[#] & /@ matrix;
ByteCount[matrix5]
Do[x1 = Table[#1\[ConjugateTranspose].(matrix5[[#2]].#1) &[vector, 
      i], {i, 1, n}];, {iterator1, 1, m}] // AccurateTiming

(* 27024088 *)
(* 0.1791 seconds *)

Thus, the fastest computation is achieved by packing the individual matrices within each list, which is true for matrix2 but not for matrix.