矩阵张量积并行计算

矩阵张量积并行计算
谭国律，刘建涛
（上饶师范学院 数学与计算机系，江西 上饶 334001）
摘
要:在分析矩阵张量积的数学特性的基础上，讨论了矩阵张量积的并行计算问题，提出了几种并行计算模型，并进行
了算法复杂性分析。
关键词:矩阵；张量积；并行算法；计算复杂性
The Parallel Computing on Matrix Tensor Product
，则 Q2
证明 定理2
根据引理1直接验证即可。 设有分块矩阵 A = (Aij )n×n ，B = (B st )m×m ，
其中子块 Aij 和 Bst 均为方阵，则 A ⊗ B 与如下矩阵 置换相似
证毕
对于 m 个 n 阶可逆矩阵 A1 , A2 , Λ , Am ，由[6] 知， (⊗ Ai ) −1 = ⊗ Ai−1 。但对于 n m 阶的大矩阵 ⊗ Ai ，
⊗ Ai 。
i =1 m
第一阶段：按“基本并行算法”，计算 A1 ⊗ A2 ， 并把计算结果记为 B11 ，把 B11 回收到 P 上，然后同 理计算 A3 ⊗ A4 并回收计算结果 B12 。这样共进行
p =1
⊗ A p 。即 ⊗ A p 是一个
p =1
m
m
∏s
p =1
p
行 ∏ t p 列的大矩阵，
p =1
其 α 行 β 列的元素为 ∏ aαp( p ) β ( p ) ，这里
p =1
m
α ∈ Γ( s1 , s 2 , Λ , s m ) ，β ∈ Γ(t1 , t 2 , Λ , t m ) ， 且α, β 均
m i =1
[6]
注意到引理2中的置换矩阵 Q 与那里的 A 和 B 的具体元素无关，而仅与它们的阶数有关。由假设 故存在统一的置换矩阵 Q1 ， 诸 Aij 均为同阶的方阵， 使得 Q1 ( Aij ⊗ B)Q1 = B ⊗ Aij 。所以
Q1 Ο Q1 Ο ( A ⊗ B) Q1 Q1 ( A1n ⊗ B )Q1 Λ Q1 ( Ann ⊗ B )Q1 Q1
i =1 i =1 i =1 m m m
在不知晓它是 m 个 n 阶矩阵的张量积时，要计算它 的逆矩阵就相当困难了。正像文献[5]指出的那样， 矩阵的张量积具有很好的密码学性质。按(1)式计 算 m 个 n 阶矩阵的张量积， 需要进行 (m − 1)n
2m
2 B11 Λ 阵，且 A1 ⊗ A2 = Λ Λ 2 Bn 1 Λ
按字典序排列。 为了记号简单，无特别声明时，以下所提及的 矩阵均为方阵。下面是与本文相关的矩阵张量积的 一些性质。 引理1
[6]
设有矩阵 A = (a ij ) n×m 和 B ，则
2
相关数学原理
引入序列集合
[6]
Γ(n1 , nα = (α (1), Λ , α (m));1 ≤ α (i) ≤ ni , i = 1, Λ , m}
= Q ' ( A ⊗ B )Q = Q −1 ( A ⊗ B )Q 。
(1)
*
本文受到江西省自然科学基金(0411030)资助
证明 1知
首先， A ⊗ B = ( A ⊗ I m )( I n ⊗ B) 。由引理
( A11 ⊗ B pq ) m×m Λ ( A ⊗ n1 B pq ) m×m
证明 （2）
由定理1知
A11 ⊗ B Λ Λ A⊗ B = Λ A ⊗B Λ n1 A1n ⊗ B Λ 。 Ann ⊗ B
对（2）式的右边，把它的第 m + 1 行依次与前面的 行交换，直至换到第2行；第 2m + 1 行依次与前面的 行交换，直至换到第3行；…；第 (n − 1)m + 1 行依次 与前面的行交换，直至换到第 n 行。然后又把它的 第 m + 1 列依次与前面的列交换，直至换到第2列； 第 2m + 1 列依次与前面的列交换，直至换到第3 列；…；第 (n − 1)m + 1 列依次与前面的列交换，直 至换到第 n 列 （这里的行与列号均指绝对行与列号， 即指不分块的行与列号）。这时（2）式的右边就 把变成了如下形式 diag {A,∗} （3） 再对 （3） 式中的*块施行类似的手法， 最终可把 （2） 的右边变成如下形式 diag {A, A, Λ , A} （4） （4）式即为 I m ⊗ A 。以上说明存在一个 nm 阶 置换矩阵 Q ,便得 Q( A ⊗ I m )Q = I m ⊗ A 。 对上面形成的置换矩阵 Q ，同理可证明，它使 得 Q( I n ⊗ B)Q = B ⊗ I n 。所以 Q( A ⊗ I m )( I n ⊗ B)Q) = (Q( A ⊗ I m )Q)(Q( I n ⊗ B)Q = ( I m ⊗ A)( B ⊗ I n ) = B ⊗ A 即 Q( A ⊗ B)Q = B ⊗ A 。 证毕 基于引理2，对于两个矩阵 A 和 B ，若存在置换 矩阵 Q ，使得 QAQ = B ，则称 A 与 B 置换相似。 引理 3
1
引言
其中 s = ∏ s p , t = ∏ t p , aαβ = ∏ aαp( p ) β ( p ) ,简记为
p =1 p =1 p =1
m m
m
m
m
在工程设计、数值代数等领域中，许多的计算 问题最终会归结到矩阵的计算问题，由于此类问题 计算量大，因此有效地进行这类矩阵计算在实际应 用中非常重要，也引起许多学者对这类问题的研究 兴趣。对于矩阵乘并行算法，文献[1]转载了著名 的 Cannon 算法和 Fox 算法，文献[2]论述了 4 种基 于条形划分的矩阵乘并行算法，文献[3]提出了一 种 B 迁移矩阵乘并行算法，文献[4]对分布式环境 下几种矩阵乘并行算法进行了分析与比较，等等。 在文献[5]中，笔者提出了一种基于矩阵张量积的 数据加密方案，在其中利用低阶矩阵通过张量积运 算来构造复杂的高阶矩阵。对于矩阵张量积的计 算，其计算量更大。因此，研究矩阵张量积的高效 快速计算问题显得非常重要。
( B pq ⊗ A1n ) m×m Λ 。 ( B pq ⊗ Ann ) m×m
( B pq ⊗ A11 ) m×m Λ ( B pq ⊗ An1 ) m×m
矩阵的张量积满足结合律，即 所以存在置换 又由于每个 Bst 也是同阶的方阵， 矩阵 Q2 ，使得 Q2 ( Bst ⊗ Aij )Q2 = Aij ⊗ Bst
当 n1 = n2 = Λ = nm = n 时,简记为 Γm,n 。 设有矩阵 A p = (a ijp )s
p ×t p
a11 B a12 B Λ a1m B a 21 B a 22 B Λ a 2 m B 。 A⊗ B = Μ Μ Μ Μ a B a B Λ a B n2 nm n1
第三步： k ← k + 1 ，若 k = m ，则转第四步，否 则转第二步； 第四步：回收计算结果。由定理 1，
m B11 Λ ⊗ Ai = Λ Λ i =1 m Bn 1 Λ m
3
3.1
矩阵张量积的并行计算
基本并行算法
设有 n 阶矩阵 A1 = (aij ) n×n 和 A2 ， n × n 台处理
product, presented some parallel computing models, and analyses the algorithm complexity.
Key words: Matrix; Tensor Product; Parallel Algorithms; Computational Complexity
B1m n Λ 。 m Bnn
按上述方法计算，各处理器上的负载均衡，均 进行了 n 2 + n 2⋅2 + Λ + 2 2 ( m−1) 次乘法，而且各处理器 之间不需通信。当然，这要求各处理器具有相当的 存储能力。
器按二维阵列依次记为 Pij 。由引理1，可按下列方 法计算 A1 ⊗ A2 。 把 A1 的各元素分散分配到各处理器上， aij 分 配到 Pij 上，把 A2 存放到各处理器上，然后在各处 理器上并行计算 aij A2 。 把各处理器上的计算结果回 收即得到 A1 ⊗ A2 。 下面进行算法复杂性分析，为了便于叙述， 略去回收的过程，且仅考虑乘法的执行次数。 在 Pij 上计算 aij ⊗ A2 的时间复杂性是 n 2 ， 从而 并行计算时的代价为 , c(n) = t (n) ⋅ p(n) = n 4 , 加速比 为
Q2 Ο 作置换矩阵 Q = B ⊗ A11 Λ Λ Q Λ B ⊗ A Λ n1 ( A11 ⊗ B pq ) m×m Λ ( An1 ⊗ B pq ) m×m B ⊗ A1n Λ Q = B ⊗ Ann Λ Λ Λ
( A1n ⊗ B pq ) m×m Λ 。 ( Ann ⊗ B pq ) m×m
TAN Guo-lv, LIU Jian-tao (Dept. of Mathematic & Computer, Shangrao Normal College, Shangrao Jiangxi 334001 China)
Abstract: Based on analyzing its mathematical properties, this paper discussed the parallel computing problems of matrix tensor
Λ Λ Λ
( A1n ⊗ B pq ) m×m Λ ( Ann ⊗ B pq ) m×m
(5)
a11 I m a I A ⊗ I m = 21 m Λ a I n1 m