解决线性方程组

Question

解决线性方程组

6

我有一个包含6个方程的系统需要在程序中反复求解（当然有许多不同的输入）。我目前使用的是克莱姆法则方法来解决这个系统，效果还不错（尽管明确的方程式长度超过2页，但处理器似乎非常喜欢加法和乘法运算，它可以在1微秒内得出答案）。然而，我需要求解的次数非常多，因此我正在寻找更快的方法。

问题是，是否存在更快或更有效的方法来解决这些方程，或者像CUDA这样的东西对此有益呢？

- Faken

你确定这6个方程式都是必要的吗？这些方程式已经被化简到最大程度了吗？ - BoltBait

我正在解决一个稳定性问题，它需要6个自由度（3个正交的xyz力和3个xyz扭矩）。我从Matlab中推导出方程，并将显式解硬编码到程序中（确定被单独解决）。然而，我无法进一步简化实际方程，它们太大且难以处理。 - Faken

你如何计算行列式？ - sellibitze

@aaa：我正在使用VS2008，优化设置为最大速度。 @sellibitze：我考虑过使用简单的循环来进行计算，但由于Matlab已经输出了简化的显式方程，所以我直接将其硬编码进去，认为这样可能会更快，因为生成的代码中没有条件语句，但说实话，这只是我的猜测，因为我不是计算机科学家。 - Faken

我个人不使用微软编译器，但据我所知，英特尔编译器会快得多，如果你能得到一个的话。根据你的循环，你也可能从自动OpenMP并行生成中获得一些好处。 - Anycorn

显示剩余3条评论

6个回答

3

也许你可以尝试使用http://arma.sourceforge.net/docs.html。它提供了预制的求解函数http://arma.sourceforge.net/docs.html#solve。但是它使用的atlas/lapack后端更适用于更大的函数。

你还可以尝试使用乘以逆矩阵http://arma.sourceforge.net/docs.html#inv，它是编译时模板，也可能更适合你的目的。

尝试这样做：x = inv(A)*b。由于A不会改变，因此只需进行一次倒置操作。然后你就可以通过简单的矩阵向量乘法轻松快速地完成任务。

- Anycorn

@GMan已将其删除。另外，我正在开发cublas/ublas桥接器，并寻找合作伙伴。您是否认识有兴趣的人（或者您自己）？我记得在某个地方看到过您提到使用cuda。 - Anycorn

@aaa：你的意思是允许Boost的uBLAS（或其他BLAS库）利用CUBLAS吗？我很感兴趣，但我没有时间去做其他事情。:( 我确实使用过CUDA，但只是为了探究，从未进行过任何严肃的工作。 - GManNickG

@GMan 当然，没问题。我以为你可能认识某个人。这更像是在GPU内存中使用cublas内核和少量函数进行通信的ublas表达式。这里有一个小测试案例：http://code.google.com/p/asadchev/source/browse/trunk/projects/boost/numeric/bindings/cublas/test.cpp - Anycorn

@aaa：你做的这个小项目非常棒。 :) 希望你能找到人帮忙完成。 - GManNickG

反转方法可能真的是最好的解决方案，而不需要使用CUDA（如果这种方法不够用，我将进一步探索CUDA）。通过在Matlab中进行一些巧妙的替换，我们可以将方程简化为相当合理的形式。我仍然需要多次计算逆矩阵，但至少它不再运行在程序的迭代部分了。虽然缺点是现在到处都有许多小方程。哦，谢谢你的想法！ - Faken

@GMan 谢谢。还有其他的东西，不幸的是还没有记录下来，我已经写信给了支持主应用程序。如果你想的话可以随意浏览，我非常需要反馈。 - Anycorn

2

你可以查看Boost的uBLAS。

然而，这种方法并不是很简单；你需要了解LU分解。

- GManNickG

1

或者任何其他提供LU分解、前向/后向替换等功能的库（+1） - sellibitze

LU分解是一种计算机友好的求解方法吗？我几年前在数值方法课上用我的TI-83计算器编程实现了其中一种算法，我还记得它使用了很多除法，这并不是很适合计算机。我会再次研究它，也许可以推导出一些通用公式来进行编程硬编码。 - Faken

@aaa：我的方程式的“形式”已知且不会改变，只是值不同（当形成Cramer法则可用的形式时，矩阵中也有零和一）。 uBLAS 不会考虑到这一点吗？ - Faken

@aaa：虽然它是通用的，但应该会进行大量优化。当然，Faken只需要尝试并分析哪种方法更快。 - GManNickG

@Gman：啊，我的VS2008上没有分析器，而且我也不知道如何使用它，因为我从来没有必要使用过（至少目前还没有）。我最好的办法就是手动计时每个函数... - Faken

2

肯定的，很难事先预测。如果您决定尝试ublas，可能值得使用bounded_matrix，因为它可以在编译时确定维度。 - Anycorn

1

如果您想要运行CUDA，就需要一张不错的Nvidia显卡。

如果您拥有Intel的CPU，我建议您使用Intel的MKL http://software.intel.com/en-us/intel-mkl/，这是专为Intel CPU进行优化的。

如果您使用CUDA，可能会遇到浮点或双精度问题。

此外，如果您对GPU编程不熟悉，您将需要更多时间来解决CUDA的问题。

- shader

哎呀...$400以上，超出了我的运营预算。也许我的大学有一些许可证，但我认为这将排除在家工作的可能性。我知道CUDA中的单精度/双精度问题，目前我仍在使用双精度，因为我不会因此受到速度惩罚。然而，如果我使用克莱姆法则，则应该能够通过缺少除法来使用单精度。 - Faken

@Fake 实际上，加法和减法是误差的主要来源。乘法和除法则不太会产生误差。 - Anycorn

我认为单精度对我来说已经足够了。我正在处理一个物理系统，其中我的控制误差已经远远超出了单精度数学的误差。 - Faken

你的显卡型号是什么？ - shader

@shader：家里的电脑是8800GTX，学校的电脑是310 GT...这张卡完全没用（是的，它实际上也是离散的！更悲哀的是，它还与Core i7 860处理器配对）。两张卡都支持CUDA，如果我能证明310 GT有一点速度优势，我应该能说服我的教授给我一张真正有实力的显卡。 - Faken

显示剩余2条评论

0

使用SSE2或更高版本，您至少可以获得两倍的速度提升。但与CUDA或OpenCL端口相比，这只是微不足道的。如果正确实现，CUDA或OpenCL端口可以获得一到两个数量级的加速。

如果您了解Python，PyCUDA可能是一个很好的入门点。

- Marcelo Cantos

我目前在使用核心i7处理器的VS2008，SSE2是否已默认启用？如果没有，默认如何启用？此外，在概念上，实现CUDA的最佳方法是什么（例如，一个线程生成要计算的值，一个线程处理从CUDA加载和检索数据，一个线程处理结果等）？ - Faken

当然。SSE2 几乎是十年前引入的。Core i7 架构支持 SSE4.2。很抱歉，我对 CUDA 无能为力，我没有太多的实践经验。 - Marcelo Cantos

0

除非你能够以非顺序的方式解决方程，否则CUDA是无法帮助你的。事实上，CUDA可能会更慢。任何不是极度并行的东西都不会从CUDA中获益。通过编译器开关启用SSE2是不够的。你需要一个编码为使用SSE2的库。在我看来，最好的线性代数库是Eigen。它非常容易使用，并支持SIMD（不仅仅是SSE2）。

- user401947

你所说的非顺序解方程是什么意思？我现在知道这个问题实际上是一个多变量优化问题（随着学习的深入，这个项目总是让我这样做）。然而，它是一个优化问题中的优化问题，因此我可以并行处理单个优化问题。如果让主CPU设置问题，CUDA能否自行调整参数并进行迭代，而不需要CPU明确提供数据？与CPU准备矩阵并由CUDA解决并简单返回不同，没有其他东西？ - Faken

把GPU看作是一个多核处理器。GPU有很多核心，但每个核心比CPU核心弱得多。GPU的优势在于并行化。你能把整个问题分成可以相互独立执行的子任务吗？比如说，你有方程1、2、...、N。你能独立解决它们吗？如果可以，CUDA可能会有所帮助。你可以先尝试在CPU上并行化你的代码，因为用CUDA做同样的事情更难。根据我的经验，线性代数非常难并行化，除非问题由独立的子任务组成。 - user401947

CUDA是一种类似于C的编程语言。GPU编码涉及显式内存管理。在移动数据时必须非常小心。解决一个6x6方程并将答案返回到CPU并不能证明其超额开销。为了从GPU中受益，您的算法必须能够同时流畅处理大量的方程。这些方程之间不应该有依赖关系。然后GPU可以比CPU更快地解决所有这些方程。 - user401947

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sellibitze · Accepted Answer

Cramer's rule不具备良好的可扩展性。对于只有两个或三个未知数的小型方程组，它还可以使用，但是如果方程组变得更大，则其他方法更有效率，例如：LU分解+前向替换+后向替换。