矩阵乘法与矩阵加速

矩阵乘法

矩阵乘法比较简单,就是两个矩阵相乘得到一个新矩阵的运算.

乘法的过程就是:

第一个矩阵的每一行和第二个矩阵的每一列对应位置相乘相加,放入新矩阵.

不太显然,矩阵乘法对于参与运算的矩阵是有限制的:

$$[n\times m] * [m\times k] = [n\times k]$$

即,一个 $n\times m$ 的矩阵和一个 $m\times k$ 的矩阵相乘得到一个 $n \times k$ 的矩阵.

必须是形如上面那样的矩阵才能进行乘法.

从这里可以看出,一般的矩阵乘法是不满足交换律的.(个别情况除外)

显然,一次矩阵乘法的复杂度是 $\Theta(n\times m\times 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 ;
}

十分简单!

矩阵加速

根据一些资料,我们知道矩乘的本质是向量卷积,方程代换和线性变换.

由此得到启发,能否用矩阵来转移递推方程? 答案是肯定的.

以 $Fibonacii$ 数列的递推为例,我们来考虑构造转移矩阵.

众所周知, $Fibonacii$ 数列的递推式是 $f_n=f_{n-1}+f_{n-2}$.

可以发现, $Fibonacii$ 的递推只和某一项的前两项相关.

所以我们考虑的矩阵应该是 $2\times 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] \times \left[\begin{array}{ll}{a} & {b} \ {c} & {d} \end{array}\right] = \left[\begin{array}{l}{f_{i+1}} \ {f_{i}}\end{array}\right] $$

根据矩阵乘法的过程,可以得到:

$$a\times f_i + c \times f_{i-1} = f_{i+1}$$

$$b\times f_i + d \times 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]$$

一次转移就乘一次转移矩阵,自行判断幂次即可.

矩阵加速递推的扩展

咕咕咕…