当A和B都是大矩阵时，在MATLAB中的AX = B中求解X的有效方法 [英] Efficient way to solve for X in AX=B in MATLAB when both A and B are big matrices

问题描述

我有这个问题，需要解决AX=B中的X. A的大小为15000 x 15000，稀疏且对称. B是15000 X 7500，并且不稀疏.解决X最快的方法是什么?

I have this problem which requires solving for X in AX=B. A is of the order 15000 x 15000 and is sparse and symmetric. B is 15000 X 7500 and is NOT sparse. What is the fastest way to solve for X?

我可以想到两种方式.

1. 最简单的方法，X = A\B

2. 使用循环，

1. Simplest possible way, X = A\B

2. Using for loop,

invA = A\speye(size(A))
for i = 1:size(B,2)
    X(:,i) = invA*B(:,i);
end

有没有比以上两种更好的方法?如果没有，我提到的两者中哪一个最好?

Is there a better way than the above two? If not, which one is best between the two I mentioned?

推荐答案

第一件事-从不， ever 计算A的逆.即从不稀疏，除非A是对角矩阵.尝试将其用于简单的三对角矩阵.该行本身会杀死您的代码-从内存角度和从性能角度来看.而且，计算逆函数在数值上比其他方法更不准确.

First things first - never, ever compute inverse of A. That is never sparse except when A is a diagonal matrix. Try it for a simple tridiagonal matrix. That line on its own kills your code - memory-wise and performance-wise. And computing the inverse is numerically less accurate than other methods.

通常，\应该可以为您工作. MATLAB确实识别出您的矩阵是稀疏的，并执行了稀疏分解.如果将矩阵B作为右手边，则其性能要比仅使用b向量求解一个方程组的性能好得多.因此，您可以正确执行此操作.您可以在这里尝试的唯一其他技术方法是根据您拥有的矩阵显式调用lu，chol或ldl，然后自己执行向后/向前替换.也许您在那里节省了时间.

Generally, \ should work for you fine. MATLAB does recognize that your matrix is sparse and executes sparse factorization. If you give a matrix B as the right-hand side, the performance is much better than if you only solve one system of equations with a b vector. So you do that correctly. The only other technical thing you could try here is to explicitly call lu, chol, or ldl, depending on the matrix you have, and perform backward/forward substitution yourself. Maybe you save some time there.

事实是，求解方程式线性系统(尤其是稀疏系统)的方法强烈依赖于该问题.但我想在几乎所有(稀疏)情况下，15k系统的分解都只需几分之一秒.如今，这不是一个大型系统.如果您的代码运行缓慢，则可能意味着您的因素不再是稀疏.您需要确保对矩阵进行适当的重新排序，以在稀疏分解期间最小化填充(添加的非零条目).这是关键的一步.在此页面上 ，以获取有关如何对系统重新排序的一些测试和解释.并在此SO线程中简要查看示例重新排序.

The fact is that the methods to solve linear systems of equations, especially sparse systems, strongly depend on the problem. But in almost any (sparse) case I imagine, factorization of a 15k system should only take a fraction of a second. That is not a large system nowadays. If your code is slow, this probably means that your factor is not that sparse sparse anymore. You need to make sure that your matrix is properly reordered to minimize the fill (added non-zero entries) during sparse factorization. That is the crucial step. Have a look at this page for some tests and explanations on how to reorder your system. And have a brief look at example reorderings at this SO thread.

这篇关于当A和B都是大矩阵时，在MATLAB中的AX = B中求解X的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！