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

news/2024/5/26 20:48:14/文章来源:https://blog.csdn.net/beijinghorn/article/details/125074303

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

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

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

相关文章

什么是测试自动化平台?为什么需要测试自动化平台?如何选择平台

什么是测试自动化平台? 测试自动化平台是一种软件工具或框架,可帮助软件开发团队实现测试流程的自动化。它集成了多种功能和工具,使测试人员能够更高效地进行测试计划、用例设计、测试执行和结果分析。 为什么需要测试自动化平台&#xff1f…

微信小程序-day01

文章目录 前言微信小程序介绍 一、为什么要学习微信小程序?二、微信小程序的历史创建开发环境1.注册账号2.获取APPID 三、下载微信开发者工具1.创建微信小程序项目2.填写相关信息3.项目创建成功 四、小程序目录结构项目的主体组成结构 总结 前言 微信小程序介绍 微信小程序&…

3.环境对象this、this指向总结(待完成还有节流防抖待完成)、回调函数、事件

环境对象this 环境对象本质上是一个关键字 this this所在的代码区域不同,代表的含义不同 全局作用域中的this 全局作用域中this代表window对象 局部作用域中的this 在局部作用域中(函数中)this代表window对象 函数直接调用的时候简写了,函数完整写法…

网络编程:网络编程基础

一、网络发展 1.TCP/IP两个协议阶段 TCP/IP协议已分成了两个不同的协议: 用来检测网络传输中差错的传输控制协议TCP 专门负责对不同网络进行2互联的互联网协议IP 2.网络体系结构 OSI体系口诀:物链网输会示用 2.1网络体系结构概念 每一层都有自己独…

【python】anaconda安装过程

【运行环境】Windows11 文章目录 一、anaconda下载二、anaconda安装三、环境变量配置四、测试环境变量是否配置成功五、总结 一、anaconda下载 1、输入网址“https://www.anaconda.com”进入Anaconda官网。 2、找到【Free Download】点击进入: 3、点击对应系统的…

【论文速读】 | DeGPT:通过大语言模型优化反编译器输出

本次分享论文为:DeGPT: Optimizing Decompiler Output with LLM 基本信息 原文作者:Peiwei Hu, Ruigang Liang, Kai Chen 作者单位:中国科学院信息工程研究所;中国科学院大学网络空间安全学院 关键词:反向工程&…

【自然语言处理】NLP入门(五):1、正则表达式与Python中的实现(5):字符串常用方法:对齐方式、大小写转换详解

文章目录 一、前言二、正则表达式与Python中的实现1.字符串构造2. 字符串截取3. 字符串格式化输出4.字符转义符5. 字符串常用函数函数与方法之比较 6. 字符串常用方法1. 对齐方式center()ljust()rjust() 2. 大小写转换lower()upper()capitalize()title()swapcase() 一、前言 本…

ModuleNotFoundError: No module named ‘sklearn.cross_validation‘

一、问题分析 ModuleNotFoundError: No module named sklearn.cross_validation 英文先翻译一遍,模块未找到问题,这里涉及到sklearn这个模块,Sklearn (全称 SciKit-Learn),是基于 Python 语言的机器学习工…

mysql如何开启手动提交事务

在mysql中,有一个变量autocommit,表示自动提交,默认为1,表示开启自动提交。通过以下命令查询 select autocommit;当autocommit为1时,任何一条sql语句都是一个事务,执行完由mysql自动提交。如果想自己决定什…

鸿蒙实战开发学习:【HiView插件开发】

概述 Hiview是一个跨平台的终端设备维测服务集,其中是由插件管理平台和插件实现的各自功能构成整套系统。 本文描述了hiview插件开发的全部流程。 插件的概念 整节部分包括了插件的概念,事件源的概念,流水线的概念等基本概念 插件的定义 …

【SpringCloud微服务实战01】Eureka 注册中心

前言 在 Eureka 架构中,微服务角色有两类: EurekaServer :服务端,注册中心 记录服务信息 心跳监控 EurekaClient :客户端 Provider :服务提供者,例如案例中的 user-service …

吴恩达机器学习笔记 十八 制定一个性能评估标准 学习曲线 高偏差 高方差

一个模型的好坏的评估基准可以从下面几个方面考虑: 1.考虑人类在这个问题上的表现 2.对比竞争算法的表现 3.根据经验猜测 判断是高偏差还是高方差 训练样本数量越多,越难完美地拟合每个样本,因此 J_train 会逐渐增大一点点,但泛…

创造一款安卓自定义控件(4)——使用Matrix的setPolyToPoly方法实现图像纠正

接上文: 创造一款安卓自定义控件_任意4顶点裁剪框http://t.csdnimg.cn/vu1r5 创造一款安卓自定义控件_任意4顶点裁剪框2_为裁剪框添加放大镜功能http://t.csdnimg.cn/qkngh 创造一款安卓自定义控件_裁剪原理介绍http://t.csdnimg.cn/ORRRL 需求 随着需求修改&#x…

Apache Doris 2.1.0 版本发布:开箱盲测性能大幅优化,复杂查询性能提升 100%

亲爱的社区小伙伴们,我们很高兴地向大家宣布,在 3 月 8 日我们引来了 Apache Doris 2.1.0 版本的正式发布,欢迎大家下载使用。 在查询性能方面, 2.1 系列版本我们着重提升了开箱盲测性能,力争不做调优的情况下取得较好…

Python绘图-14绘制3D图(下)

14.7绘制3D等高线图个性化colormap 14.7.1图像呈现 14.7.2绘图代码 import numpy as np # 导入numpy库,numpy是Python的一个强大的数值计算扩展程序库,支持大量的维度数组与矩阵运算。 import matplotlib.pyplot as plt # 导入matplotlib的绘图模块p…

【漏洞复现】网康NS-ASG应用安全网关 index.php SQL注入漏洞(CVE-2024-2330)

0x01 产品简介 网康科技的NS-ASG应用安全网关是一款软硬件一体化的产品,集成了SSL和 IPSecQ,旨在保障业务访问的安全性,适配所有移动终端,提供多种链路均衡和选择技术,支持多种认证方式灵活组合,以及内置短…

【数据结构】树与堆 (向上/下调整算法和复杂度的分析、堆排序以及topk问题)

文章目录 1.树的概念1.1树的相关概念1.2树的表示 2.二叉树2.1概念2.2特殊二叉树2.3二叉树的存储 3.堆3.1堆的插入(向上调整)3.2堆的删除(向下调整)3.3堆的创建3.3.1使用向上调整3.3.2使用向下调整3.3.3两种建堆方式的比较 3.4堆排…

数据通信练习题

1.0osi七层模型 应用层 data 表示层 会话层 传输层 数据段 防火墙,端口(TCP UDP) 网络层 数据包 路由器 数据链路层 数据帧 交换机 物理层 比特流 网卡 2.IP地址分类 私有地址 A类 0--127 10.0.0.0…

基于HarmonyOS ArkTS中秋国庆祝福程序、以代码之名,写阖家团圆祝福

中秋、国庆双节将至,作为程序员,以代码之名,表达对于阖家团圆的祝福。本节将演示如何在基于HarmonyOS ArkUI的SwiperController、Image、Swiper等组件来实现节日祝福轮播程序。 规则要求具体要求如下: 1、根据主题,用…

计算机网络——OSI网络层次模型

计算机网络——OSI网络层次模型 应用层表示层会话层传输层TCP和UDP协议复用分用 网络层数据链路层物理层OSI网络层次模型中的硬件设备MAC地址和IP地址MAC地址IP地址MAC地址和IP地址区别 OSI网络层次模型通信过程解释端到端点到点端到端和点到点的区别 我们之前简单介绍了一下网…