matlab - 求解巨大的稀疏线性系统,其中 A 是 kron 乘积的结果
问题描述
如何(A ⊗ B + C ⊗ D) x = b
在不计算相乘的实际矩阵的情况下求解 MATLAB中的线性系统x
(⊗ 表示克罗内克积)。尽管A
, B
,C
和D
是sparse
矩阵,但幼稚的方法,
x = (kron(A,B) + kron(C,D))\b
不适合内存并导致 MATLAB 对于大型矩阵(每个矩阵约 1000 x 1000 个元素)崩溃。
关于这个还能做什么?
解决方案
看到您的矩阵通常非常稀疏,张量积的最终结果不应该占用那么多内存。这是由于中间计算的巨大内存需求而根本无法完成矢量化的情况之一,但它可能使用循环(和部分矢量化)。
请注意,这是一种“总比没有好,但不是很多”的解决方案。
我将使用ndSparse
submit,因为它可以更轻松地处理稀疏矩阵。
% Create some matrices
[A,B] = deal(sparse(1000,1000));
A(randperm(1000^2, 10000)) = randn(1E4, 1);
B(randperm(1000^2, 10000)) = randn(1E4, 1);
A = ndSparse(A); B = ndSparse(B);
% Kronecker tensor product, copied from kron.m
[ma,na] = size(A);
[mb,nb] = size(B);
A = reshape(A,[1 ma 1 na]);
B = reshape(B,[mb 1 nb 1]);
% K = reshape(A.*B,[ma*mb na*nb]); % This fails, too much memory.
K = ndSparse(sparse(mb*ma*nb*na,1),[mb, ma, nb, na]); % This works
从这里可以根据可用内存继续:
% If there's plenty of memory (2D x 1D -> 3D):
for ind1 = 1:mb
K(ind1,:,:,:) = bsxfun(@times, A, B(ind1, :, :, :));
end
% If there's less memory (1D x 1D -> 2D):
for ind1 = 1:mb
for ind2 = 1:ma
K(ind1,ind2,:,:) = bsxfun(@times, A(:, ind2, :, :), B(ind1, :, :, :));
end
end
% If there's even less memory (1D x 0D -> 1D):
for ind1 = 1:mb
for ind2 = 1:ma
for ind3 = 1:nb
K(ind1,ind2,ind3,:) = bsxfun(@times, A(:, ind2, :, :), B(ind1, :, ind3, :));
end
end
end
% If there's absolutely no memory (0D x 0D -> 0D):
for ind1 = 1:mb
for ind2 = 1:ma
for ind3 = 1:nb
for ind4 = 1:na
K(ind1,ind2,ind3,ind4) = A(:, ind2, :, ind4) .* B(ind1, :, ind3, :);
end
end
end
end
K = sparse(reshape(K,[ma*mb na*nb])); % Final touch
所以这只是如何最终执行计算的理论演示,但不幸的是它非常低效,因为它必须一遍又一遍地调用类方法,而且它也不能保证有足够的内存来评估\
运算符.
改善这一点的一种可能方法是以matlab.internal.sparse.kronSparse
某种块方式调用并将中间结果存储在输出数组的正确位置,但这需要仔细考虑。
顺便说一句,我尝试使用 Ander 提到的 FEX 提交(KronProd
),但是当您需要计算时它没有任何好处kron(A,B) + kron(C,D)
(尽管它在某些情况下非常棒kron(A,B)\b
)。
推荐阅读
- python - Django将数据传递给html
- c# - 如何在 c# asp.net 中使用 crud 操作创建 Windows 服务
- excel - 如何更改此语句以添加另一个 If?
- android - MVVMCross Native Android Progressbar 移动元素与当前进度
- c - CS50 CAESAR - 不同的输出取决于语句的位置,但我不明白为什么
- equation - 将程序员的函数转换为数学符号
- c - 在 C 中编程时使用 sqlite3.h 库时找不到文件
- vb.net - VB.NET 自动保存文本文件多个
- c# - 无法在 .Net Core3.1 Web API 服务中上传大文件
- google-app-engine - Google App Engine - 将应用程序配置为始终以测试版部署