Matlab如何转置稀疏矩阵？

Question

我一直想知道这个问题很长一段时间但是找不到参考:Matlab如何快速转置稀疏矩阵,因为它存储在CSC(压缩稀疏列)格式中？

也其文档验证稀疏矩阵转置的效率:

要执行此操作(逐行访问),您可以转置矩阵,对列执行操作,然后重新转换结果...转置矩阵所需的时间可以忽略不计.

后续行动(根据@Mikhail的建议修改):

我同意@Roger和@Milhail的说法,设置一个标志足以支持许多操作,例如BLAS或稀疏BLAS操作的接口.但在我看来,Matlab做了"实际"换位.例如,我有一个稀疏矩阵X,大小为m*n = 7984*12411,我想缩放每一列和每一行:

% scaling each column
t = 0;
for i = 1 : 1000
    A = X; t0 = tic;
    A = bsxfun(@times, A, rand(1,n));
    t = t + toc(t0);
end

t = 0.023636秒

% scaling each row
t = 0;
for i = 1 : 1000
    A = X; t0 = tic;
    A = bsxfun(@times, A, rand(m,1));
    t = t + toc(t0);
end

t = 138.3586秒

% scaling each row by transposing X and transforming back
t = 0;
for i = 1 : 1000
    A = X; t0 = tic;
    A = A'; A = bsxfun(@times, A, rand(1,m)); A = A';
    t = t + toc(t0);
end

t = 19.5433秒

此结果意味着逐列访问比逐行访问更快.这是有道理的,因为稀疏矩阵是逐列存储的.因此,X'列缩放速度快的唯一原因应该是X实际上转换为X'而不是设置标志.

此外,如果每个稀疏矩阵以CSC格式存储,则简单地设置标志不能使CS'格式化为X'.

任何意见？提前致谢.

Answer 1

经过一周的探索,我对转置矩阵的内部机制的猜测是排序.

假设A是一个稀疏矩阵,

[I, J, S] = find(A);
[sorted_I, idx] = sort(I);
J = J(idx);
S = S(idx);
B = sparse(J, sorted_I, S);

然后B是转置A.

上面的实现大约是transpose我的机器上Matlab内置效率的一半.考虑到Matlab的内置函数是多线程的,我的猜测可能是合理的.

Answer 2

我同意罗杰·罗兰在评论中提到的内容。为了证实这一建议，您可以检查 BLAS 接口中的一些函数，MATLAB 使用该函数进行矩阵运算。我不确定它使用什么实现，但由于他们使用英特尔 IPP 进行图像处理，我想他们也可能使用英特尔 MKL 来加快矩阵运算。

这里是函数的文档mkl_?cscsv，它求解 CSC 格式稀疏矩阵的线性方程组。请注意transa输入标志，它明确定义提供的矩阵是否应被视为转置。