# Improve performance of DeleteDuplicates for list of matrices

I have a matrix $$A_0[x,y,z]$$ and a list of matrices $$B$$ with about 30 matrices. Matrix $$A_0$$ is a function of some parameters $$x,y,z$$. I create a new list of matrices, say $$A_1$$ produced by conjugating $$A_0$$ with all elements in $$B$$. Specifically,

A1[x_, y_, z_] = Table[B[[i]].A0[x, y, z].ConjugateTranspose[B[[i]]], {i, 1, Length[B]}] //Simplify // DeleteDuplicates;


Note that at the end I remove possible duplicate matrices in $$A_1$$.

From here I proceed in the same fashion, taking the new list of matrices $$A_1$$ and conjugating each element with each element in $$B$$, removing duplicates and obtaining a new list $$A_2$$

A2[x_, y_, z_] = Flatten[Table[B[[i]].A1[x, y, z][[j]].ConjugateTranspose[B[[i]]], {i, 1, Length[B]}, {j,1,Length[A1[x, y, z]]}],1]
//Simplify // DeleteDuplicates;


Clearly this scales exponentially and at step $$n$$ I have to do $$30^n$$ matrix multiplications and then apply more operations on the list to remove the duplicates. In practice though, the non duplicate matrices after removing duplicates are something like ~(30,90,200,700,1500) for the first 5 iterations for my specific problem and lists of matrices. The problem is that after step 4 it takes a very long time to calculate in my computer. I suspect that this is mainly due to the use of DeleteDuplicates and I have seen that in simpler problems one can get an order of magnitude improvement if they use other ways to do the comparisons.

Questions:

1. Can I use a more clever and efficient way to delete the duplicates, instead of using the built-in function DeleteDuplicates?
2. I have tried to generalize my code so that I don't have to define every new step of iteration as a new block of code and defined an iterative function as follows:
iter[x_, y_, z_, 0] :=
Table[B[[i]] . A0[x, y, z] .
ConjugateTranspose[B[[i]]], {i, 1, Length[B]}] //Simplify // DeleteDuplicates;
iter[x_, y_, z_, n_] :=
Flatten[
Table[
B[[i]] . iter[x, y, z, n - 1][[j]] . ConjugateTranspose[B[[i]]], {i,
1, Length[B]}, {j, 1,
Length[iter[x, y, z, n - 1]]}], 1] //Simplify //
DeleteDuplicates;


However, this doesn't seem to calculate beyond iterations 0 and 1. Or maybe it is way too slow? Any ideas how to do this properly?

1. If I define an iterative function as in Q2 and evaluate it, will it store previous values and only evaluate the new unknown ones or re-evaluate all function from scratch. That is, let's I have evaluated up to $$n=1$$ and call if for $$n=2$$ will it calculate again from scratch the values for $$n=0,1$$? If so, that would be clearly extremely inefficient.

EDIT: Added matrices so that one can run the code I added the matrices straight after the first iteration.

A1[x_,y_,z_]={{{(1 + z)/2, 1/2 (x - I y)}, {1/2 (x + I y), (1 - z)/2}}, {{(1 - z)/
2, 1/2 (x + I y)}, {1/2 (x - I y), (1 + z)/2}}, {{(1 - z)/2,
1/2 (-x - I y)}, {1/2 (-x + I y), (1 + z)/2}}, {{(1 + z)/2,
1/2 (-x + I y)}, {1/2 (-x - I y), (1 - z)/2}}, {{(1 + x)/2,
1/2 (-y + I z)}, {1/2 (-y - I z), (1 - x)/2}}, {{(1 + x)/2,
1/2 (y - I z)}, {1/2 (y + I z), (1 - x)/2}}, {{(1 - x)/2,
1/2 (-y - I z)}, {1/2 (-y + I z), (1 + x)/2}}, {{(1 - x)/2,
1/2 (y + I z)}, {1/2 (y - I z), (1 + x)/2}}, {{(1 - y)/2,
1/2 (I x + z)}, {1/2 (-I x + z), (1 + y)/2}}, {{(1 + y)/2,
1/2 I (x + I z)}, {-(1/2) I (x - I z), (1 - y)/2}}, {{(1 - y)/
2, -(1/2) I (x - I z)}, {1/2 I (x + I z), (1 + y)/2}}, {{(1 + y)/2,
1/2 (-I x + z)}, {1/2 (I x + z), (1 - y)/2}}, {{(1 + x)/2,
1/2 (I y + z)}, {1/2 (-I y + z), (1 - x)/2}}, {{(1 + x)/
2, -(1/2) I (y - I z)}, {1/2 I (y + I z), (1 - x)/2}}, {{(1 - x)/2,
1/2 I (y + I z)}, {-(1/2) I (y - I z), (1 + x)/2}}, {{(1 - x)/2,
1/2 (-I y + z)}, {1/2 (I y + z), (1 + x)/2}}, {{(1 - y)/2,
1/2 (x - I z)}, {1/2 (x + I z), (1 + y)/2}}, {{(1 + y)/2,
1/2 (x + I z)}, {1/2 (x - I z), (1 - y)/2}}, {{(1 - y)/2,
1/2 (-x + I z)}, {1/2 (-x - I z), (1 + y)/2}}, {{(1 + y)/2,
1/2 (-x - I z)}, {1/2 (-x + I z), (1 - y)/2}}, {{(1 + z)/
2, -(1/2) I (x - I y)}, {1/2 I (x + I y), (1 - z)/2}}, {{(1 - z)/2,
1/2 (-I x + y)}, {1/2 (I x + y), (1 + z)/2}}, {{(1 - z)/2,
1/2 I (x + I y)}, {-(1/2) I (x - I y), (1 + z)/2}}, {{(1 + z)/2,
1/2 (I x + y)}, {1/2 (-I x + y), (1 - z)/2}}};

B={{{1, 0}, {0, (-1)^(1/4)}}, {{0, (-1)^(1/4)}, {1,
0}}, {{0, -(-1)^(3/4)}, {I, 0}}, {{1, 0}, {0, -(-1)^(1/4)}}, {{1/
Sqrt, 1/2 + I/2}, {-(I/Sqrt), -(1/2) + I/2}}, {{1/Sqrt,
1/2 + I/2}, {I/Sqrt, 1/2 - I/2}}, {{I/Sqrt,
1/2 - I/2}, {-(1/Sqrt), -(1/2) - I/2}}, {{1/Sqrt[
2], -(1/2) - I/2}, {-(I/Sqrt), 1/2 - I/2}}, {{1/Sqrt[
2], -(1/2) + I/2}, {1/Sqrt, 1/2 - I/2}}, {{I/Sqrt,
1/2 + I/2}, {-(I/Sqrt), 1/2 + I/2}}, {{-(1/Sqrt),
1/2 - I/2}, {1/Sqrt, 1/2 - I/2}}, {{1/Sqrt, 1/2 - I/2}, {1/
Sqrt, -(1/2) + I/2}}, {{1/Sqrt, 1/2 + I/2}, {1/Sqrt[
2], -(1/2) - I/2}}, {{1/Sqrt, 1/2 + I/2}, {-(1/Sqrt),
1/2 + I/2}}, {{I/Sqrt, 1/2 - I/2}, {-(I/Sqrt),
1/2 - I/2}}, {{1/Sqrt, -(1/2) - I/2}, {1/Sqrt,
1/2 + I/2}}, {{1/2 - I/2, I/Sqrt}, {1/2 + I/2, 1/Sqrt[
2]}}, {{1/2 + I/2, 1/Sqrt}, {1/2 - I/2, I/Sqrt[
2]}}, {{-(1/2) + I/2, -(I/Sqrt)}, {1/2 + I/2, 1/Sqrt[
2]}}, {{1/2 - I/2, -(I/Sqrt)}, {1/2 + I/2, -(1/Sqrt)}}, {{1,
0}, {0, (-1)^(3/4)}}, {{0, (-1)^(1/4)}, {I,
0}}, {{0, -(-1)^(3/4)}, {-1, 0}}, {{1, 0}, {0, -(-1)^(3/4)}}};

• Very likely, Simplify is more of a bottleneck than DeleteDuplicates. However, having no input example, I cannot run it without guessing. Mar 30 at 6:57
• Would DeleteDuplicates understand if two matrices are the same but their form is slightly different? I suspect not, and this is why I used Simplify, to put them in similar form. Mar 30 at 7:05
• I evn cannot imagine how your matrices look like. Do they have to be symbolic? Everything would be way faster if you could use matrices with floating point numbers Mar 30 at 7:21
• I added the matrices now, so the code should run Mar 30 at 7:21
• Hm. Apparently, the entries in A are polynomials in x, y, z. You could try to use floating point numbers least for the coefficients. Then Expand should be able to take it quickly to a usable normal form. Or instead of Expand you could also try to use CoefficientRules to extract just the coefficients before you send everything to DeleteDuplicates. Mar 30 at 7:28

Depends on the dimension of the matrix class. The fastest way of deleting without deleting for small matrices is to use Union. The EqualTest may be streamlined eg by comparing simple features like first element or the trace. Instead of appending the latest entry use Union.

For very big matrices its probably faster to convert them to images by Image@Raster@matrix.

For very very big arrays it may be even faster to make the EqualTest on ImageResize'ed objects.

Image processing has the most alaborated mechanisms for simple operations on large arrays

An example

img1 = Image@  Raster@
(ar1 = Array[({Sin[#1/24]^6 RandomReal[{0, 0.4}],
Sin[#2/12]^4 RandomReal[{0.4, 0.6}],
RandomReal[Sin[(#1 + #2)/12]^4 {0.2, 0.8}]} &), {1080,
1920}]).

ar2 = ReplacePart[ar1, {200, 200} -> {0, 0, 0}];
imge=Image@  Raster@ ar2

Timing[ar1 == ar2;]

Timing[img1==img2;]

• I think there are some typos in your code (an extra "." and imge->img2). Apart from that, even though it is cool and I learned something new, I don't think it would be too useful in my case as my matrices are 2x2. Otherwise, can you look at the example I have provided and suggest an implementation? Mar 31 at 2:28
• I think this can't work, at least in its current form, because my A1 matrices depend on unspecified parameters $(x,y,z)$. Moreover, my matrices have complex elements in general. Mar 31 at 2:52