装好了CLAPACK，试着用最小二乘法解了个10000*100阶矩阵乘以100*1阶矩阵等于10000*1阶矩阵的方程，瞬间出来结果，估计比matlab还要快一点。当然这只用转成100*100阶矩阵的QR分解问题。我自己写的代码，用的householer算法，这样的矩阵分解真的很 费时间，这实在是让人很沮丧，让人觉得我自己真的不会写程序。花了两三天自己写矩阵的类，结果还不令人满意。这也是为什么我转头研究这些库。
我 好好想一了想，首先并不用把所有的事情都揽到自己头上，非要代码100%都是自己的。已经有现成的很完美的解决方案，拿来用就是了，我只是做科学计算，数学实验的人，没必要浪费时间到没有意义的地方。其次，并不是代码的问题，代码的速度很大程度上取决于算法，手头讲线性代数这方面算法的书并不多，倒是一堆讲美式期权估价算法的文章。两周的实习也让我深刻的认识到算法的重要性远大于编程的技巧。
接下来的事情就是好好学习这些库的用法，以更加熟练的运用到自己的程序之中。LAPACK用起来很方便，几乎程序的源代码都在SRC目录，每个源文件里面都有函数的详细用法。但是为了实现一个方法， 却很难在那么多源文件里面选择是哪一个，尤其是对新手，对那些函数的命名规则不熟的人，真的是举步维艰。
这里是比较容易找到的官方的使用说明。
下面就 是这些函数的一些总结和索引，方便自己查阅和中文的搜索。
这里还包含一些其他的科学计算库中的函数索引。
这里可以可以查到大部分函数的用法，还带例子，可以说是福利了。

这里实际上有我在网络上找到的唯一的也是详尽的一个安装方法，可是依照它一步步做下来，最后的程序还是F5不了。其实是因为自己对Visual Studio实在很不熟的缘故，并不是安装步骤有问题。通过这里一篇简短的Levmar安装说明，我终于明白了是怎么回事。

打开CLAPACK-3.1.1-VisualStudio文件夹，先把\LIB\Win32的lib都删了,以免混淆

双击clapack.vcproj打开工程项目文件，下面的各编译步骤都编译成debug模式

依次编译F2CLIBS,tmglib,blas,CLAPACK,结果是在\LIB\Win32下依次生成了 libf2cd.lib,tmglibd.lib,BLASd.lib,clapackd.lib

工具->选项->项目和解决方案->vc++目录->包含文件处添加     \INCLUDE目录

工具->选项->项目和解决方案->vc++目录->库文件处添加        \LIB\Win32目录

项目属性->连接器->输入->附加依赖项libf2cd.lib BLASd.lib clapackd.lib tmglibd.lib

项目属性->连接器->输入->忽略特定库Libcmtd.lib

原来是Libcmtd.lib和MSVCRT.lib两个默认库和libf2cd.lib的冲突造成的链接问题。

详细的解释见这里：http://blog.csdn.net/pgmsoul/archive/2009/05/20/4203941.aspx

最后总结一下安装Library的方法：

1. 像boost那样大多数都是直接可用的头文件的，可以直接设置\INCLUDE目录
2. 而像CLAPACK这个和boost中有一些库，必须编译成Lib，然后设置成\LIB目录
3. 测试库文件，编译或者运行出错的时候，记得查看日志，找出真正的错误原因

如此简单。

转帖自：http://hi.baidu.com/kaien_space/blog/item/dcb84b8b96347bd4fd1f1011.html

关于CLAPACK的使用网上的资料并不多。主要就是官方网站上的安装说明，以 及LAPACK官方论坛上的一些资料。然而，国外一般科研使用的平台都是UNIX或LINUX, 所以对于windows上使用CLAPACK的相关介绍就很少。幸运的是，官方提供了CLAPACK的windows版本，而且还有专门的 VisualStudio工程包。所以，对于广大VS用户来说可谓非常之方便。

然而，即使如此，很多人在使用的过程中还是出现这样那样的问题。其中，多数的情况都是出在编译的时候。而且上网提问多数都没人能够解答。
鉴于此，本人就对如何在VC上编译和使用CLAPACK库，作下简单的说明。

1、什么是CLAPACK:
CLAPACK是LAPACK的C语言接口。LAPACK的全称是Linear Algebra PACKage，是非常著名的线性代数库。原版的LAPACK是用Fortran写的，为了方便C/C++程序的使用，就有了LAPACK的C接口 CLAPACK。

LAPACK的主页是 http://www.netlib.org/lapack/
CLAPACK则在 http://www.netlib.org/clapack/。

这两个库都是开源的，可以在官方网站免费下载和使用。

2、CLAPACK的安装:
所谓的安装其实就是把源代码编译成我们可以调用的库.lib文件。

首先从主页上下载CLAPACK包。http://www.netlib.org/clapack/ 上有很多版本。我们选择
http://www.netlib.org/clapack/CLAPACK-3.1.1-VisualStudio.zip
大小: 42MB
版本: 3.1.1
是专门提供给VS用户的。
（注意:VS的版本不能太低。VC6.0是无法使用的。VS2005及以上都应该没问题。本人用的是VS2008。测试的时候发现工程文件版本太老，还需 要转换一下呢。当然转换后运行也很正常。如果你坚持要使用VC++6.0那请下载http://www.netlib.org/clapack/CLAPACK3-Windows.zip 这是CLAPACK3.0版，比我介绍的版本3.1.1版要旧一些）

下载解压后，我们可以看到如下目录结构:
SRC             CLAPACK的源代码
BLAS            BLAS的源代码
F2CLIBS       F2C的源代码

LIB                 编译后的库文件.lib
INCLUDE       头文件
TESTING       一些使用范例程序
INSTALL        里面有UNIX和其他平台下安装的文件和方法。lawn81.pdf文件是CLAPACK的使用说明，大家使用的时候可以看看。
这里我要提醒大家。虽然软件包里已经有编译好的.lib文件，就在LIB中。但是我建议 大家不要直接使用他们，还是自己编译一下再用才保险。很多人就是因为直接使用他们而出错的。这点非常重要！如果你就是直接调用他们失败的，那不妨先自己编 译一下再试试。

另外，CLAPACK需要F2CLIBS库，并且使用了blas和tmglib这两个外部的库。这几个库都已经包含在了CLAPACK的安装包中。 所以，大家无需另外下载。当然，使用前我们还是要重新编译一下的，原因上面已经说过了。

接下来，我详细地讲讲如何编译他们。
首先双击 clapack.vcproj打开工程项目文件。工程中已经包含了所有的子项目。
我们根据个人需要，编译成debug模式，或者release模式。为了能在自己的程序调用中方便的进行debug，我这里就以debug模式为例说明。 我的系统是win32。如果你是64位系统也是支持的，操作方法类似。

首先编译F2CLIBS，用于将fortran转换为c语言。
选择libf2c子项目。直接生成之。编译过程中可能会有一些warning，不要理会他们。编译成功后，输出文件是libf2cd.lib。这里的d就 是debug模式，如果是release模式就是libf2cd.lib。输出文件默认路径是LIB文件夹。注意，LIBWin32下已经有一些 lib了。大家最好把他们都先删除了，以免新旧文件混淆。

接着编译tmglib。这是一个矩阵库。
这个库在TESTINGMATGEN里面。选择他生成就好了。
输出文件还是在LIB里面。文件名是tmglibd.lib。
然后是编译blas，选择项目blas, 编译之。输出文件BLASd.lib。

最后是编译CLAPACK，生成clapackd.lib.

其他模式对应的输出文件大家可以参看下表。
这里需要注意的是，不同模式间不要混合使用。

Win 32

x64

3、如何调用CLAPACK:
前面，我们已经生成了CLAPACK的库文件了。那么如何在自己的程序中使用他们呢？
其实很简单。你所需要的只有两部分:
1)头文件
头文件就是.h文件。存放在INCLUDE中。在自己的工程里加入这个目录就行了。里面的文件最好不要作任何修改。程序中主要调用的头文件是 clapack.h和f2c.h。

2)库文件
库文件就是我们前面编译生成的那些lib文件了。

这里，我就以一个具体的调用实例详细地说明如何在VC中设置和使用CLAPACK。
首先，VC中项目的设置方式是:
项目的属性里。C/C++选项卡中，附加包含目录里添加INCLUDE目录。
连接器选项卡中。附加库目录里添加LIBWin32目录。然后附加依赖项添加libf2cd.lib BLASd.lib clapackd.lib tmglibd.lib。(根据不同的编译模式和个人需要以及系统需要选择库文件)

另外，如果想在调试时能对库函数进行源码级调试。那么需要在VS的 工具–选项–项目和解决方案–VC++目录 中添加SRC的目录。

本文，我们将调用CLAPACK的一个函数dgesvd_()来学习使用的方法。

注意: 包括此函数在内的所有的CLAPACK函数可以在SRC下找到源代码，并在代码中有函数参数的说明信息。dgesvd_ 的代码文件就是dgesvd.c。

dgesvd_的函数声明:

 int dgesvd_(char *jobu, char *jobvt, integer *m, integer *n,
doublereal *a, integer *lda, doublereal *s, doublereal *u, integer *
ldu, doublereal *vt, integer *ldvt, doublereal *work, integer *lwork,
integer *info)

dgesvd_的功能是对一个实矩阵A进行SVD分解(singular value decomposition)。
即 A = U * SIGMA * transpose(V)

dgesvd.c文件里有详细地函数说明和参数说明。
SIGMA is an M-by-N matrix which is zero except for its
min(m,n) diagonal elements, U is an M-by-M orthogonal matrix, and
V is an N-by-N orthogonal matrix. The diagonal elements of SIGMA
are the singular values of A; they are real and non-negative, and
are returned in descending order. The first min(m,n) columns of
U and V are the left and right singular vectors of A.

Note that the routine returns V**T, not V.
…………………………………..

参数的具体说明也请参看这个文件的 Arguments部分

  #include <stdio.h>
#include <process.h>
//因为程序是C++，而CLAPACK是f2c程序转换的C语言版本，所以在此处用extern关键字调用
extern"C"
{
#include <f2c.h>
#include <clapack.h>
}
 
 
#define SIZE 4
 
int main()
{
char JOBU;
char JOBVT;
 
int i;
 
//数据类型integer是fortran里的。这里在C++下可以使用的原因是f2c.h文件中已经作了定义
integer M = SIZE;
integer N = SIZE;
integer LDA = M;
integer LDU = M;
integer LDVT = N;
integer LWORK;
integer INFO;
 
integer mn = min( M, N );
 
integer MN = max( M, N );
 
double a[SIZE*SIZE] = { 16.0, 5.0, 9.0 , 4.0, 2.0, 11.0, 7.0 ,  14.0, 3.0, 10.0, 6.0, 15.0, 13.0, 8.0, 12.0, 1.0};
double s[SIZE];
double wk[201];
double uu[SIZE*SIZE];
double vt[SIZE*SIZE];
 
JOBU = 'A';
 
JOBVT = 'A';
 
LWORK = 201;
 
/* Subroutine int dgesvd_(char *jobu, char *jobvt, integer *m, integer  *n,
doublereal *a, integer *lda, doublereal *s, doublereal *u,  integer *
ldu, doublereal *vt, integer *ldvt, doublereal *work, integer  *lwork,
integer *info)
*/
dgesvd_( &JOBU, &JOBVT, &M, &N, a, &LDA, s, uu,  &LDU, vt, &LDVT, wk, &LWORK, &INFO);
 
printf("INFO=%d n", INFO );
for ( i= 0; i<SIZE; i++ ) {
printf("s[ %d ] = %fn", i, s[ i ] );
}
 
system("pause");
 
return 0;
}

运算结果输出:
INFO=0
s[ 0 ] = 34.000000
s[ 1 ] = 17.888544
s[ 2 ] = 4.472136
s[ 3 ] = 0.000000

注意：这个例子中我们使用的库是clapackd.lib。
libf2cd.lib BLASd.lib tmglibd.lib都没有用到。
总之需要什么库就用什么库。关键点是一定要自己编译生成这些.lib文件来使用。不要用现成的，以免出错。

kaien

2009年2月6日

在 C++中，库的地位是非常高的。C++之父 Bjarne Stroustrup先生多次表示了设计库来扩充功能要好过设计更多的语法的言论。现实中，C++的库门类繁多，解决 的问题也是极其广泛，库从轻量级到重量级的都有。不少都是让人眼界大开，亦或是望而生叹的思维杰作。由于库的数量非常庞大，而且限于笔者水平，其中很多并 不了解。所以文中所提的一些库都是比较著名的大型库。

C++各大有名库的介绍——科学计算

１、Blitz++

参考网站：http://www.oonumerics.org/blitz

Blitz++ 是一个高效率的数值计算函数库，它的设计目的是希望建立一套既具像C++ 一样方便，同时又比Fortran速度更快的数值计算环境。通常，用C++所写出的数值程序， 比 Fortran慢20%左右，因此Blitz++正是要改掉这个缺点。方法是利用C++的template 技术，程序执行甚至可以比Fortran更快。

Blitz++目前仍在发展中，对于常见的SVD，FFTs，QMRES等常见的线性代数方法并不提供，不过使用者可以很容易地利用 Blitz++所提供的函数来构建。

２、POOMA

参考网站：http://www.codesourcery.com/pooma/pooma

POOMA是一个免费的高性能的C++库，用于处理并行式科学计算。POOMA的面向对象设计方便了快速的程 序开发，对并行机器进行了优化以达到最高的效率，方便在工业和研究环境中使用。

３、MTL

参考网站：http://www.osl.iu.edu/research/mtl

Matrix Template Library(MTL) 是一个高性能的泛型组件库，提供了各种格式矩阵的大量线性代数方面的功能。在某些应用使用高性能编译器的情况下，比如Intel的编译器，从产生的汇编代 码可以看出其与手写几乎没有两样的效能。

４、CGAL

参考网站：www.cgal.org

Computational Geometry Algorithms Library的目的是把在计 算几何方面的大部分重要的解决方案和方法以C++库的形式提供给工业和学术界的用户。

Intel Math Kernel Library
1.基本线形代数运算(BLAS) 向量与向量、向量与矩阵、矩阵与矩阵的运算
2.稀疏线形代数运算
3.快速傅立叶变换(单精度/双精度)(fftw)
4.LAPACK(求解线形方程组、最小方差、特征值、Sylvester方程等)
5.向量数学库(VML)
6.向量统计学库(VSL)
7.高级离散傅立叶变换

IMSL
软件名称 IMSL C Numerical Library(不兼容vc6 编译器)
程序设计语言 C, Forton, C#, Java
资源网址 http://www.vni.com/
功能概述 分为统计库和数学库两部分. 数学库包含应用数学和特殊函数.IMSL 程序库 – 已成为数值分析解决方案的工业标准。 IMSL 程序库提供最完整与最值得信赖的函数库。 IMSL 数值程序库提供目前世界上最广泛被使用的 IMSL 算法，有超过 370 验证过、最正确与 thread-safe 的数学与统计程序。 IMSL FORTRAN 程序库提供新一代以 FORTRAN 90 为程序库基础的程序，能展现出最佳化的演算法能力应用于多处理器与其它高效能运算系统。

LAPACK
UserGuide: http://www.netlib.org/lapack/lug/lapack_lug.html

lapack
软件名称 Linear Algebra Package
程序设计语言 Fortran 77
资源网址 http://www.netlib.org/lapack
功能概述 线性代数计算子程序包

clapack
软件名称 Linear Algebra Package for C
程序设计语言 c/c++
资源网址 http://www.netlib.org/clapack/
功能概述 c版的线性代数计算子程序包
如何在Visual Studio 2008中安装CLAPACK http://www.deuxmille.org/archives/1486

lapack++
软件名称 Linear Algebra Package in c++
程序设计语言 c++
资源网址 http://math.nist.gov/lapack++/
功能概述 c++版的线性代数计算子程序包

BLAS
软件名称 Basic Linear Algebra Subroutines
程序设计语言 Fortran 77
主要开发者 Kagstrom B. ，Ling P. ，Van Loan C.
资源网址 http://www.netlib.org/blas
功能概述 Blas是执行向量和矩阵运算的子程序集合。

uBLAS
BLAS in C++ with expression templates. 表达式模版形式的 C++ 中的BLAS ，

gsl
软件名称 GNU Scientific Library (linux)
程序设计语言 C , C++ compable
资源网址 http://www.gnu.org/software/gsl/
功能概述 范围广泛, 包括数值分析的常见内容

Blitz++
软件名称　Blitz++ (不兼容vc6编译器)
资源网址 http://sourceforge.net/project/showfiles.php?group_id=63961
功能概述　The current versions provide dense arrays and vectors, random number generators, and small vectors and matrices.是一个高效率的数值计算函数库，它的设计目的是希望建立一套既具像 C++ 一样方便，同时又比 Fortran 速度更快的数值计算环境。通常，用 C++ 所写出的数值程序，比 Fortran 慢 20% 左右，因此Blitz++ 正是要改掉这个缺点。方法是利用 C++ 的 template 技术，程序执行甚至可以比 Fortran 更快。

MTL
软件名称　Matrix Template Library(兼容vc6编 译器)
资源网址 http://www.osl.iu.edu/research/mtl/
功能概述　The Matrix Template Library (MTL) is a high-performance generic component library that provides comprehensive linear algebra functionality for a wide variety of matrix formats. MTL专注于线性代数相关的计算任务，如各种形式矩阵的生成(对角，共轭，稀疏，对 称等)，相关的计算，变换，以及与一维向量的运算。

Armadillo
Armadillo is a C++ linear algebra library (matrix maths) aiming towards a good balance between speed and ease of use. Integer, floating point and complex numbers are supported, as well as a subset of trigonometric and statistics functions. Various matrix decompositions are provided through optional integration with LAPACK and ATLAS libraries.
资源网址 http://arma.sourceforge.net/

ATLAS
The ATLAS (Automatically Tuned Linear Algebra Software) project is an ongoing research effort focusing on applying empirical techniques in order to provide portable performance. At present, it provides C and Fortran77 interfaces to a portably efficient BLAS implementation, as well as a few routines from LAPACK.
资源网址 http://math-atlas.sourceforge.net/

二十世纪七大算法：
1946年　蒙特卡洛方法；
1951年　矩阵计算的分解方法；
1959~1961年　计算矩阵特征值的QR算法；
1962年　快速排序算法；
1965年　快速傅利叶变换算法；
1977年　整数关系探测算法；
1987年　快速多极算法。

下面是二十世纪最好的十大算法：

20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1. Monte Carlo方法
1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字 计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓，Metropolis算法可以说是最早的用来生成随机数，解决 不确定性问题的算法之一。

2. 线性规划的单纯形方法
1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时 又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是 由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的，但在实践中该算法是高度有效的 ——它本身说明了有关计算的本质的一些有趣的事情。

3. Krylov子空间叠代法
1950年，来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为Ax=b的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵，致使代数解x=b/A是不容易计算的(确实，矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为Kx(k+1)=Kx(k)+b- Ax(k)的方程，其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家Nikolai Krylov命名的Krylov子空间由作用在初始“余量”向量 r(0)=b-Ax(0)上的矩阵幂张成的。当 A是对称矩阵时，Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组，Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中，许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技 巧，像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journal on Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

4. 矩阵计算的分解方法
1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软 件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分 析”的重要文章。)

5. Fortran最优编译程序

1957年，John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他 人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23，500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵本征值计算的QR算法
1959—61年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大概是和矩阵相连在—起的最重要的数了，而且计算它们可能是最需要技巧的。把—个 方阵变换为一个“几乎是”上三角的矩阵――意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素――是相对容易的，但要想不产生大量的误差就把这些非零 元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解， A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把 A=Q(k)R(k) 变成 A(k+1)==Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。20世纪60年代中期QR 算法把一度难以对付的本征值问题变成了例行程序的计算。

7. 快速分类法
1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法.把n个事物按数或字母的次序排列起来，在心智上是不会有什么触动的单调平凡的事。智力的挑战在于发明一种快速完成 排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主 元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的第一个元素的话！)，快速分类法运行的平均次数具有O(Nlog(N)) 的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。

8. 快速Fourier变换
1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和AT＆T贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要 追溯到Gauss(他需要计算小行星的轨道)，但是Cooley—Tukey的论文弄清楚了Fourier变换计算起来有多容易。就像快速分类法一 样，FFT有赖于用分割开和控制的策略，把表面上令人讨厌的O(N*N) 降到令人满意的O(Nlog(N)) 。但是不像快速分类法，其执行(初一看)是非直观的而且不那么直接。其本身就给计算机科学一种推动力去研究计算问题和算法的固有复杂性。

9. 整数关系侦查算法
1977年，BrighamYoung大学的Helaman Ferguson 和Rodney Forcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1),x(2),…,x(n) ，是否存在整数a(1),a(2),..,a(n) （不全为零），使得
a(1)x(1)+a(2)x(2)+…+a(n)x(n)=0
对于n=2 ，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2) 的连分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1)和a(2) 。欧几里得算法不终止——或者如果你只是简单地由于厌倦计算——那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的 推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧 点，b(3)=3.544090 和 b(4)=3.564407所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是257^30 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。

10. 快速多极算法
1987年，耶鲁大学的Leslie Greengard 和Vladimir Rokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中 的星体，或者蛋白质中的原于)看来需要O(N*N) 的计算量——比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响。空间的层 次分解用来确定当距离增大时，比以往任何时候都更大的质点组。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。

三、结束语
2l世纪将会带来什么样的新的洞察和算法？对于又一个一百年完整的回答显然是不知道的。然而，有一点似乎是肯定的。正如20世纪能够产生最好的l0个算法 一样，新世纪对我们来说既不会是很宁静的，也不会是弱智的。

基础类
1、 Dinkumware C++ Library

参考站点：http://www.dinkumware.com

P.J. Plauger编写的高品质的标准库。P.J. Plauger博士是Dr. Dobb”s程序设计杰出奖的获得者。其编写的库长期被Microsoft采用，并且最近Borland也取得了其OEM的license，在其 C/C+ +的产品中采用Dinkumware的库。

2、 RogueWave Standard C++ Library

参 考站点：http://www.roguewave.com

这 个库在Borland C++ Builder的早期版本中曾经被采用，后来被其他的库给替换了。笔者不推荐使用。

3、SGI STL

参 考站点：http://www.roguewave.com

SGI 公司的C++标准模版库。

4、STLport

参考站点：http://www.stlport.org

SGI STL库的跨平台可移植版本。
5、准标准库——Boost

Boost 库是一个经过千锤百炼、可移植、提供源代码的C++库，作为标准库的后备，是C++标准化进程的发动机之一。 Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，其成员已近2000人。 Boost库为我们带来了最新、最酷、最实用的技术，是不折不扣的”准”标准库。

Boost中比较有名气的有这么几个库：

Regex
正则表达式库

Spirit
LL parser framework，用C++代码直接表达EBNF

Graph
图组件和算法

Lambda
在调用的地方定义短小匿名的函数对象，很实用的functional功能

Concept check
检查泛型编程中的concept

MPL
用模板实现的元编程框架

Thread
可移植的C++多线程库

Python
把C++类和函数映射到Python之中

Pool
内存池管理

Smart_ptr
5个智能指针，学习智能指针必读，一份不错的参考是来自CUJ的文章：

Smart Pointers in Boost,哦，这篇文章可以查到，CUJ是提供在线浏览的。中文版见笔者在《Dr. Dobb”s Journal软件研发杂志》第7辑上的译文。

Boost 总体来说是实用价值很高，质量很高的库。并且由于其对跨平台的强调，对标准C++的强调，是编写平台无关，现代C++的开发者必备的工具。但是Boost 中也有很多是实验性质的东西，在实际的开发中实用需要谨慎。并且很多Boost中的库功能堪称对语言功能的扩展，其构造用尽精巧的手法，不要贸然的花费时 间研读。Boost另外一面，比如Graph这样的库则是具有工业强度，结构良好，非常值得研读的精品代码，并且也可以放心的在产品代码中多多利用。

参 考站点：http://www.boost.org（国 内镜像：http://www.c-view.org/tech/lib/boost/index.htm , 中文文档：http://code.google.com/p/boost-doc-zh/downloads/list）

GUI

在 众多C++的库中，GUI部分的库算是比较繁荣，也比较引人注目的。在实际开发中，GUI库的选择也是非常重要的一件事情，下面我们综述一下可选择的 GUI库，各自的特点以及相关工具的支持。

1) MFC

大名鼎鼎的微软基础类库（Microsoft Foundation Class）。大凡学过VC++的人都应该知道这个库。虽然从技术角度讲，MFC是不大漂亮的，但是它构建于Windows API 之上，能够使程序员的工作更容易,编程效率高，减少了大量在建立 Windows 程序时必须编写的代码，同时它还提供了所有一般 C++ 编程的优点，例如继承和封装。MFC 编写的程序在各个版本的Windows操作系统上是可移植的，例如，在 Windows 3.1下编写的代码可以很容易地移植到 Windows NT 或 Windows 95 上。但是在最近发展以及官方支持上日渐势微。

2) QT

参考网站：http://www.trolltech.com

Qt 是Trolltech公司的一个多平台的C++图形用户界面应用程序框架。它提供给应用程序开发者建立艺术级的图形用户界面所需的所用功能。Qt是完全面 向对象的很容易扩展，并且允许真正地组件编程。自从1996年早些时候，Qt进入商业领域，它已经成为全世界范围内数千种成功的应用程序的基础。Qt也是 流行的Linux桌面环境KDE 的基础，同时它还支持Windows、Macintosh、Unix/X11等多种平台。

3) WxWindows

参考网站：http://www.wxwindows.org

跨平台的GUI库。因为其类层 次极像MFC，所以有文章介绍从MFC到WxWindows的代码移植以实现跨平台的功能。通过多年的开发也是一个日 趋完善的 GUI库，支持同样不弱于前面两个库。并且是完全开放源代码的。新近的C++ Builder X的GUI设计器就是基于这个库的。

4) Fox

开放源代码的GUI库。作者从自己亲身的开发经验中得出了一个理想的GUI库应该是什么样子的感受出发，从而开始了对这个库的开发。 有兴趣的可以尝试一下。

参考网站：http://www.fox-toolkit.org/

5)  WTL

基 于ATL的一个库。因为使用了大量ATL的轻量级手法，模板等技术，在代码尺寸，以及速度优化方面做得非常到位。主要面向的使用群体是开发COM轻量级供 网络下载的可视化控件的开发者。

6)  GTK

参考网站：http://gtkmm.sourceforge.net/

GTK 是一个大名鼎鼎的C的开源GUI库。在Linux世界中有Gnome这样的杀手应用。而GTK就是这个库的C++封装版本。

点我阅读更多