Aztec在混凝土细观数值模拟中的应用研究

细观数值模拟是混凝土性能研究的一种重要手段,但稀疏线性方程组求解在总体模拟时间中所占比重很大。由于属于三维问题,且规模很大,所以采用预条件Krylov子空间迭代是必由之路。Aztec是国际上专门设计用于求解稀疏线性方程组的软件包之一,由于目前混凝土细观数值模拟中的稀疏线性方程组对称正定,所以利用Aztec中提供的CG迭代法进行求解,并对多种能保持对称性的预条件选项进行了实验比较。结果表明,在基于区域分解的并行不完全Cholesky分解、无重叠对称化GS迭代、最小二乘等预条件技术中,第一种的效率最高,且在重叠度为0,填充层次为0时,效果最好;实验结果还表明,在本应用问题中,用RCM排序一般导致求解时间更长,从而没有必要采用。     

区域分解型并行预条件的一种粗网格校正算法

区域分解是并行计算的基本手段之一,在稀疏线性方程组迭代求解时,对不完全分解等串行计算时很有效的预条件,经常采用区域分解的思想进行并行化。但区域分解的本质是利用局部解来近似全局解,从而必然存在较大误差,为此,提出一种粗网格校正算法,通过非重叠子区域浓缩,每个非重叠子区域浓缩为一个超结点,形成一个含全局信息且阶数等于子区域个数的小线性方程组,之后用其对原并行预条件进行校正。对块Jacobi型、经典加性Schwarz、以及因子组合型并行不完全分解预条件的实验表明,粗网格校正能有效改善收敛性并提高求解效率。     

一种并行ACS-2-opt算法处理TSP问题的方法

针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度。同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度。最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法。实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能。     

一种基于MPI的稀疏化局部尺度并行谱聚类算法的研究与实现

谱聚类算法由于其可识别非凸数据分布、可有效避免局部最优解、不受数据点维数限制等优点,在许多领域得到广泛应用。然而,随着数据量的增大和数据维数的增多,在保证聚类准确性的前提下,尽可能降低计算时间将变得非常必要。此外,影响谱聚类算法聚类质量的因素除数据集本身外,还与所采用的求解距离矩阵的方法、相似性矩阵的尺度参数、Laplacian矩阵形式等多种因素相关。针对以上问题,首先对于大规模数据问题,将MPI并行编程模型应用于谱聚类算法;然后利用t-最近邻方法对谱聚类算法中较大维数的Laplacian矩阵进行近似转化,同时用局部尺度(Local Scaling)参数对算法中的尺度参数进行自动调节。基于上述分析,提出了一种谱聚类并行实现算法,即稀疏化局部尺度并行谱聚类算法SLSPSC,并在四个数据集上进行了测试,与现有的并行谱聚类算法PSC在运行时间和聚类质量两方面做了比较分析。实验结果显示,该算法降低了求解Laplacian矩阵的总时间,同时部分数据集聚类质量得到较大提高。     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

使用均值距离与关联性标记的并行OPTICS算法

针对大数据环境下传统并行密度聚类算法中存在的数据划分不合理,聚类结果准确度不高,结果受参数影响较大以及并行效率低等问题,提出一种MapReduce下使用均值距离与关联性标记的并行OPTICS算法——POMDRM-MR。算法使用一种基于维度稀疏度的减少边界点划分策略（DS-PRBP）,划分数据集;针对各个分区,提出标记点排序识别簇算法（MOPTICS）,构建数据点与核心点之间的关联性,并标记数据点迭代次数,在距离度量中,使用领域均值距离策略（FMD）,计算数据点的领域均值距离,代替可达距离排序,输出关联性标记序列;最后结合重排序序列提取簇算法（REC）,对输出序列进行二次排序并提取簇,提高算法局部聚类的准确性和稳定性;在合并全局簇时,算法提出边界密度筛选策略（BD-FLC）,计算筛选密度相近局部簇;又基于n叉树的并集型合并与MapReduce模型,提出并行局部簇合并算法（MCNT-MR）,加快局部簇收敛,并行合并局部簇,提升全局簇合并效率。对照实验表明,POMDRM-MR算法聚类效果更佳,且在大规模数据集下算法的并行化性能更好。     

自适应谱聚类算法并行实现及优化

谱聚类算法是基于谱图分割理论的聚类方法,其对高维、非凸数据分布问题有很好的聚类效果。但对大规模数据问题的聚类,该方法存在着计算时间和存储空间等方面的瓶颈。本文给出了一个自适应的谱聚类并行算法,通过局部计算和异步循环通信并行方法,最大限度减少了并行谱聚类中数据通信次数,并通过计算与通信重叠策略,进一步降低了并行算法的通信开销。在并行算法实现中,将自主开发的最优预条件共轭梯度法并行求解器 PLOBPCG 用于谱聚类的特征降维。在中科院的“元”超级计算机上,通过对两类大规模数据聚类的测试表明,在 2048 核上的加速比接近线性加速,并行效率达到96%以上。     

基于改进PSRS的并行0-1规划算法

结合0-1整数规划的隐式枚举法对目标排序法进行分析.引入PSRS(并行正则采样排序)算法对目标排序法的核心运算进行并行化,并改进PSRS算法的数据收集策略以适应0-1整数规划的并行隐式枚举.最后给出了基于改进的PSRS的并行0-1整数规划的求解算法,并对算法的时间复杂度进行了分析.     

精确排序的四面体体数据快速可视化

采用投影四面体法进行可视化时需要对所有四面体进行排序,而四面体的不规则性和较强的依赖性导致并行排序的难度很大,为此提出一种精确排序的并行化算法.该算法在排序阶段逐层并行提取互不遮挡的四面体,并在绘制阶段采用区域求和表、提前终止等技术直接减少处理的四面体个数,再将四面体数据集进行有序投影得到最终的绘制结果.实验结果表明,采用文中算法的GPU实现比基于CPU的精确排序快91％;对于大尺度数据集(大于百万个四面体),提前终止的算法使绘制效率提高10％以上.     

一种用于求解多目标组合优化的混合遗传算法 *

为高效求解多目标组合优化问题 ,提出一种进化计算与局部搜索结合的多目标算法。此算法基于个体排序数和密度值进行适应度赋值 ,采用非劣解并行局部搜索策略 ,在解的适应度赋值和局部搜索过程中使用 Pa-reto支配的概念。实验结果表明 ,新算法不仅提高了优化搜索的效率 ,且能够找到更多的近似 Pareto最优解。     

Extension of fractional step techniques for incompressible flows: The preconditioned Orthomin(1) for the pressure Schur complement

The objective of this paper is to present different fractional step schemes in the algebraic context to solve the incompressible Navier–Stokes equations, test them and pick the best one in terms of efficiency and robustness. The equivalence between fractional step schemes and iterative methods for the pressure Schur complement system has been well established in the literature. For example, the classical incremental projection scheme can be associated with a Richardson iteration for the pressure Schur complement plus a correction to enforce the mass conservation. We introduce in this paper an Orthomin(1) iteration which minimizes the Schur complement residual at each solver iteration by using, in the updating step, a factor dynamically computed. Two versions are considered, namely the momentum preserving and continuity preserving versions. The method is compared to the classical Richardson method, including the continuity and momentum preserving versions. In addition, two Schur complement preconditioners are considered and compared, based on the approximation of the weak Uzawa operator. From the implementation point of view, the benefit of the method is two fold. On the one hand, it can be easily implemented starting from the global matrix of the monolithic scheme, without changing the assembly. On the other hand, it enables the use of simple algebraic solvers without the need for complex preconditioners; this is a requirement for massively parallel computers. The four methods are finally tested and compared through the solution of numerical examples. The main conclusion is that with very few additional computation, the Orthomin(1) iteration largely improves the global convergence properties of the fractional schemes here presented.     

Efficient mesh optimization schemes based on Optimal Delaunay Triangulations

In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted L¹ norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.     

基于非结构网格隐式算法的GPU加速研究

针对非结构网格隐式算法在GPU上的加速效果不佳的问题,通过分析GPU的架构及并行模式,研究并实现了基于非结构网格格点格式的隐式LU-SGS算法的GPU并行加速.通过采用RCM和Metis网格重排序（重组）方法,优化非结构网格的数据局部性,改善非结构网格的隐式算法在GPU上的并行加速效果.通过三维机翼算例验证了本文实现的正确性及效率.结果表明两种网格重排序（重组）方法分别得到了63%和69%的加速效果提高.优化后的LU-SGS隐式GPU并行算法获得了相较于CPU串行算法27倍的加速比,充分说明了本文方法的高效性.     

Optimal additive Schwarz preconditioning for hypersingular integral equations on locally refined triangulations

For the non-preconditioned Galerkin matrix of the hypersingular integral operator, the condition number grows with the number of elements as well as the quotient of the maximal and the minimal mesh-size. Therefore, reliable and effective numerical computations, in particular on adaptively refined meshes, require the development of appropriate preconditioners. We propose and analyze a local multilevel preconditioner which is optimal in the sense that the condition number of the corresponding preconditioned system is independent of the number of elements, the local mesh-size, and the number of refinement levels. The theory covers closed boundaries as well as open screens in 2D and 3D. Numerical experiments underline the analytical results and compare the proposed preconditioner to other multilevel schemes as well as techniques based on operator preconditioning.     

针对指令乱序变形技术的归一化研究

新出现的恶意代码大部分是在原有恶意代码基础上修改转换而来.许多变形恶意代码更能自动完成该过程,由于其特征码不固定,给传统的基于特征码检测手段带来了极大挑战.采用归一化方法,并结合使用传统检测技术是一种应对思路.本文针对指令乱序这种常用变形技术提出了相应的归一化方案.该方案先通过控制依赖分析将待测代码划分为若干基本控制块,然后依据数据依赖图调整各基本控制块中的指令顺序,使得不同变种经处理后趋向于一致的规范形式.该方案对指令乱序的两种实现手段,即跳转法和非跳转法,同时有效.最后通过模拟测试对该方案的有效性进行了验证.     

波段排序的高光谱影像3维混合树编码方法

目的 高光谱影像压缩的关键技术是对空间维和光谱维的去相关性。根据高光谱影像数据结构的特点,如何有效去除其空间相关性与谱间相关性是高光谱影像压缩中至关重要的问题。对高光谱影像进行编码时,3维小波变换是极为有效的去除冗余的方法。因此提出了一种通过波段排序并结合3维混合树型结构对高光谱影像3维小波变换系数进行编码的算法。方法 首先,将高光谱影像按照自然波段顺序进行波段分组,并对每组影像进行相邻影像的谱间相关性统计;其次,对相关性较弱的波段组,建立以影像波段序号为顶点、影像相关性系数为边的完全图,对这个完全图求其最大汉密尔顿回路。按照求得的最大汉密尔顿回路顺序对该波段组进行重新排序,从而提高波段组的谱间相关性;在此基础上,对重新排序后的波段组进行3维小波变换,并通过3维混合树结构对3维小波变换系数进行零树编码。结果 通过对大量AVIRIS型高光谱影像数据的仿真实验,验证了本文方法的有效性。对相关性较低的波段组,加入排序算法后,其解码影像与未排序时比,峰值信噪比有了一定的提高。通过实验统计,算法平均用时2.7579s。结论 由于采用了对弱相关性波段组的重新排序机制,使得基于混合树结构的3维零树编码出现了更多有效的零树,在一定程度上提高了编码效率。通过实验统计算法用时,表明该方法以较小的时间代价获得了解码效果的提升。     

Modelling and robust stability of networked control systems with packet reordering and long delay

In this article, modelling and robust stability of networked control systems (NCS) are discussed. Considering the existence of packet reordering and network-induced delay, a new mathematical model of NCS whose network-induced delay is longer than one sampling period is obtained, which can fully describe packet reordering and effectively eliminate the impact of packet reordering on the performance of NCS such that the newest control input can be executed by the actuator. Based on this model, the time-varying NCS is converted into an uncertain discrete linear system with multi-step delay in terms of matrix theory. Furthermore, a sufficient condition for robust stability of NCS is presented. Linear matrix inequality approach has been employed to solve the controller design problems. Numerical examples are compared with previous schemes to demonstrate the effectiveness of the proposed method.     

XML数据更新编码机制——ITBI

编码技术是可扩展标记语言(XML)查询处理的基础,传统编码技术利用自然数进行编码,很难支持XML动态更新。提出了更新支持的编码方法——ITBI,该方法将整数映射到完全二叉树,利用二叉树的中序遍历定义整数新的序关系,通过新的序关系重排自然数序列将静态编码转化为动态编码。同时,基于ITBI前驱、后继、距离等定义,设计了最短位长动态编码分配算法,有效控制更新过程中编码位长的增加。最后通过实验验证了编码的有效性。     

Iterative methods with spectral preconditioning for elliptic equations

We derive two preconditioners for the iterative solution of the linear system arising from Chebyshev approximation of a generalized Helmholtz problem. These preconditioners are constructed as full spectral approximations of a differential problem close in some sense to the original one. The analysis and numerical experiments show the efficiency of these iterative schemes and indicate that they appear as valuable alternative to the usual finite difference or finite element preconditionings.