本文对嵌套网格上水平集函数的符号函数进行插值, 利用插值误差建立运动界面流场的离散多分辨分析, 根据多分辨系数确定局部网格尺度和计算格式, 构造了一类多尺度水平集方法. 对于多分辨系数较大的运动界面附近区域, 采用高精度WENO格式进行时间推进, 其余区域则直接采用多项式插值. 与单一尺度的水平集方法相比, 该方法可以在较少的CPU计算时间内捕捉到更为精细、锐利的运动界面.

引言 区域分裂方法起源于古老的schwarz交替方法[l].八十年代末期,法国数学家P.L.LionS提出了schwarz交替方法的投影解释[2一4],使得人们对schwarz交替方法有了全新的认识,为其进一步发展奠定了理论基础.由于并行计算环境的逐渐成熟以及预处理技术的兴起和大规模科学计算的需要,由严格串行的scliwarz交替方法发展了多种可完全并行的

H-张量在科学计算和工程应用中具有重要的作用,但在实际中要判定一给定张量为H-张量是不容易的.本文通过构造不同的正对角阵和运用不等式的放缩方法,给出了H-张量的一组实用性新判定方法.作为应用,给出了偶数阶实对称张量正定性判定的新条件.数值算例表明了结果的有效性.

稀疏矩阵算法是超级计算领域的热点和难点研究内容之一.本文从高可扩展、高性能和高实用这三个角度，对过去30年来国内外稀疏矩阵计算的部分主要研究工作进行了综述.并配合在三个GPU上十余个稀疏BLAS算法的测试数据，讨论了同时达到高可扩展、高性能和高实用这三个目标的主要难点.最后提出了未来稀疏矩阵计算领域的一系列挑战.

代数多重网格（AMG）是求解偏微分方程离散线性代数方程组最有效的算法之一，广泛应用于科学与工程计算领域实际问题的大规模数值模拟.随着超级计算机性能不断提升，实际数值模拟的计算规模和并行规模越来越大，同时，实际问题应用特征和计算机体系结构特征越来越复杂，AMG面临并行可扩展、算法可扩展和浮点性能优化的严峻挑战.本文结合大规模计算的发展趋势，特别是面向即将到来的百亿亿次（E级）计算，分析AMG算法在这三个方面的挑战，总结研究现状与进展，展望未来研究重点.

本文构造了一类求解非线性时滞双曲型偏微分方程的紧致差分格式, 获得了该差分格式的唯一可解性, 收敛性和无条件稳定性, 收敛阶为O(τ²+h⁴), 并进一步对时间方向进行Richardson外推, 使得收敛阶达到O(τ⁴+h⁴). 数值实验表明了算法的精度和有效性.

如何求解隐式辛格式李旺尧（中国科学院计算中心）一、前言ＨＯＷＴＯＳＯＬＶＥＩＭＰＬＩＣＩＴＳＹＭＰＬＥＣＴＩＣＳＣＨＥＭＥＳ￥ＬｉＷａｎｇｙａｏ（ＣｏｍｐｕｔｅｒＣｅｎｔｅｒ，ＡｃａｄｅｍｉａＳｉｎｉｃａ）Ａｂｓｔｒａｃｔ：Ｉｔｉｓｓｈｏｗｎｔｈａｔ...

在数学物理方法中,经常会遇到有部分边界满足周期性条件的边值问题。例如,在透平机械内部三元流动的流场延伸部分人工分界线(面)上(如图1中г_(32),г_(31)),流函数ψ满足周期性边界条件ψ|г_(32)=ψ|г_(31)+(?)。又如电机中的磁场分布(如图2),在边界Г_(32)Γ(31)半径相同处,其磁位A满足周期性条件A|г_(32)=-A|г_(31)。

将计算实矩阵的Moore-Penrose逆和Drazin逆转化为线性矩阵方程组的求解问题, 然后采用修正共轭梯度法求线性矩阵方程组的一般解,并通过简单的矩阵乘法运算或者直接得到实矩阵的Moore-Penrose逆和Drazin逆.修正共轭梯度法不同于通常的共轭梯度法, 它不要求涉及的线性代数方程组的系数矩阵正定、可逆或者列满秩, 因此总是可行的. 数值算例表明, 这种算法是有效的.

基于分裂场的完全匹配层(PML)吸收边界条件完成了对非物理反射波的吸收,初步实现了有限区域对无限开放空间的数值模拟,然而在计算区域的边界上需要对场分量进行分裂,增加了Maxwell方程组中独立方程的个数,使场分量迭代复杂,增大了数值计算量.单轴各向异性完全匹配层(UPML)边界条件则不需要对场分量进行分裂,迭代公式简单,便于程序实现,本文在常规UPML上增加了自由可变因子,使得对低频成分的反射波具有更好的吸收效果.本文首先推导了TMz波的改进型UPML方程组,给出了改进型UPML的介电参数分布方式,详细介绍了该算法的程序实现步骤,并以数值算例进行验证,分别采用基于分裂场的PML、常规UPML和改进型UPML边界条件进行数值计算,并从波场快照、时间域反射误差和频率域反射误差等方面,对比了三者的吸收效果,结果表明;在电磁波传播后期,改进型UPML吸收边界条件对低频率成分的反射波具有更好的吸收效果,更真实地模拟了开放的无限空间.

本文针对对角占优的对称矩阵(SDD)构成的稀疏线性系统,采用组合预处理技术从谱逼近角度分析并实现一种新型的预条件子.其与ILU类预条件子和AMG类预条件子相比,具有更高的并行可扩展性,满足通量守恒或者等效电阻原理. SDD矩阵通过数学上的规约手段,可以约化为标准的Laplace矩阵,其对应于图论中的无向图.基于此我们首先利用Ofer等提出的算法建立具有low stretch度量的一类生成树.然后采用树分解算法将生成树分解为子树,通过对子树选择合适的连接边进行加边修正得到相应的增广子图.最后将增广子图对应的Laplace矩阵转化为SDD矩阵,该矩阵即为原系数矩阵的预条件子.数值实验表明,与不完全Cholesky分解预条件子相比,该类预条件子更高效,其收敛速度对问题边界类型以及矩阵排序算法不敏感,并且其效率对矩阵规模增长不太敏感.

本文研究六边形区域上快速傅里叶变换(FFTH)的CUDA-MPI算法及其实现. 首先,我们通过充分利用CUDA的层次化并行机制及其库函数, 设计了FFTH的高效率的CUDA算法.对于规模为3×2048²的双精度复数类型数据, 我们设计的CUDA程序与CPU串行程序相比可以达到12倍加速比, 如果不计内存和显存之间的数据传输, 则加速比可达40倍;其计算效率与 CUFFT所提供的二维方形区域 FFT程序的效率基本一致.在此基础上, 我们通过研究GPU上分布式并行数据的转置与排序算法, 优化设计了FFTH的CUDA-MPI算法.在3×8192²的数据规模、10节点×6GPU的计算环境下, 我们的CUDA-MPI程序与CPU串行程序相比达到了55倍的加速; 其效率比MPI并行版FFTW以及基于CUFFT本地计算和FFTW并行转置的方形区域并行FFT 的效率都要高出很多. FFTH的CUDA-MPI算法研究和测试为大规模CPU+GPU异构计算机系统的可扩展新型算法的探索提供了参考.

本文给出了非负矩阵Perron根的一些新界值.设A为任意非负矩阵,ρ为其Perron根, f(A)为任意满足f(A)≥0的A的多项式,行和非零,则min(r_i(A·f(A))/r_i(f(A)))≤ρ≤r_i(A·f(A))/r_i(f(A))该结果推广了相关文献的结果,且可通过选择合适的多项式得到更精确的界值.

本文设计了任意维空间中具有线性复杂度的希尔伯特序编码解码算法并提出了希尔伯特 空间填充曲线的一种变体. 本文同时对编码解码算法进行了改进, 设计了复杂度更低的算法, 降低了计算量. 文中给出的希尔伯特空间填 充曲线的变体保证曲线的编码顺序不随曲线阶数的改变而变化.

本文提出了一种针对多尺度复合材料二、三维单胞模型生成和网格划分算法.单胞模型生成使用紧凑算法和舍选算法. 二维方法生成的椭圆数量大, 而且随机性好; 三维生成的椭球可以达到很高的体积分数. 使用自适应折线逼近算法用多边形逼近椭圆、多面体逼近椭球, 该方法能快速生成较好的质量网格. 试验证明了该算法的有效性.

基于求线性矩阵方程约束解的修正共轭梯度法的思想方法, 通过修改某些矩阵的结构,建立了求特殊类型的多矩阵变量线性矩阵方程的广义自反解的迭代算法, 证明了迭代算法的收敛性, 解决了给定矩阵在该矩阵方程的广义自反解集合中的最佳逼近计算问题.当矩阵方程相容时, 该算法可以在有限步计算后得到其一组广义自反解; 选取特殊的初始矩阵, 能够求得其极小范数广义自反解. 数值算例表明, 迭代算法是有效的.

由于非局部模型能够描述某些重要物理现象产生的奇性和间断机制，近些年来在很多领域受到广泛应用并对相关学科的发展产生了强有力的推动作用.反常扩散模型作为一个重要的非局部模型，常用于描述反常扩散等现象.非局部模型的非局部性和多尺度特征不仅推动了新的数学理论的发现，而且为现有的离散和局部连续模型及其联系提供了新的视角.尽管已经有很多成果，但无论是从数学方法和基础理论还是数值方法角度来看，多尺度非局部和反常扩散模型都有广阔的研究空间.进一步发展和完善基础数学理论和方法，在真实的解正则性条件下发展新的高效数值格式，尤其是具有稳定、收敛、满足渐近兼容的数值格式是一个研究重点.在过去的几年里，本文作者一直致力于非局部模型的数学理论和数值方法研究，在人工边界条件设计、非局部极值原理和渐近兼容的数值格式等方面，取得了一些有意义的研究成果.在反常扩散方程的数值分析方面，发展了Caputo导数的快速算法和离散分数阶类型的Grönwall不等式，并提出了误差卷积结构的思想来表示局部相容误差，为一类常用变步长数值格式的最优误差估计提供了一些基础分析框架.要完全解决非局部和反常扩散模型中的各种数学问题还有相当长的距离，需要进一步深入研究.希望本文能为推动多尺度非局部模型和反常扩散模型的基础理论和算法的深入发展起到抛砖引玉的作用.

三维变分资料同化作为现在主流数值天气预报的同化方法, 能够明显改善预报数据的质量. 随着科学研究的逐渐深入以及科学探测仪器和计算机技术的不断发展, 受计算量和内存需求量的限制, 传统串行三维变分资料同化系统已无法满足高分辨率、高精确度数值预报的要求. 所以, 三维变分资料同化系统的并行设计与实现显得尤其重要. 本文设计了混合二维区域剖分并行化方法及其通信算法库, 并将其应用于国家气象局三维变分同化系统3DVAR. 数值试验表明, 系统128核的并行效率相对于2核高达72%, 具有良好的加速效果; 同时, 内存需求也随处理器个数的增加而成倍减少, 满足了高分辨率预报的要求.

本文给出了一个基于谱分割并行求解稀疏矩阵特征值的方案,将矩阵的特征值求解区间划分为多个独立的子区间,分别对各个子区间内的特征值进行独立的并行求解. 在该方案中,提出了一种通过盖尔圆信息估计矩阵特征值分布的方法,并结合二分法以及插值方法修正特征值的分布,提高估计的准确性,进行谱区间分割. 本文还结合谱分割和基于围道积分的近似谱投影算法设计出一个特征值问题多级并行算法,并在“深腾7000” 和 “元”超级计算机上验证了本文提出谱分割方案的有效性、均衡性以及特征值并行求解的高效性. 同通用求解方法相比,基于谱区间分割的并行算法在1024核上性能提高了5倍以上,并行求解的可扩展性显著提升.

方波脉冲函数是一类新型的正交函数,它可在工程技术领域中得到广泛的应用。由于这种函数具有简明的定义、独特的运算性质、灵活的处理,不仅使人易于掌握,而且具有推导简明、公式简单、计算容易、快捷、准确度高,配合计算机使用,易于编程序、省时和节省计算机内存等一系列优点。有兴趣者,可参考文献[3]。

研究时间分数阶扩散方程, 利用时间方向的有限差分格式和空间方向的Legendre collocation谱方法构造了一个高阶稳定格式.一系列的数值试验表明该格式是稳定的, 其收敛阶为O(Δt^3-α+N^-m), 这里α, Δt, N和m分别为时间分数阶导数的阶数、时间步长、空间多项式逼近阶数和精确解的正则度.

Delaunay triangulation has been widely used in many fields such as compu- tational fluid dynamics, statistics, meteorology solid state physics, computational geometry and so on. Bowyer-Watson algorithm is a very popular one for generating Delaunay triangulation. In generating the Delaunay triangulation of a preassigned set of n points, the complexity of Bowyer-Watson algorithm can at most be reduced to O(n log n) for the simple reason that the complexity of its tree search process is O(nlog n). In this paper we suggest a tree search technique whose complexity is O(n). Noting that the order of point insertion can affect the efficiency of Bowyer- Watson algorithm, we propose a technique to optimize the point insertion process. Based on these two techniques, we obtain a fast algorithm for generating Delaunay triangulation.

本文对hp自适应策略进行了研究, 在前人提出的几种基于误差下降预测的~hp 自适应策略的基础上给出了一个新的 hp 自适应加密策略. 该策略适用于二维三角形、四边形和三维四面体、六面体等不同类型的单元, 适用于正则加密、二分加密等不同自适应加密方式. 数值实验表明, 该策略可以达到最优的误差指数下降阶, 并在数值解的精度和计算效率上优于文献中的一些策略. 该部分工作已集成到自适应有限元计算框架 PHG 的 hp 自适应模块.

本文考虑了基本初等函数的高精度快速算法问题. 首先讨论与Bernoulli 数B_2n或Euler数E_2n相关的基本初等函数(如tanx、secx、tanhx等)的幂级数展开问题, 并给出相应的幂级数展开式的快速算法. 然后,对于基本初等函数、双曲函数和反双曲函数, 在复数域上给出基于幂级数展开的任意精度的快速算法. 由于指数、对数函数可以用幂级数表示, 本文设计的算法适用于所有初等函数的计算. 算法的特点是编程简单、容易实现, 可以自成计算初等函数的体系.

基于分部的Runge-Kutta离散形式, 给出了一种新的三阶辛积分算法, 数值试验表明,长时程计算时该算法具有好的控制误差累积的能力; 与有限差分法进行空间域离散相结合, 通过数值试验进一步说明算法的有效性. 注意到位移波动方程通过谱元离散后的微分方程组, 完全符合新推导的三阶辛算法离散所需形式, 因此将该三阶辛算法与谱元法结合具有很好的优势, 并通过对横向各向同性介质弹性波场的模拟, 结果显示不但成功模拟了波的传播特性, 而且相对于传统算法, 优势明显.

中国的含油气地层分布广泛，但地质结构复杂，天然能量不足，开采难度高.油藏数值模拟方法与软件是油藏工程师对油藏进行分析和管理的重要工具，是油气藏开发后期确定剩余油分布、挖掘生产潜力和提高采收率的主要手段之一.精细地质模型可以达到很高的空间分辨率，导致网格数目巨大，模拟难度大、代价高，这给数值算法研究带来很多新挑战.本文以一个简化组分模型为例，简单介绍了其数学模型、离散方法、求解方法、并行计算和软件实现，其中着重介绍了几种被工业级软件采用的预条件方法和解耦方法.

GaBP(Gaussian Belief Propagation)是一种解线性代数方程组的迭代算法, 它是基于递归更新的概率推理算法, 具有低复杂性和高并行性. MIC是英特尔的至强融核Xeon Phi的Many Integerated Core架构. 它提供数百个同时运行的硬件线程, 能充分满足对高并发度的大量需求. 本文研究了如何高效地求解大规模稀疏线性方程组的并行算法, 通过挖掘GaBP算法特性, 优化算法存储结构和加速迭代, 同时 给出了一种求解大规模稀疏对称线性方程组的基于MIC的GaBP并行算法; 并从美国Florida大学开发的稀疏矩阵库(UFget)中抽取了部分大规模对称稀疏矩阵作为算例进行测试, 计算结果表明, 在相同精度下,基于MIC的GaBP并行算法相对于GaBP算法具有更显著的高效率.

稀疏矩阵向量乘(SpMV)是科学与工程计算中一个重要的核心函数, 但在当前基于存储器层次结构的计算平台上, 传统CSR(Compressed Sparse Row)存储的稀疏矩阵向量乘性能较低, 运行效率往往远低于硬件浮点峰值的10%. 目前现有的处理器架构一般都采用SIMD向量化技术进行加速, 但是传统CSR格式的稀疏矩阵向量乘由于访存的不规则性, 不能直接采用向量化技术进行加速, 为了利用SIMD技术, 对具有局部性特征的稀疏矩阵, 提出了新的稀疏矩阵存储格式CSRL(Compressed Sparse Row with Localinformation), 该格式可以减少SpMV时内存访问次数, 并且能够充分利用硬件的SIMD向量化技术进行读取和计算, 提高了SpMV 性能. 实验表明, 该方法相比国际著名商业库Intel MKL10.3版平均性能提升达到29.5%, 最高可达89% 的性能提升.

本文在通常的Black-Scholes假设下讨论连续观察的巴黎期权的定价问题,并给出其数值结果,基于分数步算法和两点中心隐式差分格式,采取了初值的奇性消除技术,获得了较高的效率和精度,最后分析了容许延迟时间及障碍位置对期权价格的影响。 Wilmott(1999)给出了巴黎期权定价问题的二项树算法,众所周知,二项树算法的局

保形Ｃ~１三次样条插值方法方逵，张新建（国防科技大学）ＳＨＡＰＥＰＲＥＳＥＲＶＩＮＧＣ￣１ＣＵＢＩＣＳＰＬＩＮＥＩＮＴＥＲＰＯＬＡＮＴ￥ＦａｎｇＫｕｉ；ＺｈａｎｇＸｉｎ－ｊｉａｎ（ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏ?..

随着电子计算机的使用,线性分室模型在生物学、医学、药学等学科的各个分支领域中的应用越来越广泛,也越来越深入.针对一个实际问题构造线性分室模型,首先碰到的问题是要从结构上论证所构造的模型是否合理.而判定该模型在结构上是否可完全控制,又是首先需要解决的问题之一.

拟合给定数据点集并重构曲面是几何造型研究的重要问题之一, 目前采用的主要方法为Bézier方法、NURBS方法、径向基函数方法等. 当给定数据点的参数域为凸多边形时, 需要对参数域剖分, 采用多片曲面拟合, 然后考虑相邻曲面片的拼接. 用toric Bézier曲面可以构造整体的方法进行数据拟合和曲面重构, 无须进行曲面拼接. 具体实例表明此方法是可行的和有效的.

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率, 设计了负载平衡的行划分方式, 实现了计算和通信重叠的稀疏矩阵重排序方法, 通过预处理减少计算过程中各进程间消息传递的通信量. 另外, 基于多核处理器高性能并行计算, 实现了 MPI和细粒度(线程级)OpenMP混合并行算法. 在深腾7800并行计算机上对并行算法进行了测试, 结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性, 适合大规模稀疏特征问题的求解.

利用勒让德多项式逼近理论和高斯-洛巴托求积公式, 构造了一个4级4阶的隐式Runge-Kutta方法.理论分析发现, 该算法具有良好的稳定性-是A(α)稳定的且α接近于90°, 是刚性稳定的且D值接近于0, 几乎是A稳定的和L稳定的, 并能有效求解刚性常微分方程初值问题, 数值算例显示了该算法的有效性.

二次KdV 类型水波方程作为一类重要的非线性方程有着许多广泛的应用前景. 本文基于Hamilton 系统的多辛理论研究了一类二次KdV类型水波方程的数值解法, 利用Fourier拟谱方法构造离散多辛格式的途径, 并构造了一种典型的半隐式的多辛格式, 该格式满足多辛守恒律.数值算例结果表明该多辛离散格式具有较好的长时间数值稳定性.

非奇异H-矩阵在数值线性代数的理论与应用中起着重要作用, 因此判定一个矩阵是否为非奇异H-矩阵有着非常重要的意义. 本文根据广义严格α-链对角占 优矩阵和广义严格α-对角占优矩阵的性质, 以及引入迭代因子, 给出了一组非奇异H-矩阵新的迭代判定条件. 这些判定条件推广和改进了相关已有结果, 丰富和完善了非奇异H-矩阵的理论, 数值算例说明了其有效性.

本文介绍一个面向生物分子模拟的并行有限元解法器, 该解法器基于三维并行自适应有限元软件平台PHG, 计算并模拟在生物溶液系统在静电场下的扩散过程. 该解法器的最新版本在已有算法的基础上, 添加了整体求解、含时求解等一些新算法, 规范并扩展了边界条件的选取, 并整合多项辅助功能,现提供对于~Poisson-Nernst-Planck (PNP) 方程的两个含时算法和四个稳态算法,以及对于~Smoluchowski-Poisson-Boltzmann (SPB) 方程的一个稳态算法. 解法器可模拟生物分子, 离子通道和纳米管等模型, 通过有限元方法计算静电场和离子浓度分布, 并计算电流强度、反应速率等物理量, 可研究离子通道的选择机理, 酶的催化反应过程及反应速率等问题. 相关软件、工具和进展见www.continuummodel.org.

趋化运动是细菌寻找食物、逃离有害物质的核心机制. 对于多细胞生物来说, 趋化运动对其发育和健康更是至关重要. 随着对趋化运动越来越多生物细节的理解, 其数学模型也越来越完备和复杂. 本文以大肠杆菌的趋化运动为例, 回顾了三个不同尺度的模型：上个世纪70年代提出的Keller-Segel模型, 80年代末提出的的速度跳跃模型以及本世纪初提出的含信号通路的动理学方程模型. 我们回顾近30年来这些模型提出的背景、建模思想、分析得到的关于解行为特性的一些主要结论, 以及相关数值算法, 并探讨不同尺度模型之间的联系和区别.

非奇H-矩阵作为一类特殊矩阵, 在科学和工程计算中有着重要的应用. 本文利用迭代系数构造正对角阵, 给出了非奇H-矩阵的一组迭代判别法, 并证明了其充分必要性, 推广和改进了近期的一些结果. 数值算例也说明了该组迭代判别法的有效性.

计算离散Fourier变换(DFT)快速算法的种类各式各样,因此实现FFT程序也是名目繁多的.介绍了一种FFT程序(以下简称程序1),使用它计算一个长度N=2~m(m为大于1的整数)的复数序列需要2Nlog_2N次实数乘法,但这个程序在运算量的节省上还有很大潜力.在此,我们给出一种FFT程序(以下简称程序2),它以程序1为基础,不多占存贮单元,但计算N点复数序列仅需