矩阵乘法与矩阵加速

矩阵乘法与矩阵加速

矩阵乘法

矩阵乘法⽐较简单,就是两个矩阵相乘得到⼀个新矩阵的运算.乘法的过程就是:

第⼀个矩阵的每⼀⾏和第⼆个矩阵的每⼀列对应位置相乘相加,放⼊新矩阵.不太显然,矩阵乘法对于参与运算的矩阵是有的:\\[[n\imes m] * [m\imes k] = [n\imes k] \\]

即,⼀个 \\(n\imes m\\) 的矩阵和⼀个 \\(m\imes k\\) 的矩阵相乘得到⼀个 \\(n \imes k\\) 的矩阵.必须是形如上⾯那样的矩阵才能进⾏乘法.

从这⾥可以看出,⼀般的矩阵乘法是不满⾜交换律的.(个别情况除外)显然,⼀次矩阵乘法的复杂度是 \\(\\Theta(n\imes m\imes k)\\) 的.两个矩阵相乘的代码如下:

struct Matrix {

LL e[N][M] , line , row ;

inline void clear () { line = row = 0 ; MEM ( e , 0 ) ; return ; }

friend Matrix operator * (Matrix a , Matrix b) {

Matrix c ; c.clear () ; c.line = a.line ; c.row = b.row ;

rep ( k , 0 , a.row - 1 ) rep ( i , 0 , a.line - 1 ) rep ( j , 0 , b.row - 1 ) c.e[i][j] = ( c.e[i][j] + a.e[i][k] * b.e[k][j] % mod ) % mod ; return c ; }} ;

上⾯的代码采⽤了结构体的封装形式,⽤起来更⽅便.矩阵快速幂

有了矩阵乘法,我们再来考虑和乘法密切相关的⼀种运算:幂运算.

即⼀个矩阵的若⼲次幂如何计算,显然,只有正⽅形的矩阵可以计算⾼次幂.那么类⽐于实数幂次,⼀个矩阵的 \\(p\\) 次幂只需要把它⾃乘 \\(p\\) 次即可.讨论到了幂运算的问题,就不得不提快速幂.

众所周知,快速幂的复杂度是 \\(\\Theta(log_2{P})\\) 的,其中 \\(P\\) 是模数.这样的复杂度实在令⼈眼馋,相⽐于⾃乘若⼲次快了不知道多少倍.那矩阵的幂次也可以像快速幂那样分治处理吗?

我们知道矩阵乘法是不满⾜交换律的,那么它满⾜结合律吗?如果它满⾜结合律,那么它就可以像快速幂那样运算.事实上,矩阵乘法是满⾜结合律的.于是矩阵快速幂的代码也出炉了:

inline Matrix quick (Matrix a , LL p) {

Matrix c ; c.clear () ; c.line = a.line ; c.row = a.row ; rep ( i , 0 , c.line - 1 ) c.e[i][i] = 1 ; while ( p ) {

if ( p & 1 ) c = c * a ; a = a * a ; p >>= 1 ; }

return c ;}

⼗分简单!矩阵加速

根据⼀些资料,我们知道矩乘的本质是⾼维向量卷积,⽅程代换和线性变换.由此得到启发,能否⽤矩阵来转移递推⽅程? 答案是肯定的.以 \\(Fibonacci\\) 数列的递推为例,我们来考虑构造转移矩阵.众所周知, \\(Fibonacci\\) 数列的递推式是 \\(f_n=f_{n-1}+f_{n-2}\\).可以发现, \\(Fibonacci\\) 的递推只和某⼀项的前两项相关.所以我们考虑的矩阵应该是 \\(2\imes 2\\) 的.

我们的初始矩阵是这样的:

\\[\\left[\\begin{array}{ll}{f_i}&{f_{i-1}}\\end{array}\\right] \\]⽽⽬标矩阵是这样的:

\\[\\left[\\begin{array}{ll}{f_{i+1}}&{f_{i}}\\end{array}\\right] \\]所以转移矩阵长这样:

\\[\\left[\\begin{array}{ll}{a} & {b} \\\\ {c} & {d} \\end{array}\\right] \\]我们要的矩阵转移式就是这样的:

\\[\\left[\\begin{array}{ll}{f_{i}} \\\\ {f_{i-1}} \\end{array}\\right] \imes \\left[\\begin{array}{ll}{a} & {b} \\\\ {c} & {d}\\end{array}\\right] = \\left[\\begin{array}{l}{f_{i+1}} \\\\ {f_{i}}\\end{array}\\right] \\]根据矩阵乘法的过程,可以得到:

\\[a\imes f_i + c \imes f_{i-1} = f_{i+1} \\]\\[b\imes f_i + d \imes f_{i-1} = f_{i} \\]显然,\\(a=1,c=1,b=1,d=0\\).于是,转移矩阵为:

\\[\\left[\\begin{array}{ll}{1} & {1} \\\\ {1} & {0} \\end{array}\\right] \\]初始矩阵\\(emmmm...\\),不就是这个嘛

\\[\\left[\\begin{array}{l} {1} & {1} \\end{array}\\right] \\]⼀次转移就乘⼀次转移矩阵,⾃⾏判断幂次即可.矩阵加速递推的扩展\\(updated:\\)

扩展情况并不多,⼀般只是两个递推的组合,常数项的累加以及前缀和,其实本质都是递推组合.就都以 \\(Fibonacci\\) 数列为例好了.扩展 1 带常数项

定义数列 \\(F_n\\) 的递推式为 \\(F_n=F_{n-1}+F_{n-2}+1\\) , 其中 \\(F_1 = F_2 = 1\\).没有常数项的部分就是⼀个普通的 \\(Fibonacci\\) 数列.

我们令 \\(g_n\\) 表⽰常数项的递推式,显然, \\(g_n=g_{n-1}\\).

于是我们的初始矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} & F_{n-1} & g_n \\end{array}\\right] \\]⽬标矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n+1} & F_n & g_{n+1}\\end{array}\\right] \\]那么我们要的转移矩阵应该满⾜ \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} \\\\ F_{n-1} \\\\ g_n \\end{array}\\right] \imes \\left[\\begin{array}{llll} ? & ? & ? \\\\ ? & ? & ? \\\\ ? & & \\end{array}\\right] = \\left[\\begin{array}{llll} F_{n+1} \\\\ F_n \\\\ g_{n+1}\\end{array}\\right] \\]根据上⾯构造矩阵的⽅法,可以得到,转移矩阵长这个样⼦ \\(:\\)

\\[\\left[\\begin{array}{llll} 1 & 1 & 0 \\\\ 1 & 0 & 0 \\\\ 1 & 0 & 1 \\end{array}\\right] \\](因为这些扩展的意义就在于构造不同的矩阵,所以只讲如何构造矩阵).扩展 2 带未知项递推

定义数列 \\(F_n\\) 的递推式为 \\(F_n=F_{n-1}+F_{n-2}+n\\) , 其中 \\(F_1=F_2=1\\).没有常数项的部分就是⼀个普通的 \\(Fibonacci\\) 数列.令 \\(g_n\\) 表⽰未知项的递推式,显然, \\(g_n=g_{n-1}+1\\).于是我们的初始矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} & F_{n-1} & g_n & 1 \\end{array}\\right] \\]⽬标矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n+1} & F_n & g_{n+1} & 1 \\end{array}\\right] \\]

那么我们要的转移矩阵应该满⾜ \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} \\\\ F_{n-1} \\\\ g_n \\\\ 1 \\end{array}\\right] \imes \\left[\\begin{array}{llll} ? & ? & ? & ? \\\\ ? & ? & & \\\\ & & & \\\\ & & & \\end{array}\\right] = \\left[\\begin{array}{llll} F_{n+1} \\\\ F_n \\\\ g_{n+1} \\\\ 1\\end{array}\\right] \\]

根据上⾯构造矩阵的⽅法,可以得到,转移矩阵长这个样⼦ \\(:\\)

\\[\\left[\\begin{array}{llll} 1 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 1 & 0 & 1 & 1 \\end{array}\\right] \\]扩展 3 递推式的组合

令数列 \\(F_n\\) 的递推式为 \\(F_n=F_{n-1}+F_{n-2}+f_{n-1}+f_{n-2}\\),其中,\\(F_1=F_2=f_1=f_2=1\\).这叫啥?双重 \\(Fibonacci\\) 数列?算了,还是不乱叫了.于是我们的初始矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} & F_{n-1} & f_n & f_{n-1} \\end{array}\\right] \\]⽬标矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n+1} & F_n & f_{n+1} & f_n \\end{array}\\right] \\]那么我们要的转移矩阵应该满⾜ \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} \\\\ F_{n-1} \\\\ f_n \\\\ f_{n-1} \\end{array}\\right] \imes \\left[\\begin{array}{llll} ? & ? & ? & ? \\\\ ?& ? & ? & ? \\\\ ? & ? & ? & ? \\\\ ? & ? & ? & ? \\end{array}\\right] = \\left[\\begin{array}{llll} F_{n+1} \\\\ F_n \\\\ f_{n+1} \\\\ f_n\\end{array}\\right] \\]

根据上⾯构造矩阵的⽅法,可以得到,转移矩阵长这个样⼦ \\(:\\)

\\[\\left[\\begin{array}{llll} 1 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\\\ 1 & 0 & 1 & 1 \\\\ 1 & 0 & 1 & 0 \\end{array}\\right] \\]扩展 4 前缀和

令数列 \\(F_n\\) 的递推式为 \\(F_n=F_{n-1}+F_{n-2}\\) , 求 \\(\\sum_{i=1}^{n}{F_i}\\) , 其中 \\(F_1=F_2=1\\).令 \\(S_i\\) 表⽰到 \\(i\\) 的前缀和.则显然有\\(:\\)

\\[S_i=F_{i-1}+F_{i-2}+S_{i-1} \\]于是我们的初始矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} & F_{n-1} & S_n \\end{array}\\right] \\]⽬标矩阵就是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n+1} & F_n & S_{n+1} \\end{array}\\right] \\]那么我们要的转移矩阵应该满⾜ \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} \\\\ F_{n-1} \\\\ S_n\\end{array}\\right] \imes \\left[\\begin{array}{llll} ? & ? & ? \\\\ ? & ? & ? \\\\ ? & & \\end{array}\\right] = \\left[\\begin{array}{llll} F_{n+1} \\\\ F_n \\\\ S_{n+1} \\end{array}\\right] \\]根据上⾯构造矩阵的⽅法,可以得到,转移矩阵长这个样⼦ \\(:\\)

\\[\\left[\\begin{array}{llll} 1 & 1 & 1 \\\\ 1 & 0 & 1 \\\\ 0 & 0 & 1 \\end{array}\\right] \\]扩展 5 带系数

令数列 \\(F_n\\) 的递推式为 \\(F_n = a\imes F_{n-1} + b\imes F_{n-2}\\),其中 \\(F_1,F_2\\) 是给定的数.初始矩阵仍然是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_n & F_{n-1} \\end{array}\\right] \\]⽬标矩阵仍然是 \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n+1} & F_{n} \\end{array}\\right] \\]那么我们要的转移矩阵应该满⾜ \\(:\\)

\\[\\left[\\begin{array}{llll} F_{n} \\\\ F_{n-1} \\end{array}\\right] \imes \\left[\\begin{array}{llll} ? & ? \\\\ ? & ? \\end{array}\\right] =\\left[\\begin{array}{llll} F_{n+1} \\\\ F_n \\end{array}\\right] \\]根据上⾯构造矩阵的⽅法,可以得到,转移矩阵长这个样⼦ \\(:\\)

\\[\\left[\\begin{array}{llll} a & 1 \\\\ b & 0 \\end{array}\\right] \\]完结撒花 \\(!\\)

你说为什么这⼏种扩展的框架⼀模⼀样?因为我复制的啊...(懒关于矩乘更有意思的应⽤,我还有另⼀篇博⽂