矩阵乘法算法笔记首页友邻广播我的豆瓣我的小组我的小站-vixra.pdf

豆瓣社区 豆瓣读书 豆瓣电影 豆瓣音乐 豆瓣同城 豆瓣FM 更多    首页 友邻广播 我的豆瓣 我的小组 我的小站 矩阵乘法算法笔记 2012­06­11 12:17:49 （一 ）双线性复杂度 考虑具有如下一般形式的问题 ：输入变量为域 F 中的元素 X1 , … , Xm ，设计算法输出  f (X1 , … , Xm ), … , f (X1 , … , Xm )，其中 f , … f  为  F 上的多项式。不加说明的话默认  1 n 1 n F = C。 举例 ： 1. (矩阵乘法)  n fi,k (A, B) = ∑Aij Bjk , 1 ≤ i, k ≤ n. j=1 2. (离散 Fourier 变换)  n f (X) = ∑ωij X , i = 1, … , n i j j=1 其中 ω 为 n 次单位根 (n­th root of unity)。 3. (一元多项式乘法)  f (X, Y) = ∑ X Y , i = 0, … , n − 1. i j k j,k:j+k=i 这里“算法”指算术线路 (arithmetic circuit)，即采用 F 上的二元运算加减乘除为运算门的线路 （当然算 法和线路是有区别的 ，但这里先不作区分 ）。一般用运算门的数量来衡量线路大小或者说算法的复杂 度。有时也会将加减和数乘操作忽略不计 ，具体视上下文而定。 显然减法可 以用加法 以及数乘代替 ，下面的定理说明在某种意义上也可 以忽略掉除法 ： 定理 1.1 ([Str73]) ： 计算   阶多项式的大小为 s 的 (+, ×, /)­线路可用大小为 s O(1) 的 (+, ×)­线路代替。 证明 ：原线路的每一个运算门都计算一个有理函数 f/g。在构造的新线路中将其转化为两个运算门， 分别计算 f 和 g。这一步是 自底向上地作的。 具体地说 ，考虑一个运算门，设其操作数为 a/b 和 c/ 。在新线路中 a, b, c,  已经被计算。若该运算 门为加法 ，则输出为 (a + bc)/b 。在新线路中计算 a + bc 和 b ，需要4个运算 ；若该运算门为 乘法 ，则输出为 ac/b 。在新线路中计算 ac 和 b ，需要2个运算 ；若该运算门为除法 ，则输出为  a /bc。在新线路中计算 a  和 bc ，需要2个运算。 这样在新线路中只在顶端输出的位置有除法运算 f = g/h，而线路大小增加至多常数因子。下面把这 些除法也去掉 ： 取 α1 , … , αn ∈ Fn 使得 h(α1 , … , αn ) = c ≠ 0。令  ′ −1 g (X1 , X2 , … , Xn ) = (c ) ⋅ g(X1 + α1 , … , Xn + αn ) 以及  ′ −1 ′ h (X1 , X2 , … , Xn ) = (c ) ⋅ h(X1 + α1 , … , Xn + αn )，则 h (0, … , 0) = 1