最有效的方法来求解线性方程组 [英] Most efficient way to solve a system of linear equations

问题描述

我有一个（n×n）对称矩阵A和一个（n×1）向量B.基本上，我只需要求解Ax = b。问题是A将潜在是巨大的。所以我正在寻找最有效的算法用于求解C ++中的线性方程。我翻看了Eigen图书馆。显然它有一个SVD方法，但我被告知它的速度很慢。求解x = inverse（A）* b也似乎是次优的。 uBLAS更快？有更有效的方法吗？谢谢。

编辑：矩阵A是正定的且不稀疏。

解决方案

最好的解决方法一个线性方程系统的形式 Ax = b 是做以下。

• 将 A 分解为格式 A = M1 * M2 c> M1 和 M2 都是三角形）


• 解决 M1 * y = c / code> c>使用回代替 c



>方形矩阵，步骤1将使用 LU分解。

对于非方形矩阵，步骤1将使用 QR分解。

如果矩阵A是正定而不是稀疏，则可以使用

如果你想使用eigen，你将必须先 href =http://eigen.tuxfamily.org/dox/classEigen_1_1LLT.html =nofollow>分解，然后 triangle solve it。

如果这还是很慢，幸运的是，有很多线性代数库使您能够这样做。你应该寻找的例程是 dpotrs 。有这样实现的一些库如下：

• Netlib的搭载：文档和下载（免费）


• Intel的MKL：文档和下载（免费用于非商业用途）。


• AMD的ACML：下载（免费）


• PLASMA： 下载（免费，多核优化）


• MAGMA ：下载（免费，在CUDA，OpenCL中实施）


• CULA：下载（免费频道，在CUDA中实施）。

如果您在整个项目中使用eigen，您可以按照此处。

I have an (n x n) symmetric matrix A and a (n x 1) vector B. Basically, I just need to solve Ax = b for x. The issue is that A is going to potentially be massive. So I'm looking for the most efficient algorithm for solving linear equations in C++. I looked over the Eigen library. Apparently it has an SVD method, but I've been told it's slow. Solving x=inverse(A)*b also seems like it would be suboptimal. Is uBLAS faster? Are there any more efficient methods? Thanks.

Edit: matrix A is positive definite and not sparse.

解决方案

The best way to solve A system of linear equations of the Form Ax = b is to do the following.

• decompose A into the format A = M1 * M2 (where M1 and M2 are triangular)
• Solve M1 * y = b for y using back substitution
• Solve M2 * x = y for x using back substitution

For square matrices, step 1 would use LU Decomposition.

For non square matrices, step 1 would use QR Decomposition.

If matrix A is positive definite and not sparse you'd use Cholesky Decomposition for the first step.

If you want to use eigen, you will have to first decompose it and then triangular solve it.

If this is still slow, thankfully, there are numerous linear algebra libraries available that enable you to do this. The routine you should be looking for is dpotrs. Some libraries that have this implemented are as follows:

• Netlib's lapack: Documentation and Download (free)
• Intel's MKL: Documentation and Download (Free for non commercial use).
• AMD's ACML: Download (free)
• PLASMA: Download (free, multi core optimized)
• MAGMA : Download (free, Implemented in CUDA, OpenCL)
• CULA: Download (freemium, Implemented in CUDA).

If you are using eigen in the overall project, you can interface the LAPACK routine you need as described here.

这篇关于最有效的方法来求解线性方程组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！