cenbo's Blog

工作总结一

又一轮论文投稿结束了。浑浑噩噩的生活突然有了实感，这可能就是劳动体现人的类本质。

赶截止日期的体验还是不好受。之前初次线下参会结果感染新冠郁郁寡欢，养了几天病，又花心思玩原神，所以拖延严重。最后拓展的部分直到三天前才写对，根本没有时间给杰森打磨。导师说这部分估计没人看还是挺伤心的。

看着改完的论文感觉自己还是差得太远了。赶紧总结一下论文中别人干的活。任务分配是考虑到我干不了这些活，所以这也是我缺乏的能力。

明志

博士者，人类最高之学位；攻读者必有志于学问，此亦易明。然今公共之舆论，于博士多作劝退：历时少则四年，多则七年，大好青春，束之书阁；除少数工科专业外，得利与代价相较甚微；又经济无着，需家境优渥者方可安心学习。此皆庸俗之言，不足为训，然亦有公允之处。故欲读博士者，不仅需有志于学问，还需有足够理由盖过此种劝退意见。我今将去虎狼之国，吃枪子染瘟疫而不辞，此必明志而后行。

我起于中学之信息学竞赛，大学入学堂班；学堂班专为培养基础科学人才而设也。所学之课，多研理论。时有显学，曰机器学习，业界牟利之奇术也，而斥之为炼丹。今大学毕业已逾两年。欲为程序员，而不知工业程序模式，又懒于玖玖陆，故工作三月而辞去；若为竞赛教练，又觉竞赛得奖复教竞赛，实似庞氏骗局。何不愿为其它职业？实乃家庭与同学皆近小布尔乔亚知识分子，我亦染其习气，欲维持阶级地位。若无体面工作，不如在家啃老，尚可文饰为准备留学。幸得贵人相助，大学之毕设成果发表于顶会，成绩亦为之改观。思学术若为庞氏骗局，亦其大者，君子当为。复申请，则录取。

我中学时慕东洋，后访问四月，见其文化之野蛮、社会之排外，则茫然无所依靠。于今观之，寄托于虚构之物，其信息量小，不足以承载人生。亦有信息量大者，宗教也，不足法。我向亦渴求他人之认可，然性孤僻自私，知己难求。圣人有言，万物皆备于我，若去除蒙蔽，致其中和，此心即是天理，不待他人评判。此至善矣，心向往之，然非有坚强之意志不可至。或许心智之成熟尚需时日。所谓力行近乎仁，人的正确思想，只能从社会实践中来。

加冠成人，身负责任。博学不可使议世，劳思不可以补民，君子恶之，何况不学无术、形丑体弱者乎！观吾同侪：有热爱竞赛，浸淫其中而不离者，杜兄是也，我若为之，必不如杜兄；有算法工程师，范兄是也，我若学工，或可为之；有文学青年高洁者，郑兄是也，我若学文，亦不可为；有学术天才，陈君是也，我若为之，必不如陈君。此皆有志之士，我从陈。

我将往虎狼之国，惟愿能体现价值。若科研经年，有高级文明如《乡村教师》中者，判决贡献足以偿还生存教育之消耗，则吃枪子染瘟疫而无憾。决心不惑于互联网之恶意，求学问志在学问，素夷狄行乎夷狄，以报吾妹之恩，以慰卢兄之灵。

快速矩阵乘法一

新开一个系列，学习一下平时视作黑箱略过的基础技术。如果经常用一些知名结论却不懂证明思路，恐怕也不够格自称理论计算机科学家。由于是现学现卖，内容会比较肤浅。假定读者的水平和我差不多，即学了微积分线性代数的~~小学二年级~~学生。内容以翻译为主，原文在文末“教材”中列出。中文知识不足处会使用非标准直译术语。

一、简单结论

今有二矩阵 \(x\in F^{n\times k}, y\in F^{k\times m}\), 求\(z=xy\in F^{n\times m}\), \(z_{ij}=\sum_k x_{ik} y_{kj}\). 元素假定是在域\(F\)里. 暴力算是\(O(n^3)\). 直觉上每一项都挺必要的, 但是也有冗余信息.

众所周知\(2\times 2\)分块就可以做到更好. 可以用七次乘法代替八次, 虽然不太直观:
\[\begin{align*} p_1 &= (x_{11}+x_{22})(y_{11}+y_{22})\\
p_2 &= (x_{21}+x_{22})y_{11}\\
p_3 &= x_{11}(y_{12}-y_{22})\\
p_4 &= x_{22}(y_{21}-y_{11})\\
p_5 &= (x_{11}+x_{12})y_{22}\\
p_6 &= (x_{21}-x_{11})(y_{11}+y_{12})\\
p_7 &= (x_{12}-x_{22})(y_{21}+y_{22})\\
z_{11} = x_{11}y_{11}+x_{12}y_{21} &= p_1+p_4-p_5+p_7\\
z_{12} = x_{11}y_{12}+x_{12}y_{22} &= p_3+p_5\\
z_{21} = x_{21}y_{11}+x_{22}y_{21} &= p_2+p_4\\
z_{22} = x_{21}y_{12}+x_{22}y_{22} &= p_1+p_3-p_2+p_6
\end{align*}\]
我们将\(x, y\)分成四个边长减半的小矩阵, 然后递归计算七个小矩阵乘, 再进行加减即可得到\(z\)的四个部分. 时间的递归式为\(T(n)=7T(\frac{n}{2})+O(n^2)\), 解得\(T(n)=O(n^{\log 7})=O(n^{2.807})\).

该方法[地]记作简单分块乘. 从中也可以看出, 递归时只有乘法的次数影响时间复杂度, 加减法可以忽略不计.

生活中常用的常数\(\omega\)意为两个\(n\times n\)矩阵相乘需要时间\(O(n^\omega)\). 二〇二〇年现在其值为2.3728639[玄]. 本系列试图让自己相信这个值是对的.

二、张量模型

简单分块乘算式虽繁, 细究可见从\(x, y\)到\(p\)是双线性, 从\(p\)到\(z\)是线性. 张量长于刻画多线性, 有助于深刻地分析此类计算方式.

下面我们把\(x, y\)拍扁, 随即需要记录拍扁后哪些项相乘. 拍扁后的下标代换为\(\kappa=(j, i), \mu=(i, k), \nu=(k, j)\). 记录乘法规则的三阶张量\(t\)定义如下. 若\(\kappa, \mu, \nu\)表示的\(i, j, k\)相容, 则\(t_{\kappa\mu\nu}\)为1, 否则为0. 从而\[z_\kappa=\sum_\mu\sum_\nu t_{\kappa\mu\nu}x_\mu y_\nu.\]

再用拍扁的下标重写简单分块乘.
\[p_\lambda = (\sum_\mu u_{\lambda\mu} x_\mu)(\sum_\nu v_{\lambda\nu} y_\nu)\]
\[z_\kappa = \sum_\lambda w_{\lambda\kappa} p_\lambda = \sum_{\lambda\mu\nu} w_{\lambda\kappa} u_{\lambda\mu} v_{\lambda\nu} x_\nu y_\nu\]
与定义式对照即得\(t_{\kappa\mu\nu}=\sum_\lambda w_{\lambda\kappa} u_{\lambda\mu} v_{\lambda\nu}\). 把\(w_\lambda, u_\lambda, v_\lambda\)看作向量, 张量\(t=\sum_\lambda w_\lambda \otimes u_\lambda \otimes v_\lambda\). 张量\(t\)的秩\(R(t)\)是\(t\)分解成独立张量积的最少个数, 不超过上式中\(\lambda\)的个数.

由上面推导可得, 已知秩为\(R\)的张量分解可以写出\(R\)次乘法的计算方式, 已知计算方式也可以写出张量分解. 其实此言稍有问题, 因为计算的时候并非只能将\(x\)的线性组合与\(y\)的线性组合相乘, 还可以算\(x, y\)的线性组合再乘. 不过这样的计算方式也可以写成两个张量分解的和, 因为\(z\)中只有\(x_\mu y_\nu, y_\mu x_\nu\)项没有\(x_\mu x_\nu, y_\mu y_\nu\)项. 总之\(t\)的秩与所需乘法次数差不多，从而也反映了计算时间。

现在我们只需研究矩阵乘张量\(t\). \(t\)只依赖于维度, 记作\(\langle n,k,m\rangle\), 秩记作\(R(n,k,m)\). 第一节实际上说的就是\(R(2,2,2)\le 7\). \(t\)的定义对于\(\kappa, \mu, \nu\)是对称的, 从而对\(i, j, k\)也是对称的. 一个直接的推论是, 如果我们调换\(n,k,m\)的次序, \(t\)只要换一下下标位置就能用同样的方法分解. 于是\(R(n,k,m)\)与\(n,k,m\)的顺序无关.

\(k\times m\times n\)维张量\(t\)与\(k'\times m'\times n'\)维张量\(t'\)的张量积\(s=t\otimes t'\)是\((kk')\times (mm')\times (nn')\)维张量， \(s_{\kappa\kappa', \mu\mu', \nu\nu'}=t_{\kappa\mu\nu} t'_{\kappa'\mu'\nu'}\). 张量积是线性的, 将\(t\)的分解与\(t'\)的分解相乘可得\(s\)的分解, 展开后共\(R(t)R(t')\)项. 故\(R(t\otimes t')\le R(t)R(t')\).

张量积可以用来构造更大的矩阵乘张量. 对于\(<n,k,m>\)与\(<n',k',m'>\)的张量积, \((\kappa\kappa', \mu\mu', \nu\nu')\)相容当且仅当\((\kappa, \mu, \nu)\)与\((\kappa', \mu', \nu')\)都相容, 故\(<n,k,m>\otimes<n',k',m'>\)与\(<nn',kk',mm'>\)是同一个张量. 将低维度的秩相乘, 即知高维度的秩的上界. 特别地, 当\(R(k,m,n)\le r\), \(R(kmn, kmn, kmn)\le\)\(R(k,m,n)R(m,n,k)R(n,k,m)\le r^3\). 于是\(\omega\le 3\log_{kmn} r\), 因为递归式将会变成\(T(N)=r^3T(N/kmn)+O(n^2)\).

三、边界秩

线性代数中, 我们面对高秩矩阵时常用奇异值分解来得到近似的低秩矩阵. 对张量也想要以容忍近似为代价降低秩.

将秩分解中的\(w, u, v\)用多项式环\(F[\epsilon]\)上的向量代替. 每个数现在都看作多项式. 若存在\(r\)组多项式向量的张量积之和是\(\epsilon^h t+O(\epsilon^{h+1})\), 记\(R_h(t)=r\). 这里的\(O(\epsilon^{h+1})\)表示只含有次数高于\(h\)的项, 也就是假装\(\epsilon\)是个无穷小量. 令\(\underline{R}(t)\)为最小的\(R_h(t)\), 称为边界秩.

边界秩可以作为秩的上界. 存在依赖于\(h\)的常数\(c_h\le {h+2 \choose 2}\), \(R(t)\le c_hR_h(t)\). 这是因为, 一旦得到\(\epsilon^h t+O(\epsilon^{h+1})\)的秩分解, 我们只考虑乘积中\(\epsilon^h\)的项就能求\(t\). 而三个多项式相乘时只有\({h+2 \choose 2}\)组系数的积对\(h\)次项有贡献. 总之\(r\)组多项式向量可以转化为\({h+2 \choose 2}r\)组向量.

现在看看靠近似降低秩的效果. 考虑\(2\times 2\)矩阵乘\(2\times 3\)矩阵. 易知\(R(2,2,3)\le 11\), 七个与第一节中\(\langle 2,2,2\rangle\)的相同，四个用来暴力计算剩下两项. 下面证明\(R_1(2,2,3)\le 10\).

\[\begin{align*} p_1 &= (x_{12}+\epsilon x_{22})y_{21}\\
p_2 &= x_{11}(y_{11}+\epsilon y_{12})\\
p_3 &= x_{12}(y_{11}+y_{21}+\epsilon y_{22})\\
p_4 &= (x_{11}+x_{12}+\epsilon x_{21})y_{11}\\
p_5 &= (x_{12}+\epsilon x_{21})(y_{11}+\epsilon y_{22})\\
\epsilon z_{11} &= \epsilon p_1+\epsilon p_2+O(\epsilon^2)\\
\epsilon z_{12} &= p_2 - p_4+ p_5+O(\epsilon^2)\\
\epsilon z_{21} &= p_1 - p_3+ p_5+O(\epsilon^2)
\end{align*}\]
\(z_{33}, z_{32}, z_{22}\)的计算与\(z_{11}, z_{12}, z_{21}\)对称, 可以通过类似定义\(p_6\)至\(p_{10}\)表出.

\(R_h\)满足\(R_{h+h'}(t\otimes t')\le R_h(t)R_{h'}(t')\), 这只需将两个分解式相乘即可看出. 于是我们有\(R_3(12,12,12)\le R_1(2,2,3)^3=1000\). 不仅如此, \(R_{3s}(12^s)\le 1000^s\). 故\(R(12^s) \le c_{3s} R_{3s}(12^s) \le 1000^s c_{3s}\).
\[\omega\le \log_{12^s} (1000^s c_{3s}) \le \log_{12} 1000 + \frac{\ln {3s+2 \choose 2}}{s\ln 12} \to 3\log_{12} 10 (s\to\infty)\]

也就是说\(\omega\le 2.780\). 于是我们超越了简单分块乘, 虽然只有一点点.

至于更强的结果，请听下回分解。