C#,数值计算,矩阵相乘的斯特拉森(Strassen’s Matrix Multiplication)分治算法与源代码

Volker Strassen

矩阵乘法

矩阵乘法机器学习中最基本的运算之一,对其进行优化是多种优化的关键。通常,将两个大小为N X N的矩阵相乘需要N^3次运算。从那以后,我们在更好、更聪明的矩阵乘法算法方面取得了长足的进步。沃尔克·斯特拉森于1969年首次发表了他的算法。这是第一个证明基本O(n^3)运行时不是optiomal的算法。

Strassen算法的基本思想是将A和B分为8个子矩阵,然后递归计算C的子矩阵。这种策略称为分而治之。

2 伪代码

  1. 如上图所示,将矩阵A和B划分为大小为N/2 x N/2的4个子矩阵。
  2. 递归计算7个矩阵乘法。
  3. 计算C的子矩阵。
  4. 将这些子矩阵组合到我们的新矩阵C中

3 复杂性

  1. 最坏情况时间复杂度:Θ(n^2.8074)
  2. 最佳情况时间复杂度:Θ(1)
  3. 空间复杂度:Θ(logn)

年青时正在发愁的  Volker Strassen

4 算法的详细解释

矩阵相乘在进行3D变换的时候是经常用到的。在应用中常用矩阵相乘的定义算法对其进行计算。这个算法用到了大量的循环和相乘运算,这使得算法效率不高。而矩阵相乘的计算效率很大程度上的影响了整个程序的运行速度,所以对矩阵相乘算法进行一些改进是必要的。

        我们先讨论二阶矩阵的计算方法。

        对于二阶矩阵

        a11    a12                    b11    b12    
        A =    a21    a22    B =    b21    b22
        先计算下面7个量(1)

        x1 = (a11 + a22) * (b11 + b22);
        x2 = (a21 + a22) * b11;
        x3 = a11 * (b12 - b22);
        x4 = a22 * (b21 - b11);
        x5 = (a11 + a12) * b22;
        x6 = (a21 - a11) * (b11 + b12);
        x7 = (a12 - a22) * (b21 + b22);
        再设C = AB。根据矩阵相乘的规则,C的各元素为(2)

        c11 = a11 * b11 + a12 * b21
        c12 = a11 * b12 + a12 * b22
        c21 = a21 * b11 + a22 * b21
        c22 = a21 * b12 + a22 * b22
        比较(1)(2),C的各元素可以表示为(3)

        c11 = x1 + x4 - x5 + x7
        c12 = x3 + x5
        c21 = x2 + x4
        c22 = x1 + x3 - x2 + x6

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/457378.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

速卖通安全测评补单技术提升运营安全性

对于一个新品来说,最大的问题就是评论。没有评论,你的广告就不能打的很靠前,那样你的转化率就会非常低,数据也很差。新品运气不好的来两个一星差评,链接可能就此废掉,做不上去了。所以虽然平台管的非常的严…

从根到叶:深度理解哈希表

​​​​​​​ 一.哈希表的概念 关于查找元素时: 在顺序结构以及平衡树 中,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) ,平衡树中…

MySQL 系统变量查看与设置(System Variables Configuration)

MySQL中有大量的系统变量控制服务器的行为,大部分的系统变量是不需要我们调整的,保持默认即可。但为了获得更高的性能和稳定性,有时需要适当对部分变量进行调整,本文总结了MySQL中系统变量的查看与设置方法。 目录 一、变量的类型…

学点Java打小工——Day2Day3一点作业

1 猜数字(10次机会) 随机生成[1,1000]的一个数,输入你猜的数程序会给出反馈,直到猜对或次数用尽(10次)。 //猜数字 10次机会Testpublic void guessNumber() {Random random new Random();// [0, 1000) 1// [1, 1000]int num ra…

SQLiteC/C++接口详细介绍之sqlite3类(六)

快速前往文章列表:SQLite—系列文章目录 上一篇:SQLiteC/C接口详细介绍之sqlite3类(五) 下一篇:SQLiteC/C接口详细介绍之sqlite3类(七) 19. sqlite3_changes与sqlite3_changes64 是SQLite中用…

CSDN 编辑器设置图片缩放和居中

CSDN 编辑器设置图片缩放和居中 文章目录 CSDN 编辑器设置图片缩放和居中对齐方式比例缩放 对齐方式 Markdown 编辑器插入图片的代码格式为 ![图片描述](图片路径)CSDN 的 Markdown 编辑器中插入图片,默认都是左对齐,需要设置居中对齐的话,…

9种分布式ID生成之美团(Leaf)实战

​​​​​ 前几天写过一篇《一口气说出 9种 分布式ID生成方式,面试官有点懵了》,里边简单的介绍了九种分布式ID生成方式,但是对于像美团(Leaf)、滴滴(Tinyid)、百度(uid-generator&…

多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测

多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测 目录 多维时序 | MATLAB实现BiTCN-selfAttention自注意力机制结合双向时间卷积神经网络多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.M…

三个表联合查询的场景分析-场景1:a表关联了b表和c表

本场景对应情景如下: 三个数据表,一个表的两个字段分别关联了另外两个表各自的id数据,可能包含多个id(两个1对多关联)。 目录 数据表准备 需求1、查询c表的列表数据,要求获得关联的b表中的name&#xf…

OceanBase中binlog service 功能的试用

OBLogProxy简介 OBLogProxy即OceanBase的增量日志代理服务,它可与OceanBase建立连接并读取增量日志,从而为下游服务提供了变更数据捕获(CDC)的功能。 关于OBLogProxy的详尽介绍与具体的安装指引,您可以参考这篇官方OB…

【深度学习笔记】9_8 区域卷积神经网络(R-CNN)系列

注:本文为《动手学深度学习》开源内容,部分标注了个人理解,仅为个人学习记录,无抄袭搬运意图 9.8 区域卷积神经网络(R-CNN)系列 区域卷积神经网络(region-based CNN或regions with CNN feature…

Unreal发布Android在刘海屏手机上不能全屏显示问题

Unreal 4.27发布Android在刘海屏手机上不能全屏显示问题 Android设置全屏刘海屏全屏设置4.27设置刘海屏在部分手机不能显示问题 Android设置全屏 AndroidManifest.xml文件配置 ...<activity android:name"com.epicgames.ue4.GameActivity" android:label"st…

Spring基础——使用注解开发SpringMVC

目录 配置SpringMVC的初始化信息配置ServletWebApplicationContext配置RootWebApplicationContext配置ServletContext 创建Controller控制器配置Controller响应路径接收用户传递参数接收JSON数据接收简单类型对象封装参数 接收数组类型 Restful 文章源码仓库&#xff1a;Spring…

bootstrap企业网站前端模板

介绍 企业网站前端模板 软件架构 前端所用技术html/css/js/jquery 前端框架bootstrap 安装教程 浏览器本地路径访问发布到服务器比如&#xff08;tomcat/nginx等&#xff09;云服务器/虚拟机 网站效果图 网站预览 点击预览 源码地址 https://gitee.com/taisan/company…

【镜像转存】利用交互式学习平台killercoda转存K8S镜像至Docker私人仓库

文章目录 1. 镜像转存需求2. 注册并登陆 killercoda URL3. 打开playground4. 在线拉取K8S镜像并打上标签5. 推送K8S镜像到Docker私有仓库6. 登陆Docker私有仓库查看 1. 镜像转存需求 因K8S镜像在不开代理的情况下&#xff0c;拉取超时、下载缓慢&#xff0c;导致镜像拉取不下来…

【分布式websocket】群聊中的各种难点以及解决推拉结合【第16期】

前言 群聊中未读消息如何设计&#xff0c;以及是推消息还是拉去消息如何选择是需要讨论的。推送消息是推送全量消息还是推送信号消息让客户端再去拉取。其中方案如何选型会比较纠结。 首先基本的推拉结合思路是在线用户推送消息。用户离线的话上线去拉取消息。这是简单的推拉结…

WPF —— TabControl、StackPanel 控件详解

1 TabControl简介 表示包含多个项的控件&#xff0c;这些项共享屏幕上的同一空间。 TabControl有助于最大程度地减少屏幕空间使用量&#xff0c;同时允许应用程序公开大量数据。 TabControl包含共享同一屏幕空间的多个 TabItem 对象。一次只能看到 TabControl 中的一个 Ta…

交换机/路由器的存储介质-华三

交换机/路由器的存储介质-华三 本文主要介绍网络设备的存储介质组成。 ROM(read-only memory&#xff0c;只读存储器) 用于存储 BootROM程序。BootROM程序是一个微缩的引导程序&#xff0c;主要任务是查找应用程序文件并引导到操作系统&#xff0c;在应用程序文件或配置文件出…

AJAX 01 AJAX 概念和 axios 使用

2.27 AJAX 学习 AJAX 1 入门01 AJAX 概念和 axios 使用axios 使用案例 02 认识 URLURL组成 03 URL 查询参数axios&#xff0d;查询参数案例 &#xff1a;地区查询 04 常用请求方法和数据提交axios 请求配置axios 错误处理 05 HTTP协议-报文① 请求报文作用&#xff1a;错误排查…

uniapp微信小程序_自定义交费逻辑编写

一、首先看最终效果 先说下整体逻辑,选中状态为淡紫色,点击哪个金额,充值页面上就显示多少金额 二、代码 <view class"addMoney"><view class"addMoneyTittle">充值金额</view><view class"selfaddmoney" :class"{…