-3

我想在稀疏矩阵上进行部分旋转的 LU 分解。似乎完全旋转对于稀疏矩阵来说非常快速和有效，而部分旋转对于稀疏矩阵来说效率不高。我的猜测是它不支持或针对稀疏进行优化。

A=randn(1e4).*(rand(1e4)<0.0001); 
S=sparse(A);

tic; [l,u,p]=lu(A); toc
Elapsed time is 8.699264 seconds.

tic; [l,u,p,q]=lu(S); toc
Elapsed time is 0.006430 seconds.

第二个，完全旋转的速度非常快（1400倍）

我的问题是，怎么可能？当矩阵稀疏时，部分旋转 LU 不应该更有效，并且总是（或几乎总是）比完全旋转更快吗？

有谁知道如何在稀疏矩阵上通过部分旋转来执行快速 LU？

谢谢，吉尔

4

1 回答 1

2

我觉得我必须澄清一些事情：

  1. 您是否知道您正在处理[l u p]版本中的完整矩阵，而不是稀疏矩阵？

  2. 部分旋转用于获得数值稳定性，而不是提高性能。

  3. 完全旋转用于减少分解稀疏矩阵时发生的填充量（对于完整矩阵来说不可能）。通过以最佳方式对行和列进行排序，性能显着提高。

速度增加的原因是非零点沿对角线排列。然而：

“稀疏与条目的结构有关：对角线周围的零带，外部零。” 是不正确的。

稀疏矩阵是主要包含零的矩阵，并表示为三个向量（行、列和值）。

sparse()是将完整矩阵转换为稀疏矩阵的一种完全有效的方法。Duffymo 的声明： “如果它需要一个完整的矩阵并将其映射到一个稀疏矩阵数据结构中，那么它当然会更慢。” , 是不正确的，只要整个矩阵大部分包含零。

尝试以下操作：

S = sprand(100,100,0.01);
[l, u, p] = lu(S);
spy(l)
figure
spy(u)

现在，执行以下操作：

[ll, uu, pp, qq] = lu(S);
spy(ll);
figure
spy(uu);

查看 和 的l结构u。您可能会知道为什么完全旋转会更快。

此外，当您尝试解决这个问题时，实际上并不是分解部分更快，而是稍后的前向替换部分。

于 2013-06-30T11:52:15.913 回答