# The calculation of the weight spectrum of a linear subspace in Wolfram Mathematica

3r31149. 3r3-31. 3r31134. 3r31137. 3r31132. 3r31149.

The root cause of r3r31127. 3r31132. 3r31149. 3r31134. This article owes its appearance to one rather long-standing question that was asked in the Wolfram Mathematica group of Russian-speaking support. However, the answer to it greatly grew and eventually began to live an independent life, and even got its own problems. As is clear from the title of the article, the task was devoted to calculating the weight spectrum, and therefore it directly relates to discrete mathematics and linear algebra. It also shows the solution in the programming language Wolfram Language. Despite the fact that the essence of the problem is very simple (for simple basic vectors, it is completely solved in the mind), much more interesting is the process of optimizing the algorithm for finding the weight spectrum. The authors are of the opinion that the problem considered in this article and the ways to solve it very well show how compilation and parallelization methods of applying such techniques in the Wolfram language are used. Thus, the main goal is to show one of the effective ways to speed up code in Mathematica. 3r31137. Compile 3r31136. 3r31061.

3r31132. 3r31149. 3r31134. The syntax of this function is quite simple and very similar to

Function 3r31061. . As a result, 3r3-1060. Compile 3r31061. always returns an "object" - a compiled function that can be applied to numeric values or lists of numbers. 3r3-1060. Compile 3r31061. does not support working with Wolfram Language strings, characters, or compound expressions (except expressions consisting of 3r31060. List 3r3-31061.). Below are some examples of creating compiled functions. 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. cSqr = Compile[{x}, x^2]; 3r31149. cSqr[2.0]3r31149. (* Out[]: = 4.0 *)

3r31149. cNorm = Compile[{x, y}, Sqrt[x^2 + y^2]]; 3r31149. cNorm[3.0, 4.0]3r31149. (* Out[]: = 5.0 *)

3r31149. cReIm = Compile[{{z, _Complex}}, {Re[z], Im[z]}]; 3r31149. cReIm[1 + I]3r31149. (* Out[]: = {1.? 1.0} *)

3r31149. cSum = Compile[{{list, _Real, 1}}, Module[{s = 0.0}, Do[s += el, {el, list}]; s]]; 3r31149. cSum[{1, 2, 3.0, 4.}]3r31149. (* Out[]: = 10.0 *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. All available options and more detailed examples can be found in the official documentation at the link above. Now let's go directly to the function for calculating the weight spectrum. 3r31137. 3r31132. 3r31149. 3r33333. Compilation of weight spectrum calculation

3r31132. 3r31149. 3r31134. As in the simple case, you can create some simple functions, and then apply them in turn to get the result. And you can perform all operations in the body of just one function. Both that and other method can be quite realized. We will go the second way for the sake of diversity. 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. cWeightSpectrumSimple =

Compile[

{{basis, _Integer, 2}},

Module[

{

k = Length[basis], 3r31149. spectrum = Table[0, {i, 0, Last[Dimensions[basis]]}]

},

3r31149. Do[

With[

{

(* вычисление веса одной из 2^k - 1 комбинаций *)

weight = Total[Mod[Total[IntegerDigits[b, 2, k]* basis], 2]]+ 1

},

(*

The size of the spectrum list is equal to the maximum possible weight.

The variable weight at each iteration is the weight of the linear combination 3r31149. So here we increase by 1 list element, 3r31149. Whose index is equal to the weight just calculated.

As a result spectrum contains a weight spectrum right away.

This way of counting is very similar to the sorting algorithm of 3r3114? which already saves a significant number of operations. 3r31149. *) 3r31149. spectrum[[weight]]= spectrum[[weight]]+ 1

], 3r31149. {b, ? 2 ^ k - 1}

]; 3r31149. 3r31149. Return[Transpose[{Range[0, Last[Dimensions[basis]]], spectrum}]]3r31149. ]

] 3r31114. 3r31132. 3r31149. 3r31134. As always, we will conduct a small test of the correctness of this function. In the same way, we take a list of random bases with sizes from 2 to 15 vectors, where each vector consists of 10 elements and try to calculate the time at which the weight spectrum is calculated: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 15}]; 3r31149. timeList = Table[{Length[basis], First[AbsoluteTiming[cWeightSpectrumSimple[basis]]]}, {basis, basisList}]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r31132. 3r31149. 3r33386. About the Gray Code

3r31132. 3r31149. 3r31134. While thinking about how to solve the problem, a simple thought arose. If suddenly the next value

b

k 3r33848. and add to it only those basic vectors whose index coincides with the numbers of differing bits between 3r3845. k 3r33848. and 3r33845. k + 1

. The result will be a linear combination of

k + 1

. And what if you go further? Suddenly it turns out that the difference between adjacent linear combinations in just one vector? If you build a direct sequence from 0 to 2

One of the infinite set of codes is described - the Gray Gray Code and the method for obtaining it. Below is an example of such a sequence:

3r31132. 3r31149. 3r33859. 3r31149. 3r33861. 3r31149. 3r33947. 3r31149. 3r33868. Decimal

3r31149. 3r33868. Binary

3r31149. 3r33868. Gray

3r31149. 3r33868. Gray as decimal

3r31149. 3r3393955. 3r31149. 3r33873. 3r31149. 3r33875. 3r31149. 3r33947. 3r31149. 3r3952. 0

3r31149. 3r3952. 000 3r3953. 3r31149. 3r3952. 000 3r3953. 3r31149. 3r3952. 0

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 1

3r31149. 3r3952. 001 3r3953. 3r31149. 3r3952. 001 3r3953. 3r31149. 3r3952. 1

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 2

3r31149. 3r3952. 010

3r31149. 3r3952. 011 3r3953. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3952. 011 3r3953. 3r31149. 3r3952. 010

3r31149. 3r3952. 2

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 4

3r31149. 3r3952. 100

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3952. 6

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 5

3r31149. 3r3952. 101

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3952. 7

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 6

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3952. 101

3r31149. 3r3952. 5

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 7

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3952. 100

3r31149. 3r3952. 4

3r31149. 3r3393955. 3r31149. 3r3957. 3r31149. 3r3r9959. 3r31132. 3r31149. 3r? 3594. Use in the compiled function 3r3826. 3r31132. 3r31149. 3r31134. The use of compilation already significantly speeds up the calculation of the weight spectrum; now we will try to use the Gray code and optimize the addition of the linear combination vectors. Only it is necessary to understand how to calculate the position of the changed bit at each step. Fortunately, the 13th chapter of this 3r3599 came to the rescue. books

. Entirely calculate the linear combination will be required only once at the very beginning. But, since it is precisely known that the first linear combination is a set of zeros, this will not be necessary. With all this in mind, you can create an even more optimized function for calculating the weight spectrum:

3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeEasy = Compile[{{basevectors, _Integer, 2}},

Module[{

n = Dimensions[basevectors] [[-1]], 3r31149. k = Length[basevectors], 3r31149. s = Table[0, {n + 1}], 3r31149. currentVector = Table[0, {n}], (* the first combination is always {? ?} *)

m = ? l = 0

},

(* it is known that in the spectrum, 0 will have a weight greater than or equal to 1

? since the first linear combination is always the zero vector *)

s[[1]]= 1; 3r31149. Do[

(*позиция изменившегося бита*)

m = Log2[BitAnd[-1 - b, b + 1]]+ 1; 3r31149. 3r31149. (* here there is no complete addition of vectors, but only the addition of the difference *)

currentVector = BitXor[currentVector, basevectors[[m]]]; 3r31149. 3r31149. (* weight calculation *) 3r31149. l = Total[currentVector]+ 1; 3r31149. 3r31149. s[[l]]= s[[l]]+ ?

3r31149. {b, ? 2 ^ k - 2}

]; 3r31149. 3r31149. (* Return *) s

], 3r31149. (* additional compilation options, 3r31149. The second can be used only if you have a compiler *) 3r31149. RuntimeOptions -> "Speed", (* CompilationTarget -> "C", *)

CompilationOptions -> {"ExpressionOptimization" -> True}

]; 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. Here is an example of the result for a basis of 16 vectors with a dimension of 512:

3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {16, 512}]; 3r31149. ListPlot[WeightSpectrumLinearSubspaceGrayCodeEasy[basis], 3r31149. PlotTheme -> "Web", PlotRange -> All, Filling -> Bottom] 3r31114. 3r31132. 3r31149. 3r31134. 3r33655. 3r31137. 3r31132. 3r31149. 3r31134. As a result, a one-dimensional list of weights is returned. This type of list is also quite correct, as it is easy to bring it to the view from the previous part. The first element corresponds to the frequency of meeting the vector of zero weight. The latter is the frequency of the meeting of the vector of units. Use the same code to test performance: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 15}]; 3r31149. timeList = Table[{Length[basis], First[AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]]]}, {basis, basisList}]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r3673. 3r31137. 3r31132. 3r31149. 3r31134. 3r33845. Calculation time from the size of the basis

3r31137. 3r31132. 3r31149. 3r31134. As a result, for the last basis from the list of 15 vectors, the computation speed increased by another 5 times. But this is a slightly misleading result. To understand how much efficiency has increased, it is necessary to calculate the ratio of the calculation time for the last two functions: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 20}]; 3r31149. timeList = Table[{

Length[basis], 3r31149. First[RepeatedTiming[cWeightSpectrumSimple[basis]]]/

First[RepeatedTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]]]

},

{basis, basisList}

]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r33737. 3r31137. 3r31132. 3r31149. 3r31134. 3r33845. The ratio of the spectrum calculation time using the gray code and without r3r3848. 3r31137. 3r31132. 3r31149. 3r31134. From this graph it becomes clear that in fact this algorithm lowered the complexity of computations by one degree. And this will be the more noticeable and more efficient the larger the dimension of the vectors in the basis. This result is obtained if the basis consists of vectors with the dimension 128:

3r31132. 3r31149. 3r31134. 3r33737. 3r31137. 3r31132. 3r31149. 3r33720. Parallelization 3r3-31127. 3r31132. 3r31149. 3r33724. How to calculate something in Mathematica in parallel

3r31132. 3r31149. 3r31134. Mathematica has a small set of functions that can perform asynchronous computations on different cores. Only now it is necessary to define with terminology. After all, a running process that represents something similar to a virtual machine in Mathematica is also called a kernel, i.e. Kernel. The Core of Mathematics is an interactive execution environment operating in interpreter mode. Each core takes necessarily one process in the system. Threads in the usual sense of the language does not implement. Accordingly, you need to understand that the kernels in standard use will not have shared memory. Basically, all functions of this type begin on

3r33737. Parallel

3r31061. . The easiest way to calculate something asynchronously:

3r31132. 3r31149. 3r31100. 3r31101. ParallelTable[i^2,{i, 1, 10}]3r31149. 3r31149. (* Out[]: = {? ? ? 1? 2? 3? 4? 6? 8? 100} *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. A number of functions work in a similar way: 3r31132. 3r31149. 3r3-1060. 3r33748. ParallelMap

3r31061. , 3r31060. 3r3752. ParallelDo

3r31061. , 3r31060. 3r3756. ParallelProduct

3r31061. , 3r31060. 3r33737. ParallelSum

3r31061. , 3r31137. 3r31132. 3r31149. 3r31134. There are several ways to verify that this was not actually done on a single core. This is how you can get all the running kernels: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. Kernels[]3r31149. 3r31149. (* Out[]: = {"KernelObject"[1, "local"], , "KernelObject"[N, "local"]} *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. The list will contain all currently running processes. At the same time, they should also be displayed in the task manager. 3r31137. 3r31132. 3r31149. 3r31134. LaunchKernels[n]3r31136. 3r31061. . As a result,

starts. additionally 3r33848. n cores. And the number of available processor cores can be viewed in the variable

3r33795. $ KernelCount

3r31061. . 3r31137. 3r31132. 3r31149. 3r31134. The functions listed at the beginning produce an automatic distribution of tasks among the processes. However, there is a way to independently send code to run on a specific kernel. This is done using

ParallelEvaluate 3r31061. +

ParallelSubmit 3r31061. :

3r31132. 3r31149. 3r31100. 3r31101. ParallelEvaluate[$KernelID, Kernels[] [[1 ;; 4 ;; 2]]]

3r31149. (* Out[]: = {? 3} *) 3r31114. 3r31132. 3r31149. 3r31134. This set of functions will be enough to be able to parallelize the task of calculating the weight spectrum. 3r31137. 3r31132. 3r31149. 3r33825. Dividing the main loop into parts 3r3826. 3r31132. 3r31149. 3r31134. Check whether the calculations actually occur in parallel. For four physical cores, this means that the calculation on all four cores will take as much time as on one: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {24, 24}]; 3r31149. AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis];] [[1]]

AbsoluteTiming[ParallelEvaluate[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]];] [[1]]

3r31149. (* Out[]: = ???

Out[]: = ??? *) 3r31114. 3r31132. 3r31149. 3r31134. There is a time difference, but not fourfold. So with this, everything is fine. The next step is to figure out how to divide the task into several parts. The most logical and effective is to compute only part of the linear combinations on each core. That is, as a result, each core returns a partial spectrum. But how to divide the list

b [sub] i 3r33847. 3r33848. . After all, it is not a direct sequence! In this case, a function is needed that calculates the value from the Gray Code sequence by index. This is done like this:

3r31132. 3r31149. 3r31100. 3r31101. grayNum[basis_List, index_Integer]: = IntegerDigits[BitXor[index, Quotient[index, 2]], ? Length[basis]]

Grid[Table[{i, Row[grayNum[{{0, 0}, {0, 1}, {1, 1}}, i]]}, {i, ? 7}]] 3r31114. 3r31132. 3r31149. 3r33859. 3r31149. 3r33861. 3r31149. 3r33947. 3r31149. 3r33868. index

3r31149. 3r33868. code

3r31149. 3r3393955.

3r33873. 3r31149. 3r33875. 3r31149. 3r33947. 3r31149. 3r3952. 0

3r31149. 3r3952. 000 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 1

3r31149. 3r3952. 001 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 2

3r31149. 3r3952. 011 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3952. 010

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 4

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 5

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 6

3r31149. 3r3952. 101

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 7

3r31149. 3r3952. 100

3r31149. 3r3393955. 3r31149. 3r3957. 3r31149. 3r3r9959. 3r31132. 3r31149. 3r31134. Now we modify the compiled function so that it counts only a partial spectrum in a certain range of indices of linear combinations:

3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeRange =

Compile[{{basis, _Integer, 2}, {range, _Integer, 1}},

Module[{

n = Dimensions[basis] [[-1]], 3r31149. k = Length[basis], 3r31149. s = Table[0, {n + 1}], 3r31149. currentVector = Table[0, {i, 1, Length[basis[[1]]]}],

m = ? l = 0

},

(* we calculate the first vector and its weight *)

If[range[[1]]=! = ?

currentVector = Mod[Total[basis Reverse[IntegerDigits[BitXor[range[[1]], Quotient[range[[1]]+ ? 2]], ? k]]], 2]; 3r31149. ]; 3r31149. Mod[Total[basis IntegerDigits[BitXor[range[[1]]- ? Quotient[range[[1]]- ? 2]], ? k]], 2]; 3r31149. s[[Total[currentVector]+ 1]]= 1; 3r31149. Do[

m = Log2[BitAnd[-1 - b, b + 1]]+ 1; 3r31149. currentVector = BitXor[currentVector, basis[[m]]]; 3r31149. l = Total[currentVector]+ 1; 3r31149. s[[l]]= s[[l]]+ ?

3r31149. {b, First[range], Last[range]- ? 1}

]; 3r31149. (* Return *) s

], 3r31149. (* additional compilation options, 3r31149. The second can be used only if you have a compiler *) 3r31149. RuntimeOptions -> "Speed", (* CompilationTarget -> "C", *)

CompilationOptions -> {"ExpressionOptimization" -> True}

]; 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. That is, if earlier the function counted all combinations with numbers from 0 to 2

With[{dn = Round[(iN - i1 + 1)/n]},

Join[

{{i1, i1 + dn - 1}},

Table[{dn * (i - 1), i * dn - 1}, {i, 2, n - 1}], 3r31149. {{(n - 1) * dn, iN}}

]

] 3r31114. 3r31132. 3r31149. 3r31134. Now, in order to calculate the full spectrum in such a way, it is necessary to calculate it on each of the segments, and then add all the results. For example: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeEasy[{{1, 1}, {1, 1}, {1, 1}}]3r31149. WeightSpectrumLinearSubspaceGrayCodeRange[{{1, 1}, {1, 1}, {1, 1}}, {0, 3}]3r31149. WeightSpectrumLinearSubspaceGrayCodeRange[{{1, 1}, {1, 1}, {1, 1}}, {4, 7}]3r31149. 3r31149. (*

Out[]: = {? ? 4} =

Out[]: = {? ? 2} +

Out[]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. The final step is to send these calculations to different kernels: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeParallel[basis: {{__Integer}}]: =

With[{

kernels = (If[Kernels[]=== {}, LaunchKernels[]]; Kernels[]), 3r31149. parts = partition[{0, 2^Length[basis]- 1}, Length[Kernels[]]]

},

Total[WaitAll[Table[

ParallelEvaluate[ParallelSubmit[WeightSpectrumLinearSubspaceGrayCodeRange[basis, parts[[$KernelID]]]], kernel],

{kernel, kernels}

]]]

] 3r31114. 3r31132. 3r31149. 3r31134. Here it is necessary to clarify. Such a bunch 3r31060. ParallelEvaluate

+

ParallelSubmit

in order to manually control which core will execute which part of the code. ParallelEvaluate generally cannot figure out how to properly execute asynchronous code and ultimately does it in one thread. In the general case, ParallelSubmit does not allow you to specify the correct core, but selects it automatically. 3r31132. 3r31149. Check if this feature works: 3r3r1137. 3r31132. 3r31149. 3r31100. 3r31101. ListPlot[WeightSpectrumLinearSubspaceGrayCodeParallel[RandomInteger[{0, 1}, {16, 128}]], 3r31149. PlotRange -> All, PlotTheme -> "Web", Filling -> Bottom] 3r31114. 3r31132. 3r31149. 3r31134. 3r31075. 3r31137. 3r31132. 3r31149. 3r31134. And as usual we will look at the difference in the speed of calculations. Since a laptop with a 4-core processor is used, an acceleration of about 4 times is expected. Plus, we must take into account the time for the division of tasks and the addition of the final result:

3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {20, 1024}]; 3r31149. AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis];]

AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeParallel[basis];]

3r31149. (*

Out[]: = {??? , Null}

Out[]: = {1.5 , Null}

*) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. Naturally, with a larger number of processor cores, the difference will be more noticeable. Now let's try to calculate the spectrum of a larger base. I wonder how long it will take? Suppose we assume to increase the size of the basis until one calculation takes more than a minute: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. spectrums = Block[{i = 1, basis, res}, Reap[

While[True,

i++;

basis = RandomInteger[{0, 1}, {i, i}]; 3r31149. Sow[res = AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeParallel[basis]]]; 3r31149. If[res[[1 6 Break[]]

]

] [[-1, -1]]]

3r31149. ListPlot[spectrums[[-1, -1]], 3r31149. PlotLabel-> Row[{"basis len: ", Length[spectrums]+ ? "; time:", Round[spectrums[[-1, 1]], ???], "sec"}],

Filling-> Bottom, PlotTheme -> "Web", PlotRange-> All] 3r31114. 3r31132. 3r31149. 3r31134. 3r31118. 3r31137. 3r31132. 3r31149. 3r31134. The picture clearly shows that in a minute and a half the function can calculate the spectrum for a basis of 29 vectors. This is a very good result, given that the very first option, which does not use compilation, the Gray code, parallelization, is also hardly able to execute everything in a reasonable time. The computation time will be thousands of times longer if even for 15 vectors with dimension 10 the calculation took more than 10 seconds. 3r31137. 3r31132. 3r31149. 3rr31126. Conclusion 3r3-31127. 3r31132. 3r31149. 3r31134. I do not know who and where applies all that was described in the article. Wikipedia says the Gray Code has a practical purpose. I also know that the calculation of spectra is often associated with encryption and some other problems of linear algebra. But, once again, it is worth noting that here I wanted first of all to demonstrate step-by-step solution of the problem and step-by-step application of various kinds of optimizations: improvement of the algorithm itself, use of the language features and use of the hardware capabilities of multi-core processors. I sincerely hope that the article will be useful and interesting. 3r31137. 3r31132. 3r31149. 3r31134. P.S. The author thanks Alexander Bannikov , since he is the initiator in the search for the optimal solution to this problem. 3r31137. 3r31145. 3r31149. 3r31149. 3r31149. 3r31142. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r31143. 3r31149. 3r31145. 3r31149. 3r31149. 3r31149. 3r31149.

The root cause of r3r31127. 3r31132. 3r31149. 3r31134. This article owes its appearance to one rather long-standing question that was asked in the Wolfram Mathematica group of Russian-speaking support. However, the answer to it greatly grew and eventually began to live an independent life, and even got its own problems. As is clear from the title of the article, the task was devoted to calculating the weight spectrum, and therefore it directly relates to discrete mathematics and linear algebra. It also shows the solution in the programming language Wolfram Language. Despite the fact that the essence of the problem is very simple (for simple basic vectors, it is completely solved in the mind), much more interesting is the process of optimizing the algorithm for finding the weight spectrum. The authors are of the opinion that the problem considered in this article and the ways to solve it very well show how compilation and parallelization methods of applying such techniques in the Wolfram language are used. Thus, the main goal is to show one of the effective ways to speed up code in Mathematica. 3r31137. Compile 3r31136. 3r31061.

3r31132. 3r31149. 3r31134. The syntax of this function is quite simple and very similar to

Function 3r31061. . As a result, 3r3-1060. Compile 3r31061. always returns an "object" - a compiled function that can be applied to numeric values or lists of numbers. 3r3-1060. Compile 3r31061. does not support working with Wolfram Language strings, characters, or compound expressions (except expressions consisting of 3r31060. List 3r3-31061.). Below are some examples of creating compiled functions. 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. cSqr = Compile[{x}, x^2]; 3r31149. cSqr[2.0]3r31149. (* Out[]: = 4.0 *)

3r31149. cNorm = Compile[{x, y}, Sqrt[x^2 + y^2]]; 3r31149. cNorm[3.0, 4.0]3r31149. (* Out[]: = 5.0 *)

3r31149. cReIm = Compile[{{z, _Complex}}, {Re[z], Im[z]}]; 3r31149. cReIm[1 + I]3r31149. (* Out[]: = {1.? 1.0} *)

3r31149. cSum = Compile[{{list, _Real, 1}}, Module[{s = 0.0}, Do[s += el, {el, list}]; s]]; 3r31149. cSum[{1, 2, 3.0, 4.}]3r31149. (* Out[]: = 10.0 *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. All available options and more detailed examples can be found in the official documentation at the link above. Now let's go directly to the function for calculating the weight spectrum. 3r31137. 3r31132. 3r31149. 3r33333. Compilation of weight spectrum calculation

3r31132. 3r31149. 3r31134. As in the simple case, you can create some simple functions, and then apply them in turn to get the result. And you can perform all operations in the body of just one function. Both that and other method can be quite realized. We will go the second way for the sake of diversity. 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. cWeightSpectrumSimple =

Compile[

{{basis, _Integer, 2}},

Module[

{

k = Length[basis], 3r31149. spectrum = Table[0, {i, 0, Last[Dimensions[basis]]}]

},

3r31149. Do[

With[

{

(* вычисление веса одной из 2^k - 1 комбинаций *)

weight = Total[Mod[Total[IntegerDigits[b, 2, k]* basis], 2]]+ 1

},

(*

The size of the spectrum list is equal to the maximum possible weight.

The variable weight at each iteration is the weight of the linear combination 3r31149. So here we increase by 1 list element, 3r31149. Whose index is equal to the weight just calculated.

As a result spectrum contains a weight spectrum right away.

This way of counting is very similar to the sorting algorithm of 3r3114? which already saves a significant number of operations. 3r31149. *) 3r31149. spectrum[[weight]]= spectrum[[weight]]+ 1

], 3r31149. {b, ? 2 ^ k - 1}

]; 3r31149. 3r31149. Return[Transpose[{Range[0, Last[Dimensions[basis]]], spectrum}]]3r31149. ]

] 3r31114. 3r31132. 3r31149. 3r31134. As always, we will conduct a small test of the correctness of this function. In the same way, we take a list of random bases with sizes from 2 to 15 vectors, where each vector consists of 10 elements and try to calculate the time at which the weight spectrum is calculated: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 15}]; 3r31149. timeList = Table[{Length[basis], First[AbsoluteTiming[cWeightSpectrumSimple[basis]]]}, {basis, basisList}]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r31132. 3r31149. 3r33386. About the Gray Code

3r31132. 3r31149. 3r31134. While thinking about how to solve the problem, a simple thought arose. If suddenly the next value

b

_{ i 3r33847. 3r33848. is zero, there is generally no need to multiply the base vector nAnd this number and add it. Those vectors that are multiplied with zero values do not change the result. At first it seemed like a great thought and it even worked. After all, while iterating through the list itemsb [sub] i 3r33847. 3r33848. just came out less vector addition operations. Then came the next idea. The subtraction and addition of vectors in the calculation of a linear combination is no different. This means that the following is feasible:3r31132. 3r31149. 3r31100. 3r31101. 1 * {? 1} + 0 * {? 0} + 1 * {? 1} == {? 1} + {? 1}{? 1} + {? 1} == {? 0} -> {? 0} + {? 1} == {? 1} 3r31114. 3r31132. 3r31149. 3r31134. That is, adding a vector to an intermediate sum is no different from subtracting. And then it all came together in a great idea! What if suddenly it turns out that in the loop on the list 3r33838. b [sub] i 3r33847. 3r33848. the difference between thepresentation. b [sub] k 3r3r47. 3r33848. and 3r33845. b [sub] k + 1 }3r33848. just a few bits? Then you can get a linear combination with the numberk 3r33848. and add to it only those basic vectors whose index coincides with the numbers of differing bits between 3r3845. k 3r33848. and 3r33845. k + 1

. The result will be a linear combination of

k + 1

. And what if you go further? Suddenly it turns out that the difference between adjacent linear combinations in just one vector? If you build a direct sequence from 0 to 2

^{ N }-1 - this is impossible. But suddenly you can mix and arrange these numbers in some other order? This, as it turned out, is called the Gray Code, a sequence of numbers, in which the difference between neighbors is only one digit. In 3r33432. WikipediaOne of the infinite set of codes is described - the Gray Gray Code and the method for obtaining it. Below is an example of such a sequence:

3r31132. 3r31149. 3r33859. 3r31149. 3r33861. 3r31149. 3r33947. 3r31149. 3r33868. Decimal

3r31149. 3r33868. Binary

3r31149. 3r33868. Gray

3r31149. 3r33868. Gray as decimal

3r31149. 3r3393955. 3r31149. 3r33873. 3r31149. 3r33875. 3r31149. 3r33947. 3r31149. 3r3952. 0

3r31149. 3r3952. 000 3r3953. 3r31149. 3r3952. 000 3r3953. 3r31149. 3r3952. 0

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 1

3r31149. 3r3952. 001 3r3953. 3r31149. 3r3952. 001 3r3953. 3r31149. 3r3952. 1

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 2

3r31149. 3r3952. 010

3r31149. 3r3952. 011 3r3953. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3952. 011 3r3953. 3r31149. 3r3952. 010

3r31149. 3r3952. 2

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 4

3r31149. 3r3952. 100

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3952. 6

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 5

3r31149. 3r3952. 101

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3952. 7

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 6

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3952. 101

3r31149. 3r3952. 5

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 7

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3952. 100

3r31149. 3r3952. 4

3r31149. 3r3393955. 3r31149. 3r3957. 3r31149. 3r3r9959. 3r31132. 3r31149. 3r? 3594. Use in the compiled function 3r3826. 3r31132. 3r31149. 3r31134. The use of compilation already significantly speeds up the calculation of the weight spectrum; now we will try to use the Gray code and optimize the addition of the linear combination vectors. Only it is necessary to understand how to calculate the position of the changed bit at each step. Fortunately, the 13th chapter of this 3r3599 came to the rescue. books

. Entirely calculate the linear combination will be required only once at the very beginning. But, since it is precisely known that the first linear combination is a set of zeros, this will not be necessary. With all this in mind, you can create an even more optimized function for calculating the weight spectrum:

3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeEasy = Compile[{{basevectors, _Integer, 2}},

Module[{

n = Dimensions[basevectors] [[-1]], 3r31149. k = Length[basevectors], 3r31149. s = Table[0, {n + 1}], 3r31149. currentVector = Table[0, {n}], (* the first combination is always {? ?} *)

m = ? l = 0

},

(* it is known that in the spectrum, 0 will have a weight greater than or equal to 1

? since the first linear combination is always the zero vector *)

s[[1]]= 1; 3r31149. Do[

(*позиция изменившегося бита*)

m = Log2[BitAnd[-1 - b, b + 1]]+ 1; 3r31149. 3r31149. (* here there is no complete addition of vectors, but only the addition of the difference *)

currentVector = BitXor[currentVector, basevectors[[m]]]; 3r31149. 3r31149. (* weight calculation *) 3r31149. l = Total[currentVector]+ 1; 3r31149. 3r31149. s[[l]]= s[[l]]+ ?

3r31149. {b, ? 2 ^ k - 2}

]; 3r31149. 3r31149. (* Return *) s

], 3r31149. (* additional compilation options, 3r31149. The second can be used only if you have a compiler *) 3r31149. RuntimeOptions -> "Speed", (* CompilationTarget -> "C", *)

CompilationOptions -> {"ExpressionOptimization" -> True}

]; 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. Here is an example of the result for a basis of 16 vectors with a dimension of 512:

3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {16, 512}]; 3r31149. ListPlot[WeightSpectrumLinearSubspaceGrayCodeEasy[basis], 3r31149. PlotTheme -> "Web", PlotRange -> All, Filling -> Bottom] 3r31114. 3r31132. 3r31149. 3r31134. 3r33655. 3r31137. 3r31132. 3r31149. 3r31134. As a result, a one-dimensional list of weights is returned. This type of list is also quite correct, as it is easy to bring it to the view from the previous part. The first element corresponds to the frequency of meeting the vector of zero weight. The latter is the frequency of the meeting of the vector of units. Use the same code to test performance: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 15}]; 3r31149. timeList = Table[{Length[basis], First[AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]]]}, {basis, basisList}]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r3673. 3r31137. 3r31132. 3r31149. 3r31134. 3r33845. Calculation time from the size of the basis

3r31137. 3r31132. 3r31149. 3r31134. As a result, for the last basis from the list of 15 vectors, the computation speed increased by another 5 times. But this is a slightly misleading result. To understand how much efficiency has increased, it is necessary to calculate the ratio of the calculation time for the last two functions: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basisList = Table[RandomInteger[{0, 1}, {i, 10}], {i, ? 20}]; 3r31149. timeList = Table[{

Length[basis], 3r31149. First[RepeatedTiming[cWeightSpectrumSimple[basis]]]/

First[RepeatedTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]]]

},

{basis, basisList}

]; 3r31149. ListLinePlot[timeList, PlotTheme -> "Web"]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. 3r33737. 3r31137. 3r31132. 3r31149. 3r31134. 3r33845. The ratio of the spectrum calculation time using the gray code and without r3r3848. 3r31137. 3r31132. 3r31149. 3r31134. From this graph it becomes clear that in fact this algorithm lowered the complexity of computations by one degree. And this will be the more noticeable and more efficient the larger the dimension of the vectors in the basis. This result is obtained if the basis consists of vectors with the dimension 128:

3r31132. 3r31149. 3r31134. 3r33737. 3r31137. 3r31132. 3r31149. 3r33720. Parallelization 3r3-31127. 3r31132. 3r31149. 3r33724. How to calculate something in Mathematica in parallel

3r31132. 3r31149. 3r31134. Mathematica has a small set of functions that can perform asynchronous computations on different cores. Only now it is necessary to define with terminology. After all, a running process that represents something similar to a virtual machine in Mathematica is also called a kernel, i.e. Kernel. The Core of Mathematics is an interactive execution environment operating in interpreter mode. Each core takes necessarily one process in the system. Threads in the usual sense of the language does not implement. Accordingly, you need to understand that the kernels in standard use will not have shared memory. Basically, all functions of this type begin on

3r33737. Parallel

3r31061. . The easiest way to calculate something asynchronously:

3r31132. 3r31149. 3r31100. 3r31101. ParallelTable[i^2,{i, 1, 10}]3r31149. 3r31149. (* Out[]: = {? ? ? 1? 2? 3? 4? 6? 8? 100} *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. A number of functions work in a similar way: 3r31132. 3r31149. 3r3-1060. 3r33748. ParallelMap

3r31061. , 3r31060. 3r3752. ParallelDo

3r31061. , 3r31060. 3r3756. ParallelProduct

3r31061. , 3r31060. 3r33737. ParallelSum

3r31061. , 3r31137. 3r31132. 3r31149. 3r31134. There are several ways to verify that this was not actually done on a single core. This is how you can get all the running kernels: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. Kernels[]3r31149. 3r31149. (* Out[]: = {"KernelObject"[1, "local"], , "KernelObject"[N, "local"]} *) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. The list will contain all currently running processes. At the same time, they should also be displayed in the task manager. 3r31137. 3r31132. 3r31149. 3r31134. LaunchKernels[n]3r31136. 3r31061. . As a result,

starts. additionally 3r33848. n cores. And the number of available processor cores can be viewed in the variable

3r33795. $ KernelCount

3r31061. . 3r31137. 3r31132. 3r31149. 3r31134. The functions listed at the beginning produce an automatic distribution of tasks among the processes. However, there is a way to independently send code to run on a specific kernel. This is done using

ParallelEvaluate 3r31061. +

ParallelSubmit 3r31061. :

3r31132. 3r31149. 3r31100. 3r31101. ParallelEvaluate[$KernelID, Kernels[] [[1 ;; 4 ;; 2]]]

3r31149. (* Out[]: = {? 3} *) 3r31114. 3r31132. 3r31149. 3r31134. This set of functions will be enough to be able to parallelize the task of calculating the weight spectrum. 3r31137. 3r31132. 3r31149. 3r33825. Dividing the main loop into parts 3r3826. 3r31132. 3r31149. 3r31134. Check whether the calculations actually occur in parallel. For four physical cores, this means that the calculation on all four cores will take as much time as on one: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {24, 24}]; 3r31149. AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis];] [[1]]

AbsoluteTiming[ParallelEvaluate[WeightSpectrumLinearSubspaceGrayCodeEasy[basis]];] [[1]]

3r31149. (* Out[]: = ???

Out[]: = ??? *) 3r31114. 3r31132. 3r31149. 3r31134. There is a time difference, but not fourfold. So with this, everything is fine. The next step is to figure out how to divide the task into several parts. The most logical and effective is to compute only part of the linear combinations on each core. That is, as a result, each core returns a partial spectrum. But how to divide the list

b [sub] i 3r33847. 3r33848. . After all, it is not a direct sequence! In this case, a function is needed that calculates the value from the Gray Code sequence by index. This is done like this:

3r31132. 3r31149. 3r31100. 3r31101. grayNum[basis_List, index_Integer]: = IntegerDigits[BitXor[index, Quotient[index, 2]], ? Length[basis]]

Grid[Table[{i, Row[grayNum[{{0, 0}, {0, 1}, {1, 1}}, i]]}, {i, ? 7}]] 3r31114. 3r31132. 3r31149. 3r33859. 3r31149. 3r33861. 3r31149. 3r33947. 3r31149. 3r33868. index

3r31149. 3r33868. code

3r31149. 3r3393955.

3r33873. 3r31149. 3r33875. 3r31149. 3r33947. 3r31149. 3r3952. 0

3r31149. 3r3952. 000 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 1

3r31149. 3r3952. 001 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 2

3r31149. 3r3952. 011 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 3 3r3953. 3r31149. 3r3952. 010

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 4

3r31149. 3r3952. 110 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 5

3r31149. 3r3952. 111 3r3953. 3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 6

3r31149. 3r3952. 101

3r31149. 3r3393955. 3r31149. 3r33947. 3r31149. 3r3952. 7

3r31149. 3r3952. 100

3r31149. 3r3393955. 3r31149. 3r3957. 3r31149. 3r3r9959. 3r31132. 3r31149. 3r31134. Now we modify the compiled function so that it counts only a partial spectrum in a certain range of indices of linear combinations:

3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeRange =

Compile[{{basis, _Integer, 2}, {range, _Integer, 1}},

Module[{

n = Dimensions[basis] [[-1]], 3r31149. k = Length[basis], 3r31149. s = Table[0, {n + 1}], 3r31149. currentVector = Table[0, {i, 1, Length[basis[[1]]]}],

m = ? l = 0

},

(* we calculate the first vector and its weight *)

If[range[[1]]=! = ?

currentVector = Mod[Total[basis Reverse[IntegerDigits[BitXor[range[[1]], Quotient[range[[1]]+ ? 2]], ? k]]], 2]; 3r31149. ]; 3r31149. Mod[Total[basis IntegerDigits[BitXor[range[[1]]- ? Quotient[range[[1]]- ? 2]], ? k]], 2]; 3r31149. s[[Total[currentVector]+ 1]]= 1; 3r31149. Do[

m = Log2[BitAnd[-1 - b, b + 1]]+ 1; 3r31149. currentVector = BitXor[currentVector, basis[[m]]]; 3r31149. l = Total[currentVector]+ 1; 3r31149. s[[l]]= s[[l]]+ ?

3r31149. {b, First[range], Last[range]- ? 1}

]; 3r31149. (* Return *) s

], 3r31149. (* additional compilation options, 3r31149. The second can be used only if you have a compiler *) 3r31149. RuntimeOptions -> "Speed", (* CompilationTarget -> "C", *)

CompilationOptions -> {"ExpressionOptimization" -> True}

]; 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. That is, if earlier the function counted all combinations with numbers from 0 to 2

^{ N }-? now this range can be set manually. Now we will try to figure out how to divide this very range into equal parts, depending on the number of available cores: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. partition[{i1_Integer, iN_Integer}, n_Integer]: =With[{dn = Round[(iN - i1 + 1)/n]},

Join[

{{i1, i1 + dn - 1}},

Table[{dn * (i - 1), i * dn - 1}, {i, 2, n - 1}], 3r31149. {{(n - 1) * dn, iN}}

]

] 3r31114. 3r31132. 3r31149. 3r31134. Now, in order to calculate the full spectrum in such a way, it is necessary to calculate it on each of the segments, and then add all the results. For example: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeEasy[{{1, 1}, {1, 1}, {1, 1}}]3r31149. WeightSpectrumLinearSubspaceGrayCodeRange[{{1, 1}, {1, 1}, {1, 1}}, {0, 3}]3r31149. WeightSpectrumLinearSubspaceGrayCodeRange[{{1, 1}, {1, 1}, {1, 1}}, {4, 7}]3r31149. 3r31149. (*

Out[]: = {? ? 4} =

Out[]: = {? ? 2} +

Out[]3r31113. 3r31114. 3r31132. 3r31149. 3r31134. The final step is to send these calculations to different kernels: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. WeightSpectrumLinearSubspaceGrayCodeParallel[basis: {{__Integer}}]: =

With[{

kernels = (If[Kernels[]=== {}, LaunchKernels[]]; Kernels[]), 3r31149. parts = partition[{0, 2^Length[basis]- 1}, Length[Kernels[]]]

},

Total[WaitAll[Table[

ParallelEvaluate[ParallelSubmit[WeightSpectrumLinearSubspaceGrayCodeRange[basis, parts[[$KernelID]]]], kernel],

{kernel, kernels}

]]]

] 3r31114. 3r31132. 3r31149. 3r31134. Here it is necessary to clarify. Such a bunch 3r31060. ParallelEvaluate

+

ParallelSubmit

in order to manually control which core will execute which part of the code. ParallelEvaluate generally cannot figure out how to properly execute asynchronous code and ultimately does it in one thread. In the general case, ParallelSubmit does not allow you to specify the correct core, but selects it automatically. 3r31132. 3r31149. Check if this feature works: 3r3r1137. 3r31132. 3r31149. 3r31100. 3r31101. ListPlot[WeightSpectrumLinearSubspaceGrayCodeParallel[RandomInteger[{0, 1}, {16, 128}]], 3r31149. PlotRange -> All, PlotTheme -> "Web", Filling -> Bottom] 3r31114. 3r31132. 3r31149. 3r31134. 3r31075. 3r31137. 3r31132. 3r31149. 3r31134. And as usual we will look at the difference in the speed of calculations. Since a laptop with a 4-core processor is used, an acceleration of about 4 times is expected. Plus, we must take into account the time for the division of tasks and the addition of the final result:

3r31132. 3r31149. 3r31100. 3r31101. basis = RandomInteger[{0, 1}, {20, 1024}]; 3r31149. AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeEasy[basis];]

AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeParallel[basis];]

3r31149. (*

Out[]: = {??? , Null}

Out[]: = {1.5 , Null}

*) 3r31113. 3r31114. 3r31132. 3r31149. 3r31134. Naturally, with a larger number of processor cores, the difference will be more noticeable. Now let's try to calculate the spectrum of a larger base. I wonder how long it will take? Suppose we assume to increase the size of the basis until one calculation takes more than a minute: 3r31137. 3r31132. 3r31149. 3r31100. 3r31101. spectrums = Block[{i = 1, basis, res}, Reap[

While[True,

i++;

basis = RandomInteger[{0, 1}, {i, i}]; 3r31149. Sow[res = AbsoluteTiming[WeightSpectrumLinearSubspaceGrayCodeParallel[basis]]]; 3r31149. If[res[[1 6 Break[]]

]

] [[-1, -1]]]

3r31149. ListPlot[spectrums[[-1, -1]], 3r31149. PlotLabel-> Row[{"basis len: ", Length[spectrums]+ ? "; time:", Round[spectrums[[-1, 1]], ???], "sec"}],

Filling-> Bottom, PlotTheme -> "Web", PlotRange-> All] 3r31114. 3r31132. 3r31149. 3r31134. 3r31118. 3r31137. 3r31132. 3r31149. 3r31134. The picture clearly shows that in a minute and a half the function can calculate the spectrum for a basis of 29 vectors. This is a very good result, given that the very first option, which does not use compilation, the Gray code, parallelization, is also hardly able to execute everything in a reasonable time. The computation time will be thousands of times longer if even for 15 vectors with dimension 10 the calculation took more than 10 seconds. 3r31137. 3r31132. 3r31149. 3rr31126. Conclusion 3r3-31127. 3r31132. 3r31149. 3r31134. I do not know who and where applies all that was described in the article. Wikipedia says the Gray Code has a practical purpose. I also know that the calculation of spectra is often associated with encryption and some other problems of linear algebra. But, once again, it is worth noting that here I wanted first of all to demonstrate step-by-step solution of the problem and step-by-step application of various kinds of optimizations: improvement of the algorithm itself, use of the language features and use of the hardware capabilities of multi-core processors. I sincerely hope that the article will be useful and interesting. 3r31137. 3r31132. 3r31149. 3r31134. P.S. The author thanks Alexander Bannikov , since he is the initiator in the search for the optimal solution to this problem. 3r31137. 3r31145. 3r31149. 3r31149. 3r31149. 3r31142. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r31143. 3r31149. 3r31145. 3r31149. 3r31149. 3r31149. 3r31149.