_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

Tellegens_Principle

问题

给出一个 m×nm\times n 的矩阵 AA,以及一个用于计算 uAuu\mapsto Au 的(线性的)算法,求一个几乎同样次数乘、同样次加减法的用于计算 vATvv\mapsto A^Tv 的算法。

本篇 Blog 是个人口嗨。

形式描述

我们有一个函数式的计算模型:

一个具有 nn 个输入位和 mm 个输出位的线性算法定义如下:

一个自然数 llll 条以 i=n+1,,n+li=n+1,\dots,n+l 编号的指令:

  • ri=rj+rkr_i=r_j+r_k,其中 1j,k<i1\leq j,k<i
  • ri=αrjr_i=\alpha r_j,其中 α\alpha 是常数,1j<i1\leq j<i

以及一个输出位的映射:f:{1,2,,m}{1,2,,n+l}f:\{1,2,\dots,m\}\to\{1,2,\dots,n+l\}

一个算法计算一个矩阵 Pm×nP_{m\times n} 当且仅当:

对于任意列向量 u=(u1,u2,,un)Tu=(u_1,u_2,\dots,u_n)^T,如果定义:

  • ri=uir_i=u_i,若 ini\leq n
  • 按算法中的描述定义 rir_i,若 i>ni>n

i,rf(i)=(Pu)i\forall i, r_{f(i)}=(Pu)_i

我们需要做的是:给定一个计算 AA 的算法,求一个计算 ATA^T 的算法,要求两者中的乘法次数相同,加法次数相差 mnm-n。我们假定对于 A,ATA,A^T 都不存在恒为 00 的输出。

我们也假设算法里没有“无用变量”,即不出现在后面的计算也不作为输出位的变量。

构造

为了方便表示,我们把变量记做不同的英文字母。我们以 IxI_x(仅出现在前 nn 个位置,占位用)表示 xx 这个变量是输入的;以 OxO_x(仅出现在最后,表示输出位映射)。如下是两对例子:

Ia;Ib;c=2a;d=3b;e=c+d;OeI_a;I_b;c=2a;d=3b;e=c+d;O_e 计算了 (23)\begin{pmatrix}2&3\end{pmatrix}。对应地,Id;a=2d;b=3d;Oa;ObI_d;a=2d;b=3d;O_a;O_b 计算了 (23)\begin{pmatrix}2\\3\end{pmatrix} Ia;Ib;Ic;d=a+b;e=c+d;Oe;OeI_a;I_b;I_c;d=a+b;e=c+d;O_e;O_e 计算了 (111111)\begin{pmatrix}1&1&1\\1&1&1\end{pmatrix}。对应地,Ia;Ib;c=a+b;Oc;Oc;OcI_a;I_b;c=a+b;O_c;O_c;O_c 计算了 (111111)\begin{pmatrix}1&1\\1&1\\1&1\end{pmatrix}

那么我们定义一个算法的转置如下:

  • 将输入变量记为 i1,,imi_1,\dots,i_m
  • 对于原算法中的每个变量 xx,定义一个新变量 xx'
  • 在原算法中每有一条指令 y=αxy=\alpha x,就将 αy\alpha y' 加到 xx' 上(通过定义临时变量);
  • 在原算法中每有一条指令 y=x+zy=x+z,就将 yy 加到 xx 上;
  • 在原算法中每有一条指令 OxO_x(实际上并不是“指令”,这里我们意会一下),就把对应位置的 ii_- 加到 xx 上;
  • 特殊情况:若只存在一条指令用到 xx:如果是乘法指令 y=αxy=\alpha x,那么直接定义 x=αyx'=\alpha y';如果是加法或输出,那么不定义新变量,而是使用相应的变量代替 xx'
  • 新算法中的输出位对应原算法中的输入变量,处理与上述的一般变量相同。

证明

首先我们证明这样定义的转置和原来的乘法、加法次数满足要求:如果原算法中一个变量在 aa 个指令里被作为加数(y=x+xy=x+x 的情况算两遍),bb 个指令里被作为乘数,cc 个位置作为输出,那么在转置中,就会出现 bb 次乘法、以及 a+b+c1a+b+c-1 次加法。所以若原算法中共有 aa 次加法指令和 bb 次乘法指令,那么新算法就会有 2a+b+m(a+b+n)=a+(mn)2a+b+m-(a+b+n)=a+(m-n) 次加法,bb 次乘法。

接下来还要证明新算法正确地计算了 ATA^T。对于原算法一个变量 xx,及一个输出位 ii,定义 fx,if_{x,i} 为 “xxii 的贡献”。严格的说,定义为:若强行将算法中所有在 xx 之前的所有变量置为 00(若 xx 本身为输入变量,则改为把除 xx 外的所有输入变量置为 00),而 xx 置为 11xx 后面的变量照常计算,此时算法的第 ii 个输出位的值。

显然若 tt 为第 jj 个输入变量,则 ft,i=Pj,if_{t,i}=P_{j,i}

对于一个变量 xx,定义 gx,ig_{x,i} 表示当转置算法的第 ii 位输入为 11 而其它为 00 的时候 xx' 的值(如果 xx 是那个“特殊情况”,那么改为代替 xx' 的变量)。因此不难发现若 tt 是原算法第 jj 个输入变量,那么 gt,ig_{t',i} 就表示新算法计算的矩阵中 i,ji,j 位置的值。因此只需证明 ft,i=gt,if_{t,i}=g_{t',i} 即可。

ft,i=gt,if_{t,i}=g_{t',i} 其实是显然的:固定 ii,对于 tt 在原算法中的出现位置从后往前进行归纳,容易证明此结论。

因此,定理成立。