查找矩阵中最稀疏的行

Question

我在 MATLAB 中有一个矩阵，我想确定哪一行包含的零最多。也就是说，我想找到矩阵中最稀疏的行（和列）。有什么方法比使用 mat(sum(mat==0,i)==i,:) 循环更有效吗？或者这是首选方法？

我通过使用 "minimum-degree ordering heuristic" 求解线性系统来使用它来实现 LU 分解。

Answer 1

要查找 "sparsest" 行，如果我对此的解释正确，则意味着您要查找零数最多的行。您可以将 sum 以矢量化方式与 max 结合使用来计算：

[~, row] = max(sum(mat == 0, 2));

mat == 0 会将整个矩阵转换为 true/false，使得 true 为零值，而 false 否则，我们使用 sum 求和分别在每一行上。这将减少问题，使每个元素计算我们每行遇到的零元素的数量。在此结果上使用 max 的第二个输出，因此 row 将包含具有最多零的行。我们忽略第一个输出，因为这将输出我们不关心的实际最大值。

如果您关心速度，可以对转换后的 true/false 矩阵和向量 ones 执行矩阵向量乘法。这样它将为您执行求和，因此矩阵被提升到 double 精度：

[~, row] = max((mat == 0)*ones(size(mat, 2), 1)));

小注

请注意，如果有多行共享相同数量的已找到的最大数量的零，则此方法的局限性在于它将 return 首先满足这个条件的行。就您的 objective 而言，我相信这应该足够了。另请注意，如果您的矩阵包含无零，此方法的输出将默认为第一行。有一些我没有考虑到的极端情况，但我不确定你需要检查到什么程度，所以为了简单起见，我将把它们排除在外。

Answer 2

我不知道有什么函数可以以向量化的方式按行执行此操作（也就是说，直到我看到 ), but looping over nnz 应该相当快。循环不再很慢，因为新的发动机与 R2016a 一起问世。

tmp = zeros(size(mat,1),1);
for ii = 1:size(mat,1)
    tmp(ii) = nnz(mat(ii,:));
end

附带说明：我反对使用 i 作为变量，as it denotes the imaginary unit。

查找矩阵中最稀疏的行

Find sparsest row in matrix

matlab

matrix

sparse-matrix

小注