CN103475597A - Network switching scheduling method based on matrix decomposition - Google Patents

Abstract

The invention discloses a network switching scheduling method based on matrix decomposition. In the case that the arrival of business traffic is known, the business matrix with degree m=2 ^r , r being a positive integer greater than 1, and order N is extended The algorithm is expanded into an extended matrix with a degree of 2 and order P=N×m/2. The P-order extended matrix is decomposed by a ring algorithm to obtain a P-order decomposition matrix with a degree of 1, and the P-order decomposition matrix is compressed into a degree of 2. The P/2-order compression matrix of the P/2-order compression matrix is decomposed by the ring algorithm again to obtain the P/2-order decomposition matrix with a degree of 1, and the decomposition matrix is compressed and re-decomposed repeatedly until P/2=N, that is, the decomposition If the order of the matrix is the same as that of the service matrix, the matrix is decomposed, and the decomposed matrix obtained at this time is the connection matrix required for network switching scheduling. The invention is suitable for non-blocking switching network, and for the service matrix whose degree is m= ^2r , where r is a positive integer greater than 1, the simple and easy ring algorithm can be used to decompose the matrix, so as to realize low-complexity network switching scheduling.

Description

A Network Switch Scheduling Method Based on Matrix Decomposition

technical field

The invention belongs to the technical field of network switching scheduling, and more specifically relates to a network switching scheduling method based on matrix decomposition.

Background technique

The multi-level switching structure can provide more switching interfaces to meet a large number of user access, and provide higher bandwidth to meet user service quality, and has become the first choice for large-capacity switching structures. The Multi-Plane and Multi-Stage (MPMS) structure is a special case of the multi-level switching structure, which is the extension of the intermediate module of the multi-level switching structure to the switching plane. Fig. 1 is a schematic diagram of MPMS switching structure. The inside of the plane can be a single-stage space division switch structure or a multi-stage switch structure. According to whether the arrival traffic is known, the switching scheduling algorithm is divided into two different processing methods. If the arrival flow is unknown, the scheduling can be abstracted as a bipartite graph matching problem and solved using a bipartite graph matching algorithm. If the arrival flow is known, the matrix factorization algorithm can be used.

In order to better explain the matrix factorization algorithm, we first define several noun concepts.

Definition 1: The degree of the matrix: The maximum value m of the sum of the elements of each row and the sum of the elements of each column in the matrix is the degree of the matrix. Suppose there is an A×B matrix Matrix[i,j], 0≤i≤A-1, 0≤j≤B-1, the degree of matrix Matrix[i,j] is $\underset{i}{\max }\left(\underset{j=0}{\overset{B-1}{\mathrm{\Σ}}}\mathrm{Matrix}\right[i,j\left]\right)$ and $\underset{j}{\max }\left(\underset{i=0}{\overset{A-1}{\mathrm{\Σ}}}\mathrm{matrix}\right[i,j\left]\right)$ The larger of the two.

Definition 2: Business matrix H _m , where each element H _m [i, j], 0≤i, j≤N-1, represents the number of services whose input module number i is connected to output module number j, and m represents the number of services in the business matrix Degree, that is, the number of intermediate-level modules, represents the maximum number of services that can be supported in the multi-level switching structure; N represents the number of input/output modules. It can be seen that the value of the element H _m [i, j] in the service matrix can only be selected from one of 0, 1, 2...m-1, m. For MPMS, the intermediate module refers to the switching plane.

1≤k≤m，其中每个元素

0≤i,j≤N-1，代表输入模块i是否有业务经过中间级模块k连接到输出模块j，其元素值为1代表有连接，元素值为0代表无连接。其中下标1表示连接矩阵的度，即每个中间级模块k中每个输入模块到每个输出模块最多只存在一个业务。Definition 3: Connectivity Matrix

1≤k≤m, where each element

0≤i, j≤N-1, which means whether the input module i has business connected to the output module j through the intermediate module k, the element value of which is 1 means there is a connection, and the element value is 0 means there is no connection. The subscript 1 indicates the degree of the connection matrix, that is, there is at most one service from each input module to each output module in each intermediate-level module k.

由Hall定理可得知，在无阻塞交换结构中，矩阵分解算法一定能分解出所有的子矩阵。属于无阻塞交换结构有：单级Crossbar（交叉开关矩阵），多级MPMS、Banyan（榕树网络）、Bense、Clos等，均可采用矩阵分解算法进行路由分配。以MPMS为例，如图1所示，MPMS路由调度的第一步就是把输入端到达的业务均匀下发到各个平面。矩阵分解算法对业务矩阵分解得到各个子矩阵，其中每个子矩阵就可以作为MPMS中每个平面的路由设置依据。The basic idea of the matrix decomposition algorithm is to conduct a unified routing assignment for the business under the condition of coordinating the arrival of the global business. Firstly, a business matrix H _m is obtained by statistics according to the arriving global business conditions. The goal of the matrix decomposition algorithm is to assign a unified route to the global business, that is, to decompose the business matrix H _m into m sub-matrices E ₁ ,

It can be known from Hall's theorem that in a non-blocking switching structure, the matrix decomposition algorithm must be able to decompose all sub-matrices. Non-blocking switching structures include: single-stage Crossbar (crossbar switch matrix), multi-stage MPMS, Banyan (banyan network), Bense, Clos, etc., all of which can use matrix decomposition algorithm for routing allocation. Taking MPMS as an example, as shown in Figure 1, the first step of MPMS routing scheduling is to evenly distribute the services arriving at the input end to each plane. The matrix decomposition algorithm decomposes the service matrix to obtain various sub-matrices, and each sub-matrix can be used as the routing setting basis for each plane in the MPMS.

Among the existing matrix decomposition algorithms, represented by the ring algorithm, it is possible to decompose the business matrix into all sub-matrices without rearranging adjustments or backtracking, and its time complexity increases linearly with the number of ports. In the literature [S.Andresen, "The looping algorithm extended to base2t rearrangeable switching networks," IEEE Trans.Commun.vol.COM-25, pp.1057-1063, Oct.1977] Andresen was the first to rearrange non-blocking structures in Using the ring algorithm, the basic steps are to first find an unmarked element in the business matrix and mark it as 0; then find the last unmarked element in the same column and mark it as 1; then find the last unmarked element in the same row and mark it as 0 , if the last unmarked element is not found at this time, reselect the unmarked elements of other rows. The ring algorithm processes the business matrix at one time to obtain two sub-matrices, that is, the ring algorithm is suitable for business matrices with a degree of 2. Its specific implementation steps include:

1≤k≤2，标记连接矩阵中每个元素值

为0。Step 1. Initialize each element H ₂ [i,j] of the service matrix according to the arrival of service traffic, where 0≤i,j≤N-1. Initialize all connectivity matrices

1≤k≤2, mark the value of each element in the connection matrix

is 0.

Step 2. In the business matrix H ₂ , start from element H ₂ [0,0] and traverse each element row by row and column by column.

2.1) If no non-zero elements are found in all rows, the ring algorithm ends.

H₂[i,j]＝0后，重新执行步骤2。2.2) If the element H ₂ [i,j] is found to be non-zero value 2, update the corresponding elements of the connection matrix and business matrix

After H ₂ [i,j]=0, re-execute step 2.

H₂[i,j]＝0后，继续执行步骤3。2.3) If the element H ₂ [i,j] is found to be non-zero value 1, update the corresponding elements of the connection matrix and business matrix

After H ₂ [i, j] = 0, proceed to step 3.

H₂[i,l]＝0，继续执行步骤4；反之则回到步骤2。Step 3. Find the non-zero element value 1 in row i, if the found element H ₂ [i,l] is non-zero value 1, update the corresponding elements of the connection matrix and business matrix

H ₂ [i,l]=0, continue to step 4; otherwise, go back to step 2.

H₂[r,l]＝0，i＝r，返回步骤3；反之则返回步骤2。Step 4. Find the non-zero element value 1 in column l, if the found element H ₂ [r,l] is non-zero value 1, update the corresponding elements of the connection matrix and business matrix

H ₂ [r,l]=0, i=r, return to step 3; otherwise, return to step 2.

根据业务到达是否满配，环形算法处理略有不同。在到达业务满配情况下，业务矩阵H₂每行和每列的元素之和都等于常数2，那么环形算法整个处理过程以环的起点开始，并以环的起点结束，从步骤4回到步骤2开始寻找下一个环开始的起点，直到步骤2中未找到非零元素才结束环形算法。在到达业务非满配情况下，业务矩阵H₂每行每列的元素之和小于或等于常数2，同样可以采用环形算法处理。在环遍历矩阵中，若出现从步骤3或4回到步骤2时的列（或行）并不是起始列（或行），那么一个环的处理还需从起始列（或行）的反方向开始遍历环，直到再次回到步骤2才开始寻找下一个环开始的起点，直到步骤2中未找到非零元素才结束环形算法。下面以满配业务矩阵H₂为例，对环形算法的实现步骤进行说明。It can be seen that the ring algorithm selects a starting point in step 2, then executes loop jumps between steps 3 and 4, and finally returns to the starting point. The ring algorithm processes the business matrix H ₂ to get two sub-matrices

Depending on whether the service arrival is fully configured, the ring algorithm process is slightly different. In the case of reaching full service allocation, the sum of elements in each row and column of the service matrix H ₂ is equal to a constant 2, then the entire processing process of the ring algorithm starts with the starting point of the ring and ends with the starting point of the ring, and returns from step 4 to Step 2 starts to look for the starting point of the next ring, and the ring algorithm ends when no non-zero element is found in step 2. In the case that the arrival business is not fully matched, the sum of the elements in each row and column of the business matrix H ₂ is less than or equal to the constant 2, which can also be processed by the ring algorithm. In the loop traversal matrix, if the column (or row) when returning from step 3 or 4 to step 2 is not the starting column (or row), then the processing of a loop needs to start from the starting column (or row) Start traversing the ring in the opposite direction, and start looking for the starting point of the next ring until you return to step 2 again, and end the ring algorithm until no non-zero element is found in step 2. The implementation steps of the ring algorithm are described below by taking the fully configured service matrix H ₂ as an example.

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="h"\; filenames="HDA0000374495750000011.png,HDA0000374495750000012.png"\; state="\{\{state\}\}">h</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

首先，执行步骤2寻找到一个非零值1作为环开始的起点Start，箭头指向代表了处理顺序，最终回到起始点一个环遍历结束End，再执行步骤2寻找下一个环的起点。从图2可看出，由于此处的业务矩阵H₂为满配矩阵，因此在一个环遍历完成之后，已经把矩阵中的非零元素处理完，所以就寻找不到下一个环的起点，环形算法分解结束。Fig. 2 is a schematic diagram of processing the business matrix H ₂ by the ring algorithm. As shown in Figure 2, the ring algorithm processes the business matrix in Figure 2, and the labels "①, ②" respectively represent the two connection matrices assigned to

First, perform step 2 to find a non-zero value 1 as the starting point of the ring, the arrow points to represent the processing order, and finally return to the starting point and end the loop traversal End, then perform step 2 to find the starting point of the next ring. It can be seen from Figure 2 that since the business matrix H ₂ here is a fully-matched matrix, after the completion of a ring traversal, the non-zero elements in the matrix have been processed, so the starting point of the next ring cannot be found. The ring algorithm decomposition ends.

In large-capacity switching structures, such as MPMS and multi-stage switching structures that support multiple time slots, they are non-blocking switching structures. Matrix decomposition algorithms can be used for routing. The calculated degree of the service matrix is equal to the number of planes and the number of time slots. However, the ring algorithm is limited by the degree of business matrix being 2. In order to overcome this limitation, people have done a lot of research to find a matrix decomposition strategy whose degree of business matrix is greater than 2. However, most of the matrix decomposition strategies obtained in later studies require backtracking or rearrangement adjustments, which are separated from the ring algorithm, and the algorithm implementation complexity is too high to be realizable.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the prior art and provide a low-complexity network switching scheduling method based on matrix decomposition. For non-blocking switching networks, the satisfaction degree m=2 ^r , where r is a positive integer greater than 1 Matrix, the connection matrix is obtained through matrix decomposition, and the network switching scheduling is realized.

In order to realize the above-mentioned purpose of the invention, the present invention is based on matrix decomposition network switching dispatching method, is characterized in that comprising:

S1: The number of input modules and output modules in the network is both N. According to the arrival of business traffic, the N-order business matrix H _m is obtained statistically, where m represents the degree of the business matrix H _m and satisfies the power of 2, that is, m= 2 ^r , r is a positive integer greater than 1; each element H _m [i,j] of the business matrix H _m represents the number of services connected from input module i to output module j, and the value range of i, j is 0≤i ≤N-1,0≤j≤N-1;

S2: Use the extension algorithm to extend the business matrix H _m to obtain a P-order extension matrix M ₂ with a degree of 2, where P=N×m/2; M ₂ [x,y] represents the elements in the extension matrix M ₂ , the value range of x, y is 0≤x≤P-1, 0≤y≤P-1;

此时分解矩阵个数K＝2；S3: Use the ring algorithm to decompose the extended matrix M ₂ , and decompose to obtain two P-order decomposition matrices

At this time, the number of decomposition matrices K=2;

k＝1,2,…,K进行压缩，得到K个度为2的P/2阶压缩矩阵

S4: Use the compression algorithm to decompose the K P-order matrix respectively

k=1,2,...,K for compression, get K P/2 order compression matrices with degree 2

中的每个压缩矩阵分别进行矩阵分解，得到2K个分解矩阵

S5: Use the ring algorithm again to compress K matrices

Each compressed matrix in is decomposed separately to get 2K decomposed matrices

的阶数P/2是否等于业务矩阵阶数N，如果等于，矩阵分解结束，得到网络交换调度的连接矩阵

如果不等于，令P＝P/2，K＝2K，返回步骤S4。S6: Judgment decomposition matrix

Is the order P/2 of the business matrix equal to the order N of the business matrix? If so, the matrix decomposition ends, and the connection matrix of network switching scheduling is obtained.

If not, set P=P/2, K=2K, and return to step S4.

Wherein, in the step S2, the extended algorithm includes:

初始化所有计数器为0；初始化扩展矩阵M₂中每个元素M₂[x,y]＝0；S2.1: Each row and column of the business matrix H _m corresponds to a flag number R _i , L _j , and all flag numbers are initialized to 0; each row and column of the extended matrix M ₂ corresponds to a counter

Initialize all counters to 0; initialize each element M ₂ [x,y]=0 in the extended matrix M ₂ ;

S2.2: Traverse each element H _m [i, j] in the business matrix H _m row by row, if H _m [i, j] is zero, go to step S2.6, if H _m [i, j] is a non-zero value, enter step S2.3;

判断计数器是否等于2，如果不是，不作任何操作，如果是，标志数R_i＝R_i+1并更新x；同时判断计数器

是否等于2，如果不是，不作任何操作，如果是，标志数L_j＝L_j+1并更新y；进入步骤S2.4；S2.3: order

judgment counter Whether it is equal to 2, if not, do nothing, if yes, mark number R _i =R _i +1 and update x; at the same time judge the counter

Whether it is equal to 2, if not, do not do any operation, if yes, sign number L _j =L _j +1 and update y; enter step S2.4;

H_m[i,j]＝H_m[i,j]-1；S2.4: let M ₂ [x,y]=M ₂ [x,y]+1, update the counter

_Hm [i,j]= _Hm [i,j]-1;

S2.5: Determine whether H _m [i, j] is 0, if not 0, repeat step S2.3; if it is 0, enter step S2.6;

S2.6: Determine whether the elements of the business matrix H _m have been traversed. If not, return to step S2.2 to traverse the next element. If the traverse is completed, the expansion of the business matrix ends.

按两行两列进行分块，得到P/2阶的分块矩阵，将分块矩阵中的每个子矩阵替换为子矩阵中所有元素的和，得到P/2阶压缩矩阵

Wherein, the specific method of the compression algorithm in step S4 is: decompose matrix

Block by two rows and two columns to obtain a block matrix of order P/2, replace each sub-matrix in the block matrix with the sum of all elements in the sub-matrix, and obtain a compressed matrix of order P/2

The network switching scheduling method based on matrix decomposition of the present invention, in the case of known traffic arrival, expands the business matrix with degree m= ^2r , r being a positive integer greater than 1, and order N into degree It is an expansion matrix of 2, order P=N×m/2, decompose the P-order expansion matrix using a ring algorithm to obtain a P-order decomposition matrix with a degree of 1, and compress the P-order decomposition matrix into a P/2 with a degree of 2 The first-order compression matrix is decomposed by the ring algorithm on the P/2-order compression again to obtain the P/2-order decomposition matrix with a degree of 1, and the decomposition matrix is compressed and re-decomposed repeatedly until P/2=N, that is, the decomposition matrix and the business matrix If the order is the same, the matrix decomposition is completed, and the decomposition matrix obtained at this time is the connection matrix required for network switching scheduling. The present invention is applicable to non-blocking switching networks, breaks through the limitation of ring algorithm on the service matrix degree of 2, and does not need to perform backtracking, rearrangement adjustment and other complex algorithms, but uses ring algorithm, service matrix expansion, and decomposition matrix The combination of compression enables the business matrix whose degree is m=2 ^r , where r is a positive integer greater than 1, to be decomposed by a simple ring algorithm, thereby realizing low-complexity network switching scheduling.

Description of drawings

Fig. 1 is a schematic diagram of MPMS switching structure;

Fig. 2 is the processing schematic diagram of ring algorithm to business matrix H ₂ ;

Fig. 3 is a kind of specific implementation flow chart of the network switching scheduling method based on matrix decomposition of the present invention;

Fig. 4 is a flow chart of a specific implementation of the service matrix extension algorithm.

Detailed ways

Specific embodiments of the present invention will be described below in conjunction with the accompanying drawings, so that those skilled in the art can better understand the present invention. It should be noted that in the following description, when detailed descriptions of known functions and designs may dilute the main content of the present invention, these descriptions will be omitted here.

Fig. 3 is a flow chart of a specific embodiment of the network switching scheduling method based on matrix decomposition in the present invention. As shown in Figure 3, the specific implementation steps of the present invention include:

S301: The number of input modules and output modules in the network is N, and according to the arrival of business traffic, an N-order business matrix H _m is obtained through statistics, where each element H _m [i,j], 0≤i≤N-1 , 0≤j≤N-1 indicates the number of services connected from input module i to output module j, m indicates the degree of the service matrix, and m=2 ^r , r is a positive integer greater than 1, that is, the present invention only targets the degree m =2 ^r , r is a service matrix of a positive integer greater than 1.

S302: Expand the business matrix H _m by using the expansion algorithm to obtain a P-order expansion matrix M ₂ with a degree of 2, P=N×m/2, M ₂ [x,y], 0≤x, y≤P-1 is an element in the expansion matrix _M2 .

Fig. 4 is a flow chart of a specific implementation of the service matrix extension algorithm. As shown in Figure 4, the business matrix extension algorithm includes steps:

初始化所有计数器为0；初始化扩展矩阵M₂中每个元素M₂[x,y]＝0；初始化i＝0,j＝0。S401: Each row and column of the business matrix H _m corresponds to a flag number R _i and L _j , and all flag numbers are initialized to 0; each row and column of the extended matrix M ₂ corresponds to a counter

Initialize all counters to 0; initialize each element M ₂ [x,y]=0 in the extended matrix M ₂ ; initialize i=0, j=0.

S402: Determine whether the element H _m [i, j] is zero, if H _m [i, j] is zero, go to step S410, if H _m [i, j] is non-zero, go to step S403.

5403: order $x=i\&times;\frac{\mathrm{<figure-callout\; id="2"\; label="m"\; filenames="HDA0000374495750000011.png,HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}{2}+R_i,$ $\mathrm{the\; y}=j\&times;\frac{\mathrm{<figure-callout\; id="2"\; label="m"\; filenames="HDA0000374495750000011.png,HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}{2}+L_j,$ Go to steps S404 and S406.

是否等于2，如果不是，不作任何操作，直接进入步骤S408；如果是，进入步骤S405。S404: Judgment counter

Whether it is equal to 2, if not, do not perform any operation, and directly go to step S408; if yes, go to step S405.

进入步骤S408。S405: number of flags R _i =R _i +1, update

Go to step S408.

是否等于2，如果不是，不作任何操作，直接进入步骤S408；如果是，进入步骤S407。S406: Judgment counter

Whether it is equal to 2, if not, do not perform any operation, and directly go to step S408; if yes, go to step S407.

进入步骤S408。S407: number of flags L _j =L _j +1, update

Go to step S408.

H_m[i,j]＝H_m[i,j]-1。S408: Let M ₂ [x,y]=M ₂ [x,y]+1, update the counter

_Hm [i,j]= _Hm [i,j]-1.

S409: Determine whether H _m [i, j] is 0, if not 0, return to step S403, if it is 0, enter step S410.

S410: Determine whether j=N-1, if not, it means that the elements of this row have not been traversed, and go to step S411; if yes, it means that the elements of this row have been traversed, and go to step S412.

S411: j=j+1, that is, traverse the next element in the row, and return to step S402.

S412: i=i+1, j=0, that is, enter the next line to start traversing, and enter step S413.

S413: Determine whether i=N, if not, it means that all elements of the business matrix H _m have not been traversed yet, return to step S402, and traverse the next element; if yes, it means that all elements of the business matrix H _m have been traversed, then the business Matrix expansion is over.

By adopting the business matrix extension algorithm from step S401 to step S413, the business matrix H _m with degree m can be expanded into an extended matrix M 2 with degree ₂ .

此时分解矩阵个数K＝2。S303: Decompose the extended matrix M ₂ using the ring algorithm, and decompose to obtain two P-order decomposition matrices

At this time, the number of decomposition matrices K=2.

k＝1,2,…,K进行压缩，得到K个度为2的P/2阶压缩矩阵

S304: Using a compression algorithm to decompose the K P-order matrices respectively

k=1,2,...,K for compression, get K P/2 order compression matrices with degree 2

按两行两列进行分块，得到P/2阶的分块矩阵，将分块矩阵中的每个子矩阵替换为子矩阵中所有元素的和，得到P/2阶压缩矩阵

The specific method of the compression algorithm is: decompose the matrix

Block by two rows and two columns to obtain a block matrix of order P/2, replace each sub-matrix in the block matrix with the sum of all elements in the sub-matrix, and obtain a compressed matrix of order P/2

中的每个压缩矩阵分别进行矩阵分解，得到2K个分解矩阵 S305: Using the ring algorithm again to compress the K matrices

Each compressed matrix in is decomposed separately to get 2K decomposed matrices

的阶数P/2是否等于业务矩阵阶数N，如果等于，矩阵分解结束，网络交换调度的连接矩阵

如果不等于，令P＝P/2，K＝2K返回步骤S304。S306: Determine the decomposition matrix

Is the order P/2 of the business matrix equal to the order N of the business matrix? If so, the matrix decomposition ends, and the connection matrix of the network switching scheduling

If not, set P=P/2, K=2K and return to step S304.

Example

The implementation process of the present invention will be described below by taking the fully configured service matrix H ₄ with degree m=2 ² =4 and order N=8 as an example.

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="4"\; label="h"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">h</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

The service matrix H ₄ is extended by using the extension algorithm proposed by the present invention to obtain an extension matrix M ₂ with degree 2 and order P=N×m/2=16. An input arrow indicates that a row is abstracted into two rows, and an output arrow indicates that a column is abstracted into two columns.

It can be seen that the degree ₂ of the extended matrix M is 2, which meets the requirements of the ring algorithm, and can be directly decomposed by the ring algorithm, and K=2 decomposition matrices can be obtained after decomposition

${\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 16,1</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccccccccccc}\mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$ ${\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccccccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

进行压缩处理。以

为例，按照本发明提出的压缩算法，将

按两行两列进行分块，得到8阶的分块矩阵，将分块矩阵中的每个子矩阵替换为子矩阵中所有元素的和，得到8阶压缩矩阵

Next, for the decomposition matrix

Perform compression processing. by

For example, according to the compression algorithm proposed by the present invention, the

Block by two rows and two columns to obtain an 8-order block matrix, replace each sub-matrix in the block matrix with the sum of all elements in the sub-matrix, and obtain an 8-order compressed matrix

得到的压缩矩阵

为：Similarly, we can decompose the matrix

The resulting compression matrix

for:

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="m"\; filenames="HDA0000374495750000011.png,HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; 8,2</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

的度为2，适用于环形算法。接下来，分别对两个压缩矩阵

进行再次环形算法分解，得到4个分解矩阵

It can be seen that the two compression matrices obtained after compression

The degree of 2 is suitable for the ring algorithm. Next, for the two compression matrices respectively

Decompose the ring algorithm again to get 4 decomposition matrices

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 8,1</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$ ${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 8,2</span>}}\text{<span class="notranslate"> =</span>}\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 8,3</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$ ${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 8,4</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]$

At this time, the order of the four decomposition matrices is 8, which is consistent with the order of the service matrix _H4 , the matrix decomposition is completed, and the connection matrix for network switching scheduling ${\mathrm{E.}}_1^k=m_1^{P/2,k},$ Right now ${\mathrm{E.}}_1^1={\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,1}},$ ${\mathrm{E.}}_1^2={\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,2}},$ ${\mathrm{E.}}_1^3={\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,3}},$ ${\mathrm{E.}}_1^4={\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,4}}.$ It can be known that the business matrix obtained from the original statistics $h_{}$${}_4={\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,1}}+{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,2}}+{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,3}}+{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="HDA0000374495750000012.png"\; state="\{\{state\}\}">m</figure-callout>}}_1^{\mathrm{8,4}},$ Therefore, it can be seen that the connection matrix can be successfully obtained by using the present invention.

压缩为4个度为2的4阶压缩矩阵再对这4个压缩矩阵采用环形算法进行分解，即可得到8个度为1的4阶分解矩阵从而完成矩阵分解。If the order of the business matrix is 4, and the order of the decomposition matrix obtained at this time is 8, the 4 decomposition matrices need to be reprocessed. That is, four 8th-order decomposition matrices with a degree of 1

Compressed into 4 degree 2 compressed matrices of order 4 Then for these 4 compression matrices Using the ring algorithm to decompose, you can get 8 4th-order decomposition matrices with degree 1 This completes the matrix decomposition.

Although the illustrative specific embodiments of the present invention have been described above, so that those skilled in the art can understand the present invention, it should be clear that the present invention is not limited to the scope of the specific embodiments. For those of ordinary skill in the art, As long as various changes are within the spirit and scope of the present invention defined and determined by the appended claims, these changes are obvious, and all inventions and creations using the concept of the present invention are included in the protection list.

Claims (3)

1. the network exchange dispatching method based on matrix decomposition, is characterized in that, comprises the following steps:

S1: in network, the number of input module and output module is N, according to service traffics, arrives situation, and statistics obtains N rank traffic matrix H _m, wherein, m means traffic matrix H _mdegree and to meet 2 power exponent be m=2 ^r; Traffic matrix H _meach element H _m[i, j] means that input module i is connected to the business number of output module j, i, and the span of j is 0≤i≤N-1,0≤j≤N-1;

S2: adopt expansion algorithm to traffic matrix H _mexpanded the P rank extended matrix M that degree of obtaining is 2 ₂, wherein, P=N * m/2; M ₂[x, y] means extended matrix M ₂in element, x, the span of y is 0≤x≤P-1,0≤y≤P-1;

S3: adopt circle algorithm to extended matrix M ₂carry out matrix decomposition, decompose and obtain two P rank split-matrixes

split-matrix number K=2 now;

S4: adopt compression algorithm respectively to K P rank split-matrix

k=1,2 ..., K is compressed, and obtains the P/2 rank condensation matrix that K degree is 2

S5: again adopt circle algorithm to K condensation matrix

in each condensation matrix carry out respectively matrix decomposition, obtain 2K condensation matrix

S6: judgement split-matrix

exponent number P/2 whether equal traffic matrix exponent number N, if equal, matrix decomposition finishes, and obtains the connection matrix of network exchange scheduling

if be not equal to, make P=P/2, K=2K, return to step S4.

2. network exchange dispatching method according to claim 1, is characterized in that, in described step S2, expansion algorithm comprises:

S2.1: traffic matrix H _mthe corresponding conventional number R of every row, every row _i, L _j, all conventional numbers of initialization are 0; Extended matrix M ₂the corresponding counter of every row, every row

the all counters of initialization are 0; Initialization extended matrix M ₂in each element M ₂[x, y];

S2.2: travel through line by line traffic matrix H _min each element H _m[i, j], if H _m[i, j] is null value, enters step S2.6, if H _m[i, j] is nonzero value, enters step S2.3;

S2.3: order

the judgement counter

whether equal 2, if not, do not do any operation, if so, conventional number R _i=R _i+ 1 and upgrade x; Judge counter simultaneously

whether equal 2, if not, do not do any operation, if so, conventional number L _j=L _j+ 1 and upgrade y; Enter step S2.4;

S2.4: make M ₂[x, y]=M ₂[x, y]+1, refresh counter

h _m[i, j]=H _m[i, j]-1;

S2.5: judgement H _mwhether [i, j] is 0, if be not 0, and repeating step S2.3; If 0, enter step S2.6;

S2.6: judgement traffic matrix H _melement whether travel through completely, if do not travel through completely, return to step S2.2 traversal next element, if travel through completely, the traffic matrix expansion finishes.

3. network exchange dispatching method according to claim 1 and 2, is characterized in that, the concrete grammar of the compression algorithm in described step S4 is: by split-matrix

carry out piecemeal by two row two row, obtain the matrix in block form on P/2 rank, by each submatrix in matrix in block form replace with all elements in submatrix and, obtain P/2 rank condensation matrix

Images