线性规划的分解原则和算法及其并行计算

1 引 言 并行计算机和并行计算的研究始于七十年代,而并行最优化算法的研究在八十年代中期才得到普遍的重视。近年来随着并行体系结构计算技术的飞速发展,并行最优化的研究也得到迅速的发展,它不仅使求解超大规模最优化问题(包括连续和离散)成为可能,而且对新算法和并行体系计算机结构的研究也产生重要的影响。另一方面,它在军事、工业、交通运输、能源,管理、决策和信息系统的处理等方面均有直接应用的前景,同时它在理论上对运筹学、管理科学、经济决策,系统分析和计算机科学等学科的发展有着重要的推动作用。 本文研究在内点意义下线性规划的分解原则和算法及其并行计算。众所周知,基于单纯形法的线性规划的分解原则是利用凸多面体中的任意一点可以表示为其顶点的凸组合和极射线的非负组合的性质,把原问题转化为求解一系列规模较小的线性规划问题,并通过原     

解无约束极小问题的一个并行共轭方向法

具有并行运算能力的计算机出现,促进了计算方法中的并行算法的发展,因为它是提高计算速度的一个新的重要方面。 1970年Chazan,Miranker在文[1]中,对于无约束极小问题     

解线性方程组的数值对称化方法

本文提出了解下述分块形式的线性方程组一种新的并行数值对称化方法,它是对称区域分裂法的离散模拟。将原问题分裂为四个对称的子问题,求解两个子问题后我们即可得到问题的精确解。它适用于MIMD并行计算机。文末附有数值例子。     

求代数方程组的异步并行混合算法

本文提出了求解代数方程组的一类异步并行算法,它不仅可用于一般的串行或并行计算机,也适用于MIMD计算机。在一定条件下,此算法是收敛的。本文还讨论了这类算法的某些特例,即我们常见的一些迭代算法。     

一种并行结构优化方法

本文提出一种并行结构优化方法,其主要操作均在单元内进行,不需组装总刚和求解系统方程,具有步骤简单,占内存少,计算量小和易于编程的特点。本方法可用在微型机上作结构优化设计,并且特别适用于新一代并行计算机系统。一、前言计算机系统已得到迅速的发展,突出的特点是微型化(microminaturization)和并行化(parallelization)。微型计算机以其低廉的价格和良好的环境适应性为广大工业部门和研究单位所青睐,并行计算机也以其超高速计算能力而得到普遍关注,并在国际上有了相当的应用。并行计算机大致可分为四类:单指令流多数据流(SIMD);多指令流单数据流     

Burgers方程的区域分裂并行格式

1引言 Burgers方程可作为N-S方程的简单形式,这是因为它不仅具有N-S方程的一些特性,而且数值求解方法也相近,因此,对Burgers方程的数值方法的研究具有一定的实际意义.为了在并行计算机上求解Burgers方程,已有不少文章提出了并行差分格式,如组显式方法([1]-[4])、交替分段隐格式[5],这些格式均可归结为交替型的并行格式.     

一种迭代格式的有限元并行算法*

本文提出了一种求解有限元方程的迭代格式的并行算法.该方法在线性代数方程迭代解法的基础上,引进并行运算步骤;并且运用加权残数方法,通过选择适当的权函数,推导了该并行算法的有限元基本格式.该方法在西安交通大学BLXSI-6400并行计算机上程序实现.计算结果表明它能有效地提高运算速度,减少计算时间,是一种有效的求解大型结构有限元方程的并行算法.     

一阶时态逻辑(带等词)的一个完备性定理

一阶时态逻辑是由计算机科学的发展而建立起来的一门逻辑,它是模态逻辑和时态逻辑的一个发展,同时,一阶时态逻辑还具有谓词演算的功能,本文的目的是:为具有广泛应用的带等词的一阶时态逻辑奠定一个基础,建立一个完备性定理。     

发展并行数值方法

1 引言 本世纪40年代中期至50年代初,第一台电子计算机和第一批存储程序计算机即vonNeumann计算机相继问世 。此后,计算机新陈代谢异常迅速,大约每隔5年运算速度增加10倍.50年代的计算机是串行结构,每一时刻只能按照一条指令对一个数据进行操作。由于电子信息传输速度以光速为极限,单靠改进线路已难于得到所期望的计算性能,串行计算机性能已接近了物理极限。为了克服传统计算机结构对提高运行速度的限制,从60年代起人们开始探索将并行性引入计算机结构设计,提出了研制并行计算机的设想。1972年单指令流多数据流并行计算机Illiac Ⅳ投入运行;1976年向量计算机Cray—1投入运行。在整个80年代,具有共享存储的并行向量计算机研制、生产和商售都获得了很大成功。当代高     

弹性接触问题参数变分原理的有限元并行算法*

本文基于弹性接触问题的参数变分原理的有限元解法,利用并行计算机的特性和并行处理结构,建立了相应的并行算法.该算法从刚度阵的生成和组集,静凝聚过程,求应力过程等多方面实现了并行化.该算法在西安交通大学ELXSI-6400并行计算机上程序实现,计算结果表明能有效地节省计算时间,是一种分析接触问题的有效的并行算法.     

大规模稀疏线性规划问题的初等矩阵解法

当线性规划约束条件的系数矩阵A为稀疏矩阵时,一般称为稀疏线性规划问题.解这类问题有分解原则及一般上界法,我们这里讨论初等矩阵法。 §1.齐次线性不等式的初等矩阵解法 [3] 中给出x≥0满足Ax≥0的充要条件是x=K(A)ω,ω≥0.     

A parallel iterative solver for positive-definite systems with hybrid MPI–OpenMP parallelization for multi-core clusters

This article is devoted to the development and study of an algorithm for solving large systems of linear algebraic equations with sparse stiffness matrix on supercomputer by using the preconditioned conjugate gradient method (PCG). An efficient preconditioner is constructed on the basis of the domain decomposition method (the additive Schwarz method) which makes it possible to implement the algorithm on several computing nodes. We describe the parallel algorithm of the action of the stiffness matrix and the preconditioner on a vector. In addition, to increase the computational efficiency we make use of the routines from Intel^®MKL: the direct solver (PARDISO) and the matrix–vector multiplication for sparse matrices (Sparse BLAS). We also study efficiency of using OpenMP directives on each computational node and compare it with pure MPI parallelization. The corresponding performance and scalability charts are presented.     

An asynchronous direct solver for banded linear systems

Banded linear systems occur frequently in mathematics and physics. However, direct solvers for large systems cannot be performed in parallel without communication. The aim of this paper is to develop a general asymmetric banded solver with a direct approach that scales across many processors efficiently. The key mechanism behind this is that reduction to a row-echelon form is not required by the solver. The method requires more floating point calculations than a standard solver such as LU decomposition, but by leveraging multiple processors the overall solution time is reduced. We present a solver using a superposition approach that decomposes the original linear system into q subsystems, where q is the number of superdiagonals. These methods show optimal computational cost when q processors are available because each system can be solved in parallel asynchronously. This is followed by a q×q dense constraint matrix problem that is solved before a final vectorized superposition is performed. Reduction to row echelon form is not required by the solver, and hence the method avoids fill-in. The algorithm is first developed for tridiagonal systems followed by an extension to arbitrary banded systems. Accuracy and performance is compared with existing solvers and software is provided in the supplementary material.     

A practical solution for KKT systems

We consider KKT systems of linear equations with a 2 × 2 block indefinite matrix whose (2, 2) block is zero. Such systems arise in many applications. Treating such matrices would encounter some intricacies, especially when its (1, 1) block, i.e., the stiffness matrix in term of computational mechanics, is rank-deficient. It is the rank-deficiency of the stiffness matrix that leads to the so-called rigid-displacement issue. This is believed to be one of the main reasons that many programmers would unwillingly give up the Lagrange multiplier method but select the penalty method. Based on the Sherman–Morrison formula and the conventional LDL^T decomposition for symmetric positive definite matrices, a robust direct solution is proposed, which is amenable to the conventional finite element codes, competent for both nonsingular and singular stiffness matrices, and particularly suitable to parallel computation. As a paradigm, the application to the element-free Galerkin method (EFGM) with the moving least squares interpolation is illustrated. Funded by the National Natural Science Foundation of China (NSFC), Project no. 90510019.     

分布式系统上并行矩阵乘法

1．引言矩阵乘法是最简单的数学问题,同时由于其计算量大而通常被用来对计算机的浮点运算速度进行测试,尤其是对于并行计算机,其并行效率的好坏可通过这个简单的问题反应出来,如果在这个问题上都不能取得很好的效果,对于其它问题就更不可能．此外,为了提高计算性能,对求解数值代数中的问题最终会归结到有矩阵乘法的计算,如LAPACK,ScaLAPACK等,因此有效地并行计算矩阵乘法在实际应用中是非常重要的．矩阵乘法是做C＝A×B,其中A是m×k阵,B是k×n阵,C是m×n阵．设矩阵A,B可以分成p×p块矩阵,即A＝（Ai,j）p×p,B＝（B…     

A memory‐efficient finite volume method for advection‐diffusion‐reaction systems with nonsmooth sources

We present a parallel matrix‐free implicit finite volume scheme for the solution of unsteady three‐dimensional advection‐diffusion‐reaction equations with smooth and Dirac‐Delta source terms. The scheme is formally second order in space and a Newton–Krylov method is employed for the appearing nonlinear systems in the implicit time integration. The matrix‐vector product required is hardcoded without any approximations, obtaining a matrix‐free method that needs little storage and is well‐suited for parallel implementation. We describe the matrix‐free implementation of the method in detail and give numerical evidence of its second‐order convergence in the presence of smooth source terms. For nonsmooth source terms, the convergence order drops to one half. Furthermore, we demonstrate the method's applicability for the long‐time simulation of calcium flow in heart cells and show its parallel scaling. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq31: 143–167, 2015     

关于矩阵族稳定的(J)条件及其与Buchanan准则的关系

本文注意到矩阵族稳定的Kreiss定理和Buchanan准则不便于实际应用。文中(§2,§3)从Kreiss定理的豫解条件出发得到了至少对于四阶以下矩阵族较为实用的判别稳定性的(J)条件;并证明了对于其特征值赋套的上三角矩阵族,(J)条件与Buchanan准则的等价性。§4作为(J)条件的应用讨论了逼近于二维、三维波动方程的显式差分方程(其增长矩阵分别是三、四阶矩阵族),得到了稳定的充要条件。     

Optimal Control for Static Stiffness and Thermal Sensitivity of a Hexapod Machine Tool

Beneath many conceptual advantages, parallel kinematic manipulators suffer some disadvantages which complicate their operation as machine tool. One of them is their inhomogeneous stiffness characteristic within the workspace, another is the high thermal sensitivity of their static accuracy due to the large strut lengths. Both properties, stiffness and thermal sensitivity, depend strongly on the configuration of the manipulator. As for machining purposes only five degrees of freedom are necessary, the 6th axis can be utilized to choose an optimal configuration with respect to stiffness or thermal sensitivity. In this contribution, an optimization method based on Jacobian matrix analysis is introduced and demonstrated for a model of the hexapod milling machine HEXACT. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

一类非线性代数方程组的并行算法——适用于MIMD系统

为连续对角映射.而A=(a_(ij)∈L(R~n)是单调矩阵,B∈L(R~n)为非负矩阵,b∈R~n为已知向量. 方程组(1.1)具有丰富的实际背景,许多非线性微分方程的求解问题,经过有限元或差分离散,均可归纳为(1.1)的求解.特别,如[7],[10]以及[11]讨论的弱非线性椭圆方程和Stefan问题等,均可作为(1.1)的特例.     

FSAI-based parallel Mixed Constraint Preconditioners for saddle point problems arising in geomechanics

In this paper we propose and describe a parallel implementation of a block preconditioner for the solution of saddle point linear systems arising from Finite Element (FE) discretization of 3D coupled consolidation problems. The Mixed Constraint Preconditioner developed in [L. Bergamaschi, M. Ferronato, G. Gambolati, Mixed constraint preconditioners for the solution to FE coupled consolidation equations, J. Comput. Phys., 227(23) (2008), 9885–9897] is combined with the parallel FSAI preconditioner which is used here to approximate the inverses of both the structural (1, 1) block and an appropriate Schur complement matrix. The resulting preconditioner proves effective in the acceleration of the BiCGSTAB iterative solver. Numerical results on a number of test cases of size up to 2×10⁶ unknowns and 1.2×10⁸ nonzeros show the perfect scalability of the overall code up to 256 processors.