在numpy中就地置换矩阵

计算科学 线性代数 Python 麻木的
2021-12-14 20:19:28

我想通过使用 python 的 numpy 库更改其若干行和列的顺序来就地修改密集的方形转换矩阵。在数学上,这对应于将矩阵预乘以置换矩阵 P,然后将其后乘以 P^-1 = P^T,但这不是计算上合理的解决方案。

现在我正在手动交换行和列,但我希望 numpy 有一个很好的函数 f(M, v) 其中 M 有 n 行和列,v 有 n 个条目,所以 f(M, v) 更新M根据索引排列v。也许我只是在搜索互联网时失败了。

使用 numpy 的“高级索引”可能会发生这样的事情,但我的理解是这样的解决方案不会到位。同样对于一些简单的情况,单独跟踪索引排列可能就足够了,但在我的情况下这并不方便。

补充:
有时当人们谈论排列时,他们仅指随机排列的采样,例如作为在统计中获得 p 值的过程的一部分。或者它们的意思是计数或枚举所有可能的排列。我不是在谈论这些事情。

补充:
矩阵足够小,可以放入桌面 RAM,但也足够大,我不想轻率地复制它。实际上我想使用尽可能大的矩阵,但我不想处理无法将它们保存在 RAM 中的不便,我对矩阵执行 O(N^3) LAPACK 操作,这也会限制实际矩阵大小。我目前不必要地复制了这么大的矩阵,但我希望这可以很容易地避免排列。

4个回答

根据文档,numpy 中没有就地排列方法,例如ndarray.sort

所以你的选择是(假设这M是一个N×N矩阵和p置换向量)

  1. 在 C 中实现自己的算法作为扩展模块(但就地算法很难,至少对我来说!)
  2. N内存开销

    for i in range(N):
        M[:,i] = M[p,i]
    for i in range(N):
        M[i,:] = M[i,p]
    
  3. N2内存开销

    M[:,:] = M[p,:]
    M[:,:] = M[:,p]
    

希望这些次优的技巧有用。

警告:下面的示例可以正常工作,但是使用后期建议的完整参数集会暴露一个错误,或者至少是 numpy.take() 函数中的“未记录的功能”。有关详细信息,请参阅下面的评论。 已提交错误报告

您可以使用numpy 的 take() 函数就地执行此操作,但它需要一些箍跳。

这是对单位矩阵的行进行随机排列的示例:

import numpy as np
i = np.identity(10)
rr = range(10)
np.random.shuffle(rr)
np.take(i, rr, axis=0)
array([[ 0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.]])

要就地执行此操作,您需要做的就是将“out”参数指定为与输入数组相同,并且必须设置 mode="clip" 或 mode="wrap"。如果您不设置模式,它将制作一个副本以在 Python 异常上恢复数组状态(请参见此处)

最后一点, take 似乎是一个数组方法,所以不是

np.take(i, rr, axis=0)

你可以打电话

i.take(rr, axis=0)

如果这更符合您的口味。因此,总的来说,您调用的内容应如下所示:

#Inplace Rearrange
arr = makeMyBixMatrix()
pVec0, pVec1 = calcMyPermutationVectors()
arr.take(pVec0, axis=0, out=arr, mode="clip")
arr.take(pVec1, axis=1, out=arr, mode="clip")

要置换行和列,我认为您要么必须运行它两次,要么使用numpy.unravel_index拉一些丑陋的恶作剧,这让我头疼。

如果您有一个以COO格式存储的稀疏矩阵,以下内容可能会有所帮助

    A.row = perm[A.row];
    A.col = perm[A.col];

假设A包含COO矩阵,并且permnumpy.array包含排列的。这只会有m内存开销,其中m是矩阵的非零元素的数量。

我没有足够的声誉发表评论,但我认为以下 SO 问题可能会有所帮助:https ://stackoverflow.com/questions/4370745/view-onto-a-numpy-array

基本点是您可以使用基本切片,这将在不复制的情况下创建数组视图,但如果您进行高级切片/索引,那么它将创建一个副本。