线性方程组求解库

求解线性方程组 Ax=b，常用的方法包括 直接解法（一般是对 A 进行矩阵分解）和 迭代法。常用的数值计算平台，如 Matlab，Octave，numpy 中都支持对线性方程组的求解，以 Matlab 的性能最优，支持的方法也最多，直接求解时用 x=b\A 会根据 A 的性质（如对称、稀疏）选择最优的算法，在用迭代求解时还可以先进行不完全分解来加速收敛速度。

下面总结一下我所知道的开源的求解线性方程组的相关的数值计算库，一般都是 Fortran 或 C／C＋＋开发。

• BLAS(Basic Linear Algebra Subprograms)

  blas 是许多数值计算软件库的核心, 一般是用 Fortran77 实现, 支持矩阵、向量基本操作。也有 C／C＋＋的封装。
  据说性能最优的 BLAS 实现是 gotoBLAS。

• Sparse BLAS

  BLAS的 Sparse matrix 版本。见到的都是 NIST 版本，C＋＋的，netlib 上的 是一个 Fortran 版本。

• LAPACK（Linear Algebra PACKage）

  专用于线性运算的，如求解 AX=b, 矩阵分解、求逆，求矩阵特征值、奇异值等，在 www.netlib.org/lapack/ 是 Fortran 版本的，应用很广，但还未见到针对 Sparse matrix 的版本。

• ScaLapck

  可以在分布内存的计算机上并行求解线性问题，即并行版的 LAPACK。

• SuiteSparse

  SuiteSparse 是 Prof. Tim Davis的 Sparse matrix solver 的程序包，涉及希疏矩阵分解，大多用 C 开发，提供 Matlab 接口。Matlab 中的很多数希疏矩阵函数的原型都可以在其中找到。性能非常出色。强烈推荐看看他的主页！

• TNT(Template Numerical Toolkit)

  C++的数值计算库，目标很大，据说还要集成 LAPACK++,Sparselib++,IML++,MV++。但目前还很薄弱，也就是定义了一些数据结构，求解线性方程组的能力基本没有，Sparse matrix 的操作功能也没有。

• Sparselib++

  C++的 Sparse matrix 库，与 sparse BLAS 差不多，多了对矩阵的 preconditioner功能，可以配合 IML++ 做线性方程组的迭代求解。

• IML++(Iterative Methods Library)

  C＋＋的。支持对 dense or sparse 的线性方程组的迭代求解，包括
  * Richardson Iteration
  * Chebyshev Iteration
  * Conjugate Gradient (CG)
  * Conjugate Gradient Squared (CGS)
  * BiConjugate Gradient (BiCG)
  * BiConjugate Gradient Stabilized (BiCGSTAB)
  * Generalized Minimum Residual (GMRES)
  * Quasi-Minimal Residual Without Lookahead (QMR)
  等方法，可配合使用 sparselib++。

• ITL (The Iterative Template Library)
  The ITL currently includes the following methods:

  • Conjugate Gradient (cg)
  • Conjugate Gradient Squared (cgs)
  • BiConjugate Gradient (bicg)
  • BiConjugate Gradient Stabilized (bicgstab)
  • Chebyshev Iteration (cheby)
  • Richardson Iteration (richardson)
  • Generalized Conjugate Residual (gcr)
  • Generalized Minimal Residual (gmres)
  • Quasi-Minimal Residual Without Lookahead (qmr)
  • Transpose Free Quasi-Minimal Residual Without Lookahead (tfqmr)

  The ITL currently includes the following preconditioners:

• Incomplete Cholesky (cholesky)
• Incomplete LU without fill-in (ILU)
• Incomplete LU with n fill-in and with threshold (ILUT)
• SSO
  
• SuperLU

  对大型、稀疏、非对称的线性系统的直接求解，用 Gauss 消去法做 LU 分解。用 C 开发。

• SPOOLES

  C。可求解对称和非对称的线性问题。

• MTL

  基于 C++ template 的 matrix class lib，技术比较眩，性能据说也不错，但支持的操作太少，线性方程组的只有 LU 分解，和几种迭代方法，不支持 sparse matrix。

• blitz++

  技术上更眩，但对线性方程组的支持很少。

• GSL

  GNU scientific library，很正统，但对 sparse matrix 的支持为0，性能也不突出。

• 其它

  MKL（intel math kernel library）非常强大，包括了优化过的 blas，LAPACK，又支持 sparse direct solver，可惜不开源，使用起来不方便。
  这儿对 sparse linear system direct solve software 有非常全面的总结。

I've tested some of the libraries, with following results :
testing data : sparse symmetric positive matrix
dimension : 3000x3000
density : 0.3
non-zeros : 1284213
condition : 2.7015e+04
opencv : CV_LU 45.7s(linux)
mkl : pardiso 3.17s(win)
matlab : \ 2.57s(win)
CHOLMOD : cholmod 2.48s(linux)

and I've found that linux(ubuntu-6.10 in my workstation) is far more flexible than windows in programming and scientific research!