矩阵乘法与优化

这篇具有很好参考价值的文章主要介绍了矩阵乘法与优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

矩阵乘法

0 1
1 1

这是一个矩阵,那么我要让它乘以一个这样的矩阵

1 0
0 1

那么它的结果就是

0 1
1 1

如果乘以它自身,那么它的结果就是

1 1
1 2

那么矩阵乘法的公式就应该是

(此图为网图,侵权可以私信我)

可以发现,矩阵乘法的单位元应该是

1 0 0
0 1 0
0 0 1

后面的以此类推

因为对于当前行的每一列都会都会乘以一个对应的数,那么当前列要保留的数所对应的位置就应该是 \(1\),那么经过猜测推算就可以得出上述矩阵。

另外矩阵乘法满足结合律,证明我也不会 (T﹏T)。

矩阵乘法优化递推

斐波那契数列

斐波那契数列你显然可以用 \(O(n)\) 的时间求出来,递推即可。
但是如果 \(n\)\(1e18\) 你就炸开了,所以需要一种方法优化线性的时间复杂度。
由于 \(f_i = f_{i - 1} + f_{i - 2}\) 那么可以变成从 \([f_{i - 2}, f_{i - 1}]\)\([f_{i - 1}, f_{i}]\) 的这样一个过程,我们发现这个其实是个矩阵,其中 \(i\) 是要求和的,而其它的不要保留第一个即可,那么可以由上面讲的矩阵乘法的单位元和斐波那契数列的递推公式来推出斐波那契数列的这个变化用的矩阵应该是

0 1
1 1

由于下面还要用,所以将该矩阵设为 \(x\)

所以我们就可以知道 \(f_i\) 怎么求了,那么可以得出任何数的求法,可是还是 \(O(n)\) 的,我们看看式子就明白了怎么做:

\([f_i, f_{i + 1}] = ((([f_1, f_2] \times x) \times x) \times \dots \dots ) \times x\)

由于满足结合律可以拆括号为

\([f_i, f_{i + 1}] = [f_1, f_2] \times x \times x \times \dots \dots \times x\)

还能简化为

\([f_i, f_{i + 1}] = [f_1, f_2] \times x^i\)
那么就很好算了呀,代码如下

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

const int MaxN = 110, mod = 1e9 + 7;

struct A {
  int n, m;
  ll a[MaxN][MaxN];

  A() {
    fill(a[1], a[MaxN], 0);
  }

  void build() {
    for (int i = 1; i < MaxN; i++) {
      a[i][i] = 1;
    }
  }

  void init() {
    for (int i = 1; i < m; i++) {
      a[i + 1][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
      a[i][m] = 1;
    }
  }

  A operator*(const A &b) const {
    A c;
    c.n = n, c.m = b.m;
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        for (int j = 1; j <= b.m; j++) {
          c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
        }
      }
    }
    return c;
  }
} a, c;

ll n, m = 2;

A qpow(A a, ll b) {
  A res;
  res.build(), res.n = a.n, res.m = a.m;
  for (ll i = 1; i <= b; i <<= 1) {
    if (b & i) {
      res = res * a;
    }
    a = a * a;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  a.n = 1, a.m = m;
  a.a[a.n][a.m] = 1;
  c.n = c.m = m, c.init();
  c = qpow(c, n), a = a * c;
  cout << a.a[1][m] << '\n';
  return 0;
}

那么如果是 \(f_i = f_{i - 1} + f_{i - 2} + \dots \dots + f_{i - m}\)
那么我们其实可以理解为斐波那契数列的扩展,那么同样的我们可以得到变化是要乘的矩阵应该是,对于每个 \(i\)\([i + 1, i]\) 为一,且第 \(m\) 列全为 \(1\)

代码如下

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

const int MaxN = 110, mod = 1e9 + 7;

struct A {
  int n, m;
  ll a[MaxN][MaxN];

  A() {
    fill(a[1], a[MaxN], 0);
  }

  void build() {
    for (int i = 1; i < MaxN; i++) {
      a[i][i] = 1;
    }
  }

  void init() {
    for (int i = 1; i < m; i++) {
      a[i + 1][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
      a[i][m] = 1;
    }
  }

  A operator*(const A &b) const {
    A c;
    c.n = n, c.m = b.m;
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        for (int j = 1; j <= b.m; j++) {
          c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
        }
      }
    }
    return c;
  }
} a, c;

ll n, m;

A qpow(A a, ll b) {
  A res;
  res.build(), res.n = a.n, res.m = a.m;
  for (ll i = 1; i <= b; i <<= 1) {
    if (b & i) {
      res = res * a;
    }
    a = a * a;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  a.n = 1, a.m = m;
  a.a[a.n][a.m] = 1;
  c.n = c.m = m, c.init();
  c = qpow(c, n), a = a * c;
  cout << a.a[1][m] << '\n';
  return 0;
}

P2106 Sam数

思路

首先考虑暴力求解,我们设 \(dp_{ij}\) 表示,考虑到第 \(i\) 位,而当前位为 \(j\),那么对于这种状态,我们很快就能想到一种转移:

\(dp_{ij}=\sum\limits_{k=j-2}^{j+2}dp_{i-1k}\)

然后我们会发现这样子不管是时间还是空间,都是会爆的,因为这题线性都不行,那么我们就需要矩阵乘法优化,我们发现一点,\(i\) 层的答案将会是所有可能性的和,那么我们可以设计矩形状态为 \(f_{i0}~f_{i9}\)表示 \(i\) 层,的所有可能状态,然后问么就可以推测出单位矩正为多少,然后快速幂计算即可文章来源地址https://www.toymoban.com/news/detail-478618.html

code

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

const int MaxN = 20, mod = 1000000007;

struct A {
  int n, m;
  ll a[MaxN][MaxN];

  A() {
    fill(a[0], a[MaxN], 0);
  }

  void build() {
    for (int i = 0; i < MaxN; i++) {
      a[i][i] = 1;
    }
  }

  void init() {
    for (int i = 0; i <= n; i++) {
      for (int j = max(i - 2, 0); j <= min(i + 2, m); j++) {
        a[i][j] = 1;
      }
    }
  }

  A operator*(const A &b) const {
    A c;
    c.n = n, c.m = b.m;
    for (int i = 0; i <= n; i++) {
      for (int k = 0; k <= m; k++) {
        for (int j = 0; j <= b.m; j++) {
          c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
        }
      }
    }
    return c;
  }
} a, c;

ll n, m = 9, ans;

A qpow(A a, ll b) {
  A res;
  res.build(), res.n = a.n, res.m = a.m;
  for (ll i = 1; i <= b; i <<= 1) {
    if (b & i) {
      res = res * a;
    }
    a = a * a;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  a.n = 0, a.m = m;
  for (int i = 0; i <= m; i++) {
    a.a[0][i] = 1;
  }
  c.n = c.m = m, c.init();
  c = qpow(c, n - 1), a = a * c;
  for (int i = 1; i <= m; i++) {
    ans = (ans + a.a[0][i]) % mod;
  }
  cout << ans + (n == 1) << endl;  // 如果位数是1的话那么前导0不是前导了
  return 0;
}

到了这里,关于矩阵乘法与优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 高性能计算的矩阵乘法优化 - Python + OpenMP实现

    关于上一节读者某些疑问 :为什么你用进程并行不是线程并行? 回答 :由于Python解释器有GIL(全局解释器锁),在单进程的解释器上有线程安全锁,也就是说每次只能一个线程访问解释器,因此Python在语法上的多线程(multithreads)实现是不会提高并行性能的。 这一点和C

    2024年02月15日
    浏览(66)
  • 高性能计算的矩阵乘法优化 - Python +MPI的实现

    本次实验的目的是使用MPI的并行性来进行矩阵乘法优化,本人使用 Python 实现 实验硬件: CPU :AMD Ryzen 7 5800H(3.20 GHz) 内存 :32GB (3200MHz) 要求 :使用一个矩阵,一个向量相乘,分别用单进程和多进程的mpi接口实现。 全局的规模参数是 Scale 数据示例 : 当 Scale=5 时,数据示例如

    2023年04月22日
    浏览(98)
  • 高性能计算实验——矩阵乘法基于MPI的并行实现及优化

    熟练掌握MPI编程方法,并将通用矩阵乘法转为MPI并行实现,进一步加深MPI的使用与理解。 进一步熟悉MPI矩阵乘法的实现,学习MPI点对点通信与集合通信的异同点和各自的优缺点,学会比较二者的性能以及各自使用的情形。 学习如何将自己编写的代码改造为标准库函数,供其

    2024年02月03日
    浏览(50)
  • FPGA HLS Matrix_MUL 矩阵乘法的计算与优化

    设置clock,10表示一个周期10ns,带宽100M vivado工具比较保守,计算需要的延迟是14,实际优化可以在10,设置大一点,优化的计算更多,一般约束设置大一点在30-50 选择开发板 xc7z020clg400-1 Source:描述功能模块的cpp和h代码 Test Bench:测试代码的 main.cpp matrix_mul.h #ifndef __xxxx__ #def

    2024年02月09日
    浏览(42)
  • 论文阅读:矩阵乘法GEMM的cache优化,子矩阵的切分方法Anatomy of High-Performance MatrixMultiplication

    矩阵乘法优化的知名论文goto paper: 矩阵乘法的优化需要将矩阵切分成子矩阵,用子矩阵相乘的结果组合为原矩阵相乘的结果: 上图是拆分矩阵的方法,M表示矩阵,X方向和Y方向的两个维度都是未知的。P表示横条或竖条,X方向或Y方向有一个方向的维度是极小的。B表示block块

    2024年02月16日
    浏览(53)
  • 【矩阵乘法】C++实现外部矩阵乘法

    ​ 使用文件和内存模拟系统缓存,并利用矩阵乘法验证实际和理论情况。 设计一个 Matrix 类,其中 Matrix 是存在磁盘中的一个二进制文件,类通过保存的矩阵属性来读取磁盘。前八个字节为两个 int32 ,保存矩阵的行列数。 Matrix中有一个 buffer 成员为读取到的数据缓存,通过

    2024年02月11日
    浏览(35)
  • python矩阵乘法全面解读,python矩阵乘法常用代码

      矩阵乘法,顾名思义是矩阵的乘法,矩阵相乘的含义是两个向量的积,在 Python中一般以乘号或括号表示。与常用的加、减、乘、除运算不同,矩阵乘法只能用于对给定矩阵进行乘法运算,不能进行除法运算。若要计算矩阵乘法的值,必须先进行矩阵分解。 在上一篇文章中

    2024年02月08日
    浏览(38)
  • 【单元测试】测还是不测,这是一个问题

    这篇文章也可以在我的博客中查看 相信大家从小就被千叮万嘱要做单元测试。然后秉承这一信念,成为了一个测试狂魔。凡有代码,测!覆盖!最终,一波操作猛如虎:467测试,0错误, 0自信 。 第二天。 你为了优化,颤抖着手更改了一行代码。果不其然发现牵连了 1e9 个测

    2024年02月03日
    浏览(47)
  • 矩阵乘法(矩阵乘矩阵)

    首先理了解矩阵是什么: 矩阵是一个按照长方阵列排列的复数或实数集合。(相信大家都懂) 关于矩阵的基本概念: 1.方阵:n 阶方阵 (正方形嘛) 2.同型矩阵:两个矩阵,行数与列数对应相同,称为同型矩阵 矩阵加减法: 在了解矩阵乘法前先看看矩阵加减法: 1.两个矩阵

    2024年02月08日
    浏览(51)
  • 矩阵算法之矩阵乘法

    矩阵算法在图像处理、神经网络、模式识别等领域有着广泛的用途。 在矩阵乘法中,A矩阵和B矩阵可以做乘法运算必须满足A矩阵的列的数量等于B矩阵的行的数量。 运算规则:A的每一行中的数字对应乘以B的每一列的数字把结果相加起来。 1、当矩阵A的列数(column)等于矩阵

    2024年02月11日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包