C.2矩阵运算的复杂度 ·281 -Gustafsson,Kreiss&Sundstrom(1972)stability of boundary conditions -Chorin(1973)vortex methods for CFD -Engquist Majda(1977)absorbing boundary conditions C.2矩阵运算的复杂度 算法的执行效率依赖于算法中所涉及的运算类型和运算次数。一般来说，数值算法所涉及的运算主 要是加减乘除，以及开根号运算.开根号运算依赖于具体的实现算法，一般最终也可以归结为加减乘除 运算，而且开根号运算次数往往比加减乘除运算具有更低的数量级.因此，评价算法的一个重要标准就 是加诚乘除运算的次数 一般情况下，加减运算次数与乘法运算次数具有相同的数量级，而除法运算次数往往比乘法运算具 有更低的数量级。 常见数值运算的计算量 0(n)量级 0(m2)量级 O(n3)量级 x←0x x←Ax B←-aAB y←y+ax u←-aAx+Bu C←aAB+BC s←x(内积 x←Alx(A三角矩阵 s←-lx2 A←A+axy(秩1修正) s←zl A←A+ay°+ayr*(对称秩2修正) 向量的交换，复制，比较 ↑为了提高程序执行效率，节约程序开发成本，建议尽可能地使用现有的高性能优秀程序库，如BLAS, LAPACK等 C.3数值线性代数程序库 BLAS,LAPACK,ARPACK是当前数值计算中优秀程序库的典型代表，许多科学计算软件都是基于 这些程序库，如著名的MATLAB. C.3.1 BLAS BLAS(Basic Linear Algebra Subprograms))是一组高质量的子程序，用于实现基本的向量和矩阵运算， 最初发布于1979年.在BLS中，所有的子程序都经过精心的优化以确保其高效性，同时，程序的书写 和语句的选择都很规范，以便于移植。 长期以来，专家们一直呼吁使用BLAS来建立和开发自己的线性代数软件包.这样做，不仅可以缩 短开发周期，而且便于形成统一的调用接口.在高性能计算领域，BLAS被广泛使用.合理的调用BLAS 子程序，可以大大提高程序的性能， 目前BLAS库有多种不同的优化实现，如BLAS,Goto BLAS,.ATLAS等.为提高性能，各软硬件厂商 都会对其产品的BLAS接口实现进行高度优化， C.2 矩阵运算的复杂度 · 281 · – Gustafsson, Kreiss & Sundstrom (1972) stability of boundary conditions – Chorin (1973) vortex methods for CFD – Engquist & Majda (1977) absorbing boundary conditions C.2 矩阵运算的复杂度 算法的执行效率依赖于算法中所涉及的运算类型和运算次数. 一般来说, 数值算法所涉及的运算主 要是加减乘除, 以及开根号运算. 开根号运算依赖于具体的实现算法, 一般最终也可以归结为加减乘除 运算, 而且开根号运算次数往往比加减乘除运算具有更低的数量级. 因此, 评价算法的一个重要标准就 是加减乘除运算的次数. 一般情况下, 加减运算次数与乘法运算次数具有相同的数量级, 而除法运算次数往往比乘法运算具 有更低的数量级. 常见数值运算的计算量: O(n) 量级 O(n 2 ) 量级 O(n 3 ) 量级 x ← αx x ← Ax B ← αAB y ← y + αx y ← αAx + βy C ← αAB + βC s ← y ∗x (内积) x ← A−1x (A 三角矩阵) s ← ∥x∥2 A ← A + αxy∗ (秩 1 修正) s ← ∥x∥1 A ← A + αxy∗ + αyx∗ (对称秩 2 修正) 向量的交换, 复制, 比较 † 为了提高程序执行效率, 节约程序开发成本, 建议尽可能地使用现有的高性能优秀程序库, 如BLAS, LAPACK 等. C.3 数值线性代数程序库 BLAS, LAPACK, ARPACK 是当前数值计算中优秀程序库的典型代表, 许多科学计算软件都是基于 这些程序库, 如著名的 MATLAB. C.3.1 BLAS BLAS (Basic Linear Algebra Subprograms) 是一组高质量的子程序, 用于实现基本的向量和矩阵运算, 最初发布于 1979 年. 在 BLAS 中, 所有的子程序都经过精心的优化以确保其高效性, 同时, 程序的书写 和语句的选择都很规范, 以便于移植. 长期以来, 专家们一直呼吁使用 BLAS 来建立和开发自己的线性代数软件包. 这样做, 不仅可以缩 短开发周期, 而且便于形成统一的调用接口. 在高性能计算领域, BLAS 被广泛使用. 合理的调用 BLAS 子程序, 可以大大提高程序的性能. 目前 BLAS 库有多种不同的优化实现, 如 BLAS, Goto BLAS, ATLAS 等. 为提高性能, 各软硬件厂商 都会对其产品的 BLAS 接口实现进行高度优化