交换开关与矩阵论 李鹏翔 信息与通信工程学院 我看过一篇关于Birkhoff-von Neumann 输入缓冲交换开关的论文， 这篇论文中使用了矩阵的分解法，下面是我对这篇论文中矩阵分解法 的理解以及实践： 假设一个系统有 N 个输入 N 个输出，并且每个输入端都有一个无 限大的缓存器，来保证系统不会在数据突发到达的情况下丢失数据。 在这个系统中时间是离散的，方便保证不同信道输入输出的同步性。 一个时隙中输入与输出是一一对应的，这样，这个交换开关就可以对 应成一个 *N N 的方阵，开对应1、关对应 0 。这样的开关可以为到达 的数据提供一个保证速率的服务，下面是原论文中的一张截图： 在提供保证速率的服务中，涉及到了矩阵的分解，首先给出一个 结论： 

如果一个 *N N 的矩阵 R ， ,i jr 为其第i 行第 j 列的元素，如果有 r i , j j   1 r i , j i   1 ，那么一定存在一组正数 k ( k  1, 2,3  和一组相应的置 K ) ,      N  i 1  N  j 1  换矩阵 kP ( k  1, 2,3  满足 K ) , P k k 。下面是我对分解步骤的总结： K  k 1   R       k 1  K k  1 算法一总结：如果上面提到的 *N N 矩阵 R 的所有元素的和小于 N ，那么一定有其中的一个元素 ( , i  r j 的行和与列和满足 , i n )  r , m j     1  1  ，用 一个新数   1 max[   取代原矩阵( , i r , m j r , i n ] , j 位置上的元素得到新 ) 矩阵 1R 。重复算法一直到新矩阵的所有元素和等于 N ，记为 ~ R ，且有 ~ R K   。 P k k k 1  算法二总结：e 为一个单位列向量，对于算法一中得到的矩阵 ~ R ， , i 2 ~ ( , R ，令 1 i ~ ( i jr 为矩阵 , i 3 i 表示 )N , ~ R 中第i 行第 j ~ k r 1 N  , i i 3 2 有 ~ e R e   K   k k 1  ( P e k )  ( K k 1   ，可得  k ) e   k 1 。 K k 1  算法三总结：对于算法一中得到的矩阵 (1, 2,3 )N 的一个排列，并且满足 ,  0 , k i k ( , 列的元素 ) ，令 1P 代表一个排列 1 i i 对应的置换矩阵，并且令 , )N  1  1min ~ [ k N r   ]kk i , ，则定义一个新矩阵 1R 满足 R 1 ~ R P  。如果 1 1  ，那 1 1 么 1R 为零矩阵。如果 1 1  ，那么将矩阵 1  1 1 R 1 重复算法三。 至此，这样就得到了一组正数 k 和一组相应的置换矩阵 kP 。 原论文中给出了一个例子： 

下面是我自己举出的例子：（见附件） 当算法一做到倒数第二步的时候，最后一个元素所对应的行和与列和 相同，即最后一步同时改变了行和与列和。 当做完算法三后我觉得矩阵中的元素的方差越大，进行的次数会越多， 得到的置换矩阵会越多。 参考文献： Chang C S, Chen W J, Huang H Y. Birkhoff-von Neumann input buffered crossbar switches[C]//INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE, 2000, 3: 1614-1623.