草庐IT

python - 已知结构矩阵的 NumPy 矩阵乘法效率

coder 2023-08-27 原文

我有两个要相乘的 NxN 矩阵:A 和 B。在 NumPy 中，我使用:

import numpy as np
C = np.dot(A, B)

但是，我碰巧知道对于矩阵 B，只有第 n 行和第 n 列不为零(这直接来自生成矩阵的分析公式，毫无疑问总是如此)。

希望利用这一事实并减少生成 C 所需的乘法次数，我将上面的内容替换为:

import numpy as np
for row in range(0, N):
    for col in range(0, N):
        if col != n:
            C[row, col] = A[row, n]*B[n, col]    #Just one scalar multiplication
        else:
            C[row, col] = np.dot(A[row], B[:, n])

从分析上讲，这应该降低总复杂度如下:在一般情况下(不使用任何花哨的技巧，只是基本的矩阵乘法)C = AB，其中 A 和 B 都是 NxN，应该是 O(N^3) .也就是说，所有 N 行必须乘以所有 N 列，并且这些点积中的每一个都包含 N 次乘法 => O(NNN) = O(N^3)。#

按照我在上面所做的那样利用 B 的结构，但是应该按照 O(N^2 + N^2) = O(2N^2) = O(N^2) 进行。也就是说，所有 N 行必须乘以所有 N 列，但是，对于所有这些(涉及 'B[:, n]' 的列除外)只需要一次标量乘法:只有 'B[:, m]' 的一个元素对于 m != n 是非零的。当 n == m 时，将发生 N 次(A 的每一行必须乘以 B 的 n 列)，必须发生 N 次标量乘法。#

但是，第一段代码(使用 np.dot(A, B))要快得多。我知道(通过以下信息:Why is matrix multiplication faster with numpy than with ctypes in Python?)np.dot 的低级实现细节可能是造成这种情况的原因。所以我的问题是:如何在不牺牲 NumPy 的执行效率的情况下利用矩阵 B 的结构来提高乘法效率，无需在 c 中构建自己的低级矩阵乘法？

此方法是对许多变量进行数值优化的一部分，因此，O(N^3) 很难处理，而 O(N^2) 可能会完成工作。

感谢您的帮助。另外，我是 SO 的新手，所以请原谅任何新手错误。

最佳答案

如果我正确理解了 A 和 B，那么我不理解 for 循环以及为什么您不只是将两者相乘非零向量:

# say A & B are like this:
n, N = 3, 5
A = np.array( np.random.randn(N, N ) )

B = np.zeros_like( A )
B[ n ] = np.random.randn( N )
B[:, n] = np.random.randn( N )

取B的非零行和列:

rowb, colb = B[n,:], np.copy( B[:,n] )
colb[ n ] = 0

将 A 乘以这两个向量:

X = np.outer( A[:,n], rowb )
X[:,n] += np.dot( A, colb )

验证检查:

X - np.dot( A, B )

N=100:

%timeit np.dot(A, B)
1000 loops, best of 3: 1.39 ms per loop

%timeit colb = np.copy( B[:,n] ); colb[ n ] = 0; X = np.outer( A[:,n], B[n,:] ); X[:,n] += np.dot( A, colb )
10000 loops, best of 3: 98.5 µs per loop

关于python - 已知结构矩阵的 NumPy 矩阵乘法效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20461271/

已知pythoncodesectionpreperformancenumpymatrixmatrix-multiplication

有关python - 已知结构矩阵的 NumPy 矩阵乘法效率的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  3. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  4. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. 旋转矩阵的几何意义 - 2

    点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前，先介绍一下点向量坐标矩阵的几何含义点：在一维空间下就是一个标量，如同一条直线上，以任意某一个位置为0点，以一定的尺度间隔为1，2，3...,相反方向为-1，-2，-3...；如此就形成了一维坐标系，这时候任何一个点都可以用一个数值表示，如点p1=5，即即从原点出发沿着x轴正方向移动5个尺度；点p2=-3，负方向移动3个尺度；     在一维坐标系上过原点做垂直于一维坐标系的直线，则形成了二维坐标系，此时描述一个点需要两个数值来表示点p3=（3，2），即从原点出发沿着x轴正方向移动3个尺度，在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。

  7. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  8. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  9. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  10. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

随机推荐