Mathematica: Finding ideal generators as fast as possible

[jackmell]

Hi,

I'd like to find ``ideal'' generators for integer mod groups as quickly as possible and am running into timing problems when the number is large. It's a two-step process: (1) find orbits for all combinations of a generator set, and (2) select which generators are ideal. For (1), the step that takes the longest is to locate in a list, where the orbits are for a set of generators. For example, here are small sections of the orbitList with the generator in the first column, order of generator in second, and the orbit list in third. The second table is a small section of genSet listing in each row, 4-generator pairs. The objective is to locate in orbitList, where the 4-pair generators are so that I can then obtain the orbit lists for the generator pairs.

orbitList:
$\left( \begin{array}{ccc} 5 & 6 & \{5,25,125,121,101,1\} \\ 11 & 6 & \{11,121,155,25,107,1\} \\ 13 & 2 & \{13,1\} \\ 17 & 6 & \{17,121,41,25,89,1\} \\ 19 & 6 & \{19,25,139,121,115,1\} \\ 23 & 6 & \{23,25,71,121,95,1\} \\ 29 & 2 & \{29,1\} \\ 31 & 6 & \{31,121,55,25,103,1\} \\ 37 & 6 & \{37,25,85,121,109,1\} \\ 41 & 2 & \{41,1\} \\ \end{array} \right)$
genSet:
$\left( \begin{array}{cccc} 13 & 29 & 41 & 5 \\ 13 & 29 & 41 & 11 \\ 13 & 29 & 41 & 17 \\ 13 & 29 & 41 & 19 \\ 13 & 29 & 41 & 23 \\ \end{array} \right)$
With Length[orbitList]=45, and Length[genSet]=81900 and I'm using the following code to find the locations of the 81900 generator pairs:

orbitIndex=Flatten[Map[Position[orbitList[[All,1]],#,1,1]&,#]]&/@ genSet;

So for the first genrator set of (13,29,41,5), that code would return the locations in orbitList of (3,7,10,1), the locations of these generators in orbitList. To do all 81900, takes about 2.8 seconds at 2.2 GHz but that's just a small one and I'd like to optimize the code as I plan to work on larger ones too and other parts of the code takes a lot of time as well so I was wondering if someone could suggest a faster way of doing just this part first or is this as fast as I can run it?

Ok thanks for reading,
Jack

 

[mmwave]

Dear Jack,

Thank you for reaching out with your question. I understand your desire to optimize the code for finding the ideal generators for integer mod groups as quickly as possible. After reviewing the code you provided, I have a few suggestions that may help to improve the efficiency of this process.

1. Use vectorization techniques: Instead of using Map and Position functions, which can be slow for large data sets, consider using vectorization techniques. Vectorization allows you to perform operations on entire arrays at once, rather than one element at a time. This can significantly speed up the process.

2. Use built-in functions: Mathematica has many built-in functions that are optimized for speed and efficiency. For example, instead of using Map and Flatten, you can use the built-in function PositionIndex to create an index of the orbitList, which can then be used to quickly find the locations of the generator pairs in the genSet.

3. Consider parallel processing: If you have access to a multi-core processor, you can use Mathematica's built-in parallel processing capabilities to speed up the calculations. This allows you to divide the workload among multiple cores, significantly reducing the time it takes to complete the calculations.

I hope these suggestions help to improve the speed of your code. If you have any further questions, please don't hesitate to reach out.
Scientist