A numerical seismic 3-D migration model for vector multiprocessors

The availability of a multiprocessor vector machine, such as the CRAY X-MP, along with large, fast secondary memory such as the CRAY SSD, opens new frontiers to numerical algorithm design for 3-D simulations. The 3-D seismic migration, which is of crucial importance in exploration seismology, will be studied as a model problem. The numerical model discussed in this paper employs an alternating direction implicit (ADI) Crank—Nicolson scheme which takes full advantage of the parallel architecture of the underlying machine. It is demonstrated that careful algorithm design can lead to a significant speedup of the calculation when more than one processor is used. The throughput times obtained in this study are an order of magnitude faster than some conventional approaches.     

Preconditioned accelerated generalized successive overrelaxation method for solving complex symmetric linear systems

In this paper, by adopting the preconditioned technique for the accelerated generalized successive overrelaxation method (AGSOR) proposed by Edalatpour et al. (2015), we establish the preconditioned AGSOR (PAGSOR) iteration method for solving a class of complex symmetric linear systems. The convergence conditions, optimal iteration parameters and corresponding optimal convergence factor of the PAGSOR iteration method are determined. Besides, we prove that the spectral radius of the PAGSOR iteration method is smaller than that of the AGSOR one under proper restrictions, and its optimal convergence factor is smaller than that of the preconditioned symmetric block triangular splitting (PSBTS) one put forward by Zhang et al. (2018) recently. The spectral properties of the preconditioned PAGSOR matrix are also proposed. Numerical experiments illustrate the correctness of the theories and the effectiveness of the proposed iteration method and the preconditioner for the generalized minimal residual (GMRES) method.     

Multitasking the conjugate gradient method on the CRAY X-MP/48

We show how to efficiently implement the preconditioned conjugate gradient method on a four processors computer CRAY X-MP/48. We solve block tridiagonal systems using block preconditioners well suited to parallel computation. Numerical results are presented that exhibit nearly optimal speedup and high Mflops rates.     

Vectorized algorithms for solving special tridiagonal systems

Solving special tridiagonal systems often arise in the fields of engineering and science. This special tridiagonal system is diagonally dominant and circulant near-Toeplitz. This paper presents two fast vectorized algorithms for solving special tridiagonal systems. Both algorithms employ the matrix perturbation technique and have many computational advantages on vector supercomputer. The related error analysis are also given. Some experimental results are illustrated on vector uniprocessor of the CRAY X-MP EA/116se.     

Implementation of two projection methods on a shared memory multiprocessor: DEC VAX 6240

In this paper, we compare the relative performance of two iterative schemes, based on projection techniques, on a shared memory multiprocessor - VAX 6240. We consider the CG accelerated Block-SSOR method and the CG accelerated Symmetric-Kaczmarz method for the solution of large non-symmetric systems of linear equations. We show that the regular structure of many matrices can be exploited by the CG-accelerated Block-SSOR method to provide good speedup in a multiprocessing environment. However, the CG accelerated Symmetric-Kaczmarz method, while being a viable alternative on a scalar machine, is unable to benefit from multiprocessing.     

A class of explicit preconditioned conjugate gradient methods for solving large finite element systems

A class of Explicit Preconditioned Conjugate Gradient (EPCG) methods for solving large sparse linear systems of algebraic equations resulting from the Finite Element discretization of Elliptic and Parabolic PDE's is introduced. The EPCG methods are based on explicit Approximate Inverse Matrix techniques and are particularly suitable for solving numerically initial/boundary-value problems on multiprocessor systems. The application of the new methods on 2D-linear boundary-value problems is discussed and numerical results are given.     

A parallel block row-action method for solving large sparse linear systems on distributed memory multiprocessors

Recently developed block-iterative versions of some row-action algorithms for solving general systems of sparse linear equations allow parallelism in the computations when the underlying problem is appropriately decomposed. However, problems associated with the parallel implementation of these algorithms have to be addressed. In this paper we present an implementation on distributed memory multiprocessors of a block version of the Kaczmarz row-action method. One of the main issues related to the efficient implementation of this method on a concurrent environment is to develop suitable communication schemes in order to reduce the amount of communication needed at each iteration. We propose two data distribution strategies which lead to different computation and communication schemes. To verify and compare the effectiveness of the proposed strategies, numerical experiments have been carried out on a Symult S2010 and a Meiko Computing Surface. The performance evaluation has been done using a scaled efficiency model.     

A projection method for the numerical solution of linear systems in separable stiff differential equations

This paper deals with the efficient implementation of implicit methods for solving stiff ODEs, in the case of Jacobians with separable sets of eigenvalues. For solving the linear systems required we propose a method which is particularly suitable when the large eigenvalues of the Jacobian matrix are few and well separated from the small ones. It is based on a combination of an initial iterative procedure, which reduces the components of the vector error along to the nondominant directions of J and a projection Krylov method which reduces the components of the vector error along to the directions corresponding to the large eigenvalues. The technique solves accurately and cheaply the linear systems in the Newton's method, and computes the number of stiff eigenvalues of J when this information is not explicitly available. Numerical results are given as well as comparisons with the LSODE code.     

A parallel Monte Carlo transport algorithm using a pseudo-random tree to guarantee reproducibility

We present a parallel Monte Carlo photon transport algorithm that insures the reproducibility of results. The important feature of this parallel implementation is the introduction of a pair of pseudo-random number generators. This pair of generators is structured in such a manner as to insure minimal correlation between the two sequences of pseudo-random numbers produced. We term this structure as a ‘pseudo-random tree’. Using this structure, we are able to reproduce results exactly in a asynchronous parallel processing environment. The algorithm tracks the history of photons as they interact with two carbon cylinders joined end to end. The algorithm was implemented on both a Denelcor HEP and a CRAY X-MP/48. We describe the algorithm and the pseudo-random tree structure and present speedup results of our implementation.     

基于直线投影特征的镜头畸变校正方法

针对摄像机镜头畸变校正方法的简便和快速问题,设计了基于直线投影特征的校正方法。介绍了镜头主要畸变产生原因和畸变模型;给出直线三点在理想投影下的关系,确定了适应度函数,利用遗传算法得到了畸变参数组最优解。基于matlab软件编写校正程序,并进行了实验验证。实验表明,利用畸变参数组的最优解能够实现图像畸变校正,效果较好。该标定方法只需场景内有直线存在即可实现对摄像机镜头畸变参数校正,方法所需实验条件简单,程序简便,便于现场快速校正。     

A novel algorithm and its parallelization for solving nearly penta-diagonal linear systems

In the current paper, a new serial algorithm for solving nearly penta-diagonal linear systems is presented. The computational cost of the algorithm is less than or almost equal to those of recent successful algorithms [J. Jia, Q. Kong, and T. Sogabe, A fast numerical algorithm for solving nearly penta-diagonal linear systems, Int. J. Comput. Math. 89 (2012), pp. 851–860; X.G. Lv and J. Le, A note on solving nearly penta-diagonal linear systems, Appl. Math. Comput. 204 (2008), pp. 707–712; S.N. Neossi Nguetchue and S. Abelman, A computational algorithm for solving nearly penta-diagonal linear systems, Appl. Math. Comput. 203 (2008), pp. 629–634]. Moreover, it is suitable for developing its parallel algorithms. One of the parallel algorithms is given and is shown to be promising. The implementation of the algorithms using Computer Algebra Systems such as MATLAB and MAPLE is straightforward. Two numerical examples are given in order to illustrate the validity and efficiency of our algorithms.     

基于梯度投影法与随机优化算法的约束优化方法

针对带有线性等式和不等式约束的无确定函数形式的约束优化问题,提出一种利用梯度投影法与遗传算法、同时扰动随机逼近等随机算法相结合的优化方法。该方法利用遗传算法进行全局搜索,利用同时扰动随机逼近算法进行局部搜索,算法在每次进化时根据线性约束计算父个体处的梯度投影方向,以产生新个体,从而能够严格保证新个体满足全部约束条件。将上述约束优化算法应用于典型约束优化问题,其仿真结果表明了所提出算法的可行性和收敛性。     

A split-correct parallel algorithm for solving tridiagonal symmetric toeplitz systems

In 1994, Yan and Chung produced a fast algorithm for solving a diagonally dominant symmetric Toeplitz tridiagonal system of linear equations Ax = b. In this work a method will be presented which will allow for problems of the above nature to be split into two separate systems which can be solved in parallel, and then combined and corrected to obtain a solution to the original system. An error analysis will be provided along with example cases and time comparison results.     

Fast projection methods for minimal design problems in linear system theory

The so-called minimal design problem (or MDP) of linear system theory is to find a proper minimal degree rational matrix solution of the equation H(z)D(z)=N(z), where {N(z),D(z)} are given p×r and m×r polynomial matrices with D(z) of full rank r≦m.We describe some solution algorithms that appear to be more efficient (in terms of number of computations and of potential numerical stability) than those presently known. The algorithms are based on the structure of a polynomial echelon form of the left minimal basis of the so-called generalized Sylvester resultant matrix of {N(z), D(z)}. Orthogonal projection algorithms that exploit the Toeplitz structure of this resultant matrix are used to reduce the number of computations needed for the solution.     

A parallel partition method for solving banded systems of linear equations

The partition method of Wang for tridiagonal equations is generalized to the arbitrary band case. A stability criterion is given. The algorithm is compared to Gaussian elimination and cyclic reduction.     

A direct method for solving linear systems

In this work we propose a direct method for solving systems of linear equations which is based on a successive LU-decomposition of matrices of the form l + uv ^T . Simultaneously, the factors of an LU-decomposition of the coefficient matrix are obtained. A specific choice of the “rank-one decomposition” of the given matrix leads to a variant of the Gauss elimination process.     

An efficient two-step iterative method for solving a class of complex symmetric linear systems

In this paper, a new two-step iterative method called the two-step parameterized (TSP) iteration method for a class of complex symmetric linear systems is developed. We investigate its convergence conditions and derive the quasi-optimal parameters which minimize the upper bound of the spectral radius of the iteration matrix of the TSP iteration method. Meanwhile, some more practical ways to choose iteration parameters for the TSP iteration method are proposed. Furthermore, comparisons of the TSP iteration method with some existing ones are given, which show that the upper bound of the spectral radius of the TSP iteration method is smaller than those of the modified Hermitian and skew-Hermitian splitting (MHSS), the preconditioned MHSS (PMHSS), the combination method of real part and imaginary part (CRI) and the parameterized variant of the fixed-point iteration adding the asymmetric error (PFPAE) iteration methods proposed recently. Inexact version of the TSP iteration (ITSP) method and its convergence properties are also presented. Numerical experiments demonstrate that both TSP and ITSP are effective and robust when they are used either as linear solvers or as matrix splitting preconditioners for the Krylov subspace iteration methods and they have comparable advantages over some known ones for the complex symmetric linear systems.     

A modified projection method for linear feasibility problems

In this paper, we present a modified projection method for the linear feasibility problems （LFP）. Compared with the existing methods, the new method adopts a surrogate technique to obtain new iteration instead of the line search procedure with fixed stepsize. For the new method, we first show its global convergence under the condition that the solution set is nonempty, and then establish its linear convergence rate. Preliminary numerical experiments show that this method has good performance.     

The convergence factor of the parallel Schwarz overrelaxation method for linear systems

After introducing the parallel Schwarz overrelaxation method for linear systems, we analyse the convergence factor of the method in detail. The optimal overrelaxation parameter ω of the method is discussed in this paper. Some examples are also shown.