异步并行矩阵多分裂块松弛迭代算法

1 引言 众所周知,许多微分方程经过差分或有限元离散,即可归结为线性代数方程组 Ax=b,A∈L(R~n)非奇异,x,b∈R~n.(1.1)缘于原问题的物理特性,系数矩阵A∈L(R~n)通常是大型稀疏的,并且具有规则的分块结构。鉴此,文[1]基于矩阵多重分裂的概念,并运用线性迭代法的松弛加速技巧,提出了求解这类大型稀疏分块线性代数方程组的并行矩阵多分裂块松弛迭代算法,并在适当的条件下建立了算法的收敛理论。对于SIMD多处理机系统,这类算法是颇为适用和行之有效的。     

计算简单分歧点的Weber辅助方程离散Newton法

1.引言 本文考虑单参数有限维非线性方程组G:??R~n×R~1→R~n, G(x,λ)=0 x∈R~n,λ∈R (1.1)的数值求解.方程组(1.1)的解在集合     

弱半光滑函数总体极小的广义填充函数法

设F:R~n→R为目标函数,并设F存在极小点。我们的目的是求出x∈R~n使得对所有的x∈R~n有 F(X)≤ F(x). (1.1)即求解F的总体极小. 关于求总体极小问题,到目前为止尚无理论上较为成熟、实际计算中又较为有效的方法.葛人溥在[1]中提出一种求解(1.1)的填充函数法.其基本想法是利用填充函数逐次求     

线性互补问题的一个正则互补模型

正1引言线性互补问题的一般形式为z~TF(z)=0,F(z):=Az+q≥0,z≥0,(1)简记为LCP(A,q),其中A∈R~(n×n),q∈R~n已知,z∈R~n为所求.线性互补问题最早产生于求解非线性规划问题时所需要的KKT优化条件.随着科学的发展,线性互补问题在经济和工程方面出现比较多,参见[1,2,3,4]等.几十年来,线性互补问题LCP(A,q)得到很多学者的重视,在此研究领域有丰富的成果,参见文献[5,6]及其中参考文献.对于任意的q,线性互补问题LCP(A,q)都存在唯一解的充分必要条件是A具有各阶正主子式.这类矩阵称为P-矩阵,如正定矩阵和H_+-矩     

大型线性最小二乘问题的并行矩阵多分裂松弛算法

寻求超定方程组 Ax=b,(1.1) A∈L(R~n,R~m),x∈R~n,b∈R~m,m>n,Rank(A)=n的最小二乘解,是一个熟知而又非常实际的问题,尤其在现代科技迅速发展的条件下,(1.1)中的A∈L(R~n,R~m)多数为大型的且具有稀疏特征的矩阵。此时,对其满足法方程组     

求解方程组Ax+φ(x)=0的条件预优处理

§1 引言 在实际应用中,常会遇到求解方程组 Ax+φ(x)=0 (1)的问题,此处A为n×n阶实矩阵,x∈R~n,φ:R~n→R~n为非线性算子,在[1]中指出了下面的结论:     

高阶稀疏局部非线性方程组的一种拟牛顿方法

§1.引言 当用有限元法或有限差分法分析非线性偏微分方程问题时,必然会导致求解非线性方程组的问题,即求 F(x)=0 (1.1)的解.其中,x=(x_1,x_2,…,Xx_n)~T∈D,D?R~n;F:D→R~n是一个非线性映射.因此,有效地求解非线性方程组(1.1),是分析相应的非线性问题的关键. 不管这些非线性问题是来自流体力学、固体力学,还是其他的物理范畴,它们所对应     

阻尼牛顿法迭代中病态问题趋于稳定的渐变(瞬变)过程分析

<正>1引言设映像F:DR~n→R~n,考虑非线性方程组F(x)=0,x∈DR~n,其中F(x)=(f_1(x),f_2(x),…,f_n(x))T,分量f_i(x):R~n→R(i=1,2,…,n)是连续可微实值函数.目前,非线性方程组求解的数值方法有牛顿法、同伦型法、单纯形法与胞腔排除法等[1]~[3]牛顿法是一种非常实用的计算方法,迭代公式如下x=x+p,(2)其中x为前次迭代近似,x为紧接着x后的迭代近似,p=-[F'(x)]~(-1)F(x)为牛顿修正,F'(x)为x处的雅可比矩阵.     

预条件同时置换(PSD)迭代法的收敛性分析

1引言求解线性方程组Ax=6,(1.1)其中A∈R~(n×n)非奇异阵且对角元非零,x,b∈R~n,x未知,b已知.不失一般性,我们假设A=I-L-U,(1.2)其中L,U分别为A的严格下和上三角矩阵,相应的Jacobi迭代矩阵为B=L U.(1.3)若Q是非奇异阵且Q~(-1)易计算,于是(1.1)可以变成     

一个算法的收敛性

§1.结果 在n维Euclidean空间R~n中给定一族闭凸集{Q_i}_(i=1)~(m-1),而且 S=∩Q_i≠φ, i=0求x∈S?R~n.在[1]中给出求解这个问题的迭代公式为     

APPLICATION OF NEWTON''''S AND CHEBYSHEV''''S METHODS TO PARALLEL FACTORJZATION OF POLYNOMIALS

1. IntroductionLet F: RN --+ RN be a nonlinear map. Nixon)s methodand Chebyshev's methodare well known tor solved nothear equationwhere I is the "lift mains of order N, x is an approtoation of the solution x* of (1.3), x+ and& are new approAnations Of x* produced by Newton's and Chebyshev's methods, respectively.It is wen known that the order of convergence for Newton's ac chebyshev's methods is 2 and3, re8Pectively, if F'(x*) is nonSedar.Letbe a monic poly'nondal of degree N = Zn. The…     

Parallel processing for fuzzy sets operations

Binary operations with fuzzy sets using parallel computing are investigated. A parallel algorithm for merging pairs is presented with a special functionality of the comparators.     

A new algorithm for special Vandermonde systems

In this paper a new algorithm for solving special Vandermonde systems is presented, useful when then points defining the matrix are thek th roots ofm complex numbers (n=km); if they are real and positive andn=2m, the usual case of real points symmetrically ranged around zero is obtained. The algorithm is based on an inverse matrix formulation by means of the Kronecker product and is particularly suitable for parallel implementation. Its computational complexity is analysed and compared both in the sequential and parallel formulation.     

A parallel algorithm for large systems of Volterra integral equations of Abel type

A significative number of recent applications require numerical solution of large systems of Abel–Volterra integral equations. Here we propose a parallel algorithm to numerically solve a class of these systems, designed for a distributed-memory MIMD architecture. In order to achieve a good efficiency we employ a fully parallel and fast convergent waveform relaxation (WR) method and evaluate the lag term by using FFT techniques. To accelerate the convergence of the WR method and to best exploit the parallel architecture we develop special strategies. The performances of the resulting code, NSWR4, are illustrated on some examples.     

第一类曲面积分的一类特殊解法

对一些特殊曲面(如柱面、旋转曲面)上的第一类曲面积分,转化为二重积分的基本方法可能非常复杂,用类似计算三重积分的平行截面法能更简洁地解决此类问题.     

A Linear Risk Model

A special structure optimization model is presented which includes many of the single variable risk problems that are encountered in operational problems. A risk function is assumed which is a piece-wise linear function of some random variable whose distribution is known; one seeks the value of the decision variable which minimizes expected risk. In this paper are presented the necessary and sufficient conditions for this optimization for random variables which are either continuously or discretely distributed. The important special case of a continuous risk function is discussed; multiple risk problems with a joint constraint are analyzed; and the change in policy for a small change in the distribution of the random variable is investigated. Examples illustrate the application of the model.     

A method of iterative data refinement and its applications

Iterative data refinement (IDR) is a general procedure for producing a sequence of estimates of the data that would be collected by a measuring device which is idealized to a certain extent, starting from the data that are collected by an actual measuring device. Following a discussion of the fundamentals of IDR, we present a number of previously published procedures which are special cases of it. We concentrate on examples from medical imaging. In particular, we discuss beam hardening correction in x-ray computerized tomography, attenuation correction in emission computerized tomography, and compensation for missing data in reconstruction from projections. We also show that a standard method of numerical mathematics (the parallel chord method) as well as a whole family of constrained iterative restoration algorithms are special cases of IDR. Thus IDR provides a common framework within which a number of originally different looking procedures are presented and discussed. We also present a result of theoretical nature concerning the initial behavior of IDR.     

A new class of vector spaces

Reciprocal vectors and reciprocal vector spaces are defined. The special case of symmetric vectors is considered. Reciprocal linear transformations and the symmetrical homomorphism are introduced and some properties presented.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

A non-LEA sofic group

We describe elementary examples of finitely presented sofic groups which are not residually amenable (and thus not initially subamenable or LEA, for short). We ask if an amalgam of two amenable groups over a finite subgroup is residually amenable and answer this positively for some special cases, including countable locally finite groups, residually nilpotent groups and others.