blocks|key|3429256|text|你可能想看看使用BLAS+(基本线性代数子例程)库，特别是英特尔提供了他们的MKL+here，AMD有他们的一个ACML+here，还有(开源)+Goto+BLAS+here。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3429257|(密集)矩阵-矩阵乘法内核将是一个?GEMM调用，其中的?表示浮点类型。例如，DGEMM将调用double例程。|style|CODE|3429258|除非你非常有信心知道自己在做什么，否则这些库可能会提供比你手工编写代码更好的性能。|3429259|如果你真的想自己编码，那么你可能需要考虑以下几点：|3429260|3429261|使用“向量”指令。高速缓存指令被广泛支持，一些较新的高速缓存还将支持instructions.|ordered-list-item|3429262|Nested循环展开，以最大限度地提高浮点运算与加载/存储operations.|3429263|Block-wise算法的比率，从而确保有效的高速缓存use.|3429264|Multi-threading.+|3429265|3429266|这个参考可能会让你对事物的当前状态有一个概念：|3429267|3429268|+3级BLAS+-K+Goto的高性能实施。|blockquote|3429269|3429270|3429271|希望这能有所帮助。|3429272|entityMap|0|LINK|mutability|MUTABLE|url|http://software.intel.com/en-us/articles/intel-mkl/|1|http://developer.amd.com/libraries/acml/pages/default.aspx|2|http://www.tacc.utexas.edu/tacc-projects/gotoblas2^0|16|4|0|1P|4|1|2B|4|2|0|H|5|S|1|13|5|1B|6|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@]|9|@$A|1J|B|1K|1|1L]|$A|1M|B|1N|1|1O]|$A|1P|B|1Q|1|1R]]|C|$]]|$1|D|3|E|5|6|7|1S|8|@$A|1T|B|1U|F|G]|$A|1V|B|1W|F|G]|$A|1X|B|1Y|F|G]|$A|1Z|B|20|F|G]]|9|@]|C|$]]|$1|H|3|I|5|6|7|21|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|22|8|@]|9|@]|C|$]]|$1|L|3|-4|5|6|7|23|8|@]|9|@]|C|$]]|$1|M|3|N|5|O|7|24|8|@]|9|@]|C|$]]|$1|P|3|Q|5|O|7|25|8|@]|9|@]|C|$]]|$1|R|3|S|5|O|7|26|8|@]|9|@]|C|$]]|$1|T|3|U|5|O|7|27|8|@]|9|@]|C|$]]|$1|V|3|-4|5|6|7|28|8|@]|9|@]|C|$]]|$1|W|3|X|5|6|7|29|8|@]|9|@]|C|$]]|$1|Y|3|-4|5|6|7|2A|8|@]|9|@]|C|$]]|$1|Z|3|10|5|11|7|2B|8|@]|9|@]|C|$]]|$1|12|3|-4|5|6|7|2C|8|@]|9|@]|C|$]]|$1|13|3|-4|5|6|7|2D|8|@]|9|@]|C|$]]|$1|14|3|15|5|6|7|2E|8|@]|9|@]|C|$]]|$1|16|3|-4|5|6|7|2F|8|@]|9|@]|C|$]]]|17|$18|$5|19|1A|1B|C|$1C|1D]]|1E|$5|19|1A|1B|C|$1C|1F]]|1G|$5|19|1A|1B|C|$1C|1H]]]]

You might want to have a look at using a BLAS (Basic Linear Algebra Subroutine) library, specifically Intel offer their MKL <a href="http://software.intel.com/en-us/articles/intel-mkl/" rel="nofollow">here</a>, AMD have their ACML <a href="http://developer.amd.com/libraries/acml/pages/default.aspx" rel="nofollow">here</a> and there's also the (opensource) Goto BLAS <a href="http://www.tacc.utexas.edu/tacc-projects/gotoblas2" rel="nofollow">here</a>.

The (dense) matrix-matrix multiply kernel will be a <code>?GEMM</code> call, where the <code>?</code> indicates the floating point type. For example <code>DGEMM</code> will call the <code>double</code> routine.

Unless you're extremely confident you know what you're doing with low-level optimisations, these libraries will probably offer better performance than something you can code by hand.

If you do want to have a go at coding this yourself then you may want to consider the following:

<ol>
<li>Use "vector" instructions. <code>SSE, SSE2..4</code> instructions are widely supported, some newer <code>CPU</code>'s will also support <code>AVX</code> instructions.</li>
<li>Nested loop unrolling to maximise the ratio of floating point operations to load/store operations.</li>
<li>Block-wise algorithms to ensure effective cache use.</li>
<li>Multi-threading. </li>
</ol>

This reference might give you an idea of the current state of things:

<blockquote>
 High-performance implementation of the level-3 BLAS - K Goto.
</blockquote>

Hope this helps.

blocks|key|3714414|text|我建议阅读Golub+and+Van+Loan的第一章，它解决了这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3714415|entityMap|0|LINK|mutability|MUTABLE|url|http://www.amazon.co.uk/Computations-Hopkins-Studies-Mathematical-Sciences/dp/0801854148^0|5|I|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I would suggest reading Chapter 1 of <a href="http://www.amazon.co.uk/Computations-Hopkins-Studies-Mathematical-Sciences/dp/0801854148" rel="nofollow noreferrer">Golub and Van Loan</a>, which addresses this exact question.

blocks|key|1814317|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1814318|缓存阻塞-确保您正确使用和重用缓存中的值|ordered-list-item|1814319|更好的算法-按定义乘矩阵的方法不是最佳的，看看Strassen's+algorithm|offset|length|1814320|Parallelization+-如果您的机器有多个内核和/或处理器，您可以分开并征服|1814321|+SSE+-利用现代CPU中的向量指令-现代CPU已经过优化，可以做这类事情。了解CUDA和OpenCL.|1814322|1814323|请注意，使用这些方法并不能保证更好的性能。需要进行大量的调优，从而实现显著的加速。有很多钱花在弄清楚如何快速乘法矩阵上，因此不乏关于这个主题的期刊文章。|1814324|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Strassen_algorithm|1|http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions|2|http://en.wikipedia.org/wiki/CUDA|3|http://en.wikipedia.org/wiki/OpenCL^0|0|0|N|K|0|0|0|1|3|1|15|4|2|1A|6|3|0|0|0^^$0|@$1|2|3|-4|4|5|6|12|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|13|7|@]|8|@]|9|$]]|$1|D|3|E|4|C|6|14|7|@]|8|@$F|15|G|16|1|17]]|9|$]]|$1|H|3|I|4|C|6|18|7|@]|8|@]|9|$]]|$1|J|3|K|4|C|6|19|7|@]|8|@$F|1A|G|1B|1|1C]|$F|1D|G|1E|1|1F]|$F|1G|G|1H|1|1I]]|9|$]]|$1|L|3|-4|4|5|6|1J|7|@]|8|@]|9|$]]|$1|M|3|N|4|5|6|1K|7|@]|8|@]|9|$]]|$1|O|3|-4|4|5|6|1L|7|@]|8|@]|9|$]]]|P|$Q|$4|R|S|T|9|$U|V]]|W|$4|R|S|T|9|$U|X]]|Y|$4|R|S|T|9|$U|Z]]|10|$4|R|S|T|9|$U|11]]]]

<ol>
<li>Cache blocking - making sure you're properly using and reusing values in the cache</li>
<li>Better algorithm - the "by-definition" way to multiply matrices is not optimal, take a look at <a href="http://en.wikipedia.org/wiki/Strassen_algorithm" rel="nofollow">Strassen's algorithm</a></li>
<li>Parallelization - if your machine has more than one core and/or processor, you can divide and conquer</li>
<li>SIMD - take advantage of <a href="http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions" rel="nofollow">SSE</a> vector instructions in modern CPU architectures</li>
<li>GPGPU - modern GPUs are optimized to do just this sort of thing. Look into <a href="http://en.wikipedia.org/wiki/CUDA" rel="nofollow">CUDA</a> and <a href="http://en.wikipedia.org/wiki/OpenCL" rel="nofollow">OpenCL</a>.</li>
</ol>

Note that using these methods does not guarantee better performance. There is a lot of tuning required give a significant speedup. There is a lot of money going into figuring out how to multiply matrices quickly so there is no shortage of journal articles on the subject.

blocks|key|1814357|text|如果问题涉及多个矩阵乘法-+M1+x+M2+x+...然后还有另一种基于动态规划的优化技术，这是另一种球类游戏。请注意，这不适用于提高两个矩阵相乘的效率；但是，如果您以成对方式将三个或更多矩阵相乘，则可以在更高的级别上进行优化。我只是想把这个答案扔到堆上，以完善信息。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1814358|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

If the question concerns multiple matrix multiplications - M1 x M2 x ... x Mn - then there is another optimization technique based on dynamic programming, which is sort of another ball-game. Note that this doesn't apply to improving the efficiency of multiplying two matrices; however, if you are multiplying three or more matrices in a pairwise fashion, then you can optimize at an even higher level. Just thought I'd throw this answer on the heap to round out the information.

blocks|key|1814440|text|这里有Strassen's+Algorithm，根据你矩阵的大小，它比你列出的标准算法要快一点。当然也有even+faster+algorithms，但它们的实现并不那么简单。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1814441|标准算法是O(N%5E3)，Strassen算法是O(N%5E2.8)，Coppersmith-Winograd是O(N%5E2.3)|1814442|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Strassen_algorithm|1|http://en.wikipedia.org/wiki/Coppersmith%25E2%2580%2593Winograd_algorithm^0|3|K|0|1G|M|1|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]|$A|T|B|U|1|V]]|C|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

Well there's <a href="http://en.wikipedia.org/wiki/Strassen_algorithm" rel="nofollow">Strassen's Algorithm</a>, which, depending on the size of your matrix, is ever so slightly faster than the standard algorithm that you listed. There are of course <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow">even faster algorithms</a>, but they arent so simple to implement.

The standard algorithm is O(N^3),
Strassen's algo is O(N^2.8),
and Coppersmith-Winograd is O(N^2.3)

How can I improve the efficiency of standard matrix multiplication algorithm?

The main operation involved in this approach is: <code>C[i][j]+=A[i][p]*B[p][j]</code>

What can be done to improve the efficiency of the algorithm?

Improving the efficiency of Standard Matrix Multiplication Algorithm?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

如何提高标准矩阵乘法算法的效率？这种方法涉及的主要操作是：C[i][j]+=A[i][p]*B[p][j]可以做什么来提高算法的效率？

问提高标准矩阵乘法算法的效率？
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问提高标准矩阵乘法算法的效率？EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问提高标准矩阵乘法算法的效率？
EN