Relaxed parallel two-stage multisplitting methods ∗

Two classes of relaxed parallel two-stage multisplitting methods based on extrapolated and AOR methods are studied for the solution of nonsingular linear systems, which are called outer relaxed or inner relaxed parallel two-stage multisplitting methods. Convergence of these methods is studied for H-matrix. Furthermore, computational results about these methods on a shared memory multiprocessor are presented. The results show that the methods we proposed are better than the corresponding existed parallel (two-stage) multisplitting methods.     

A note on parallel multisplitting TOR method for H-matrices

In 2001, Chang studied the convergence of parallel multisplitting TOR method for H-matrices [D.W. Chang, The parallel multisplitting TOR(MTOR) method for linear systems, Comput. Math. Appl. 41 (2001), pp. 215–227]. In this paper, we point out some gaps in the proof of Chang's main results solving them. Moreover, we improve some of Chang's convergence results. A numerical example is presented in order to illustrate the improvement of Chang's convergence region.     

Asynchronous multisplitting relaxation methods for linear complementarity problems

To solve the linear complementarity problems efficiently on the high-speed multiprocessor systems, we set up a class of asynchronous parallel matrix multisplitting accelerated over-relaxation (AOR) method by technical combination of the matrix multisplitting and the accelerated overrelaxation techniques. The convergence theory of this new method is thoroughly established under the condition that the system matrix of the linear complementarity problem is an H-matrix with positive diagonal elements. At last, we also make multi-parameter extension for this new asynchronous multisplitting AOR method, and investigate the convergence property of the resulted asynchronous multisplitting unsymmetric AOR method. Thereby, an extensive sequence of asynchronous parallel relaxed iteration methods in the sense of multisplitting is presented for solving the large scale linear complementarity problems in the asynchronous parallel computing environments. This not only affords various choices, but also presents systematic convergence theories about the asynchronous parallel relaxation methods for solving the linear complementarity problems.     

定常二级迭代法与其外迭代法收敛性的比较

研究了定常二级迭代法的收敛性,得到了定常二级迭代法与其外迭代收敛率的比较定理。结果表明外迭代的收敛速度一般快于定常二级迭代法,还给出了H-矩阵迭代法的比较结论。最后,数值例子验证了结论。     

Iterative solvers of Ax = b derived from ode's numerical integration methods

Although iterative methods for solving linear systems has been the subject of study for a long time, the acceleration of such methods is still object of interest, research focusing in improvements of already known methods as well as on new, faster ones. In this sense we can cite among several other authors, for example, the works of Martins [8], Hadjidimos [9] and Evans [7]. The purpose of this paper is twofold. First we show that the numerical integration methods for Ordinary Differential Equations, obtained by Taylor expansions, result in a B-extrapolation method [3] for iteratively solving linear algebraic systems. Second, we compare the best rates of convergence of the algorithms developed here, with the best rate of convergence of the Jacobi Over-Relaxation method, (JOR), proving that depending on the choice of the step of integration and the behavior of the spectrum of the matrix A of the original system Ax = b the third order methods derived from the Taylor expansions can be better than the JOR. The procedure used here with the splitting A – I – J can also be easely applied to other splittings, resulting in a comparison of the convergence of the present method with the SOR or iterations methods or any other linear iterative methods of degree one.     

Scheduling parallel iterative methods on multiprocessor systems

The paper describes the implementation of the Successive Overrelaxation (SOR) method on an asynchronous multiprocessor computer for solving large, linear systems. The parallel algorithm is derived by dividing the serial SOR method into noninterfering tasks which are then combined with an optimal schedule of a feasible number of processors. The important features of the algorithm are: (i) achieves a speedup S_p O(N/3) and an efficiency E_p 2/3 using P = [N/2] processors, where N is the number of the equations, (ii) contains a high level of inherent parallelism, whereas on the other hand, the convergence theory of the parallel SOR method is the same as its sequential counterpart and (iii) may be modified to use block methods in order to minimise the overhead due to communication and synchronisation of the processors.     

MPI implementation of parallel subdomain methods for linear and nonlinear convection–diffusion problems

The solution of linear and nonlinear convection–diffusion problems via parallel subdomain methods is considered. MPI implementation of parallel Schwarz alternating methods on distributed memory multiprocessors is discussed. Parallel synchronous and asynchronous iterative schemes of computation are studied. Experimental results obtained from IBM-SP series machines are displayed and analyzed. The benefits of using parallel asynchronous Schwarz alternating methods are clearly shown.     

Developing Bi-CG and Bi-CR methods to solve generalized Sylvester-transpose matrix equations

The bi-conjugate gradients(Bi-CG)and bi-conjugate residual(Bi-CR)methods are powerful tools for solving nonsymmetric linear systems Ax=b.By using Kronecker product and vectorization operator,this paper develops the Bi-CG and Bi-CR methods for the solution of the generalized Sylvester-transpose matrix equationp i=1(Ai X Bi+Ci XTDi)=E(including Lyapunov,Sylvester and Sylvester-transpose matrix equations as special cases).Numerical results validate that the proposed algorithms are much more efcient than some existing algorithms.     

Multiple search direction conjugate gradient method I: methods and their propositions

In this article, we proposed a new CG-type method based on domain decomposition method, which is called multiple search direction conjugate gradient (MSD-CG) method. In each iteration, it uses a search direction in each subdomain. Instead of making all search directions conjugate to each other, as in the block CG method [O'Leary, D. P. (1980). The block conjugate gradient algorithm and related methods. Lin. Alg. Appl., 29, 293–322.], we require that they are nonzero in corresponding subdomains only. The GIPF-CG method, an approximate version of the MSD-CG method, only requires communication between neighboring subdomains and eliminate global inner product entirely. This method is therefore well suited for massively parallel computation. We give some propositions and a preconditioned version of the MSD-CG method.     

Consistency and relative efficiency of subspace methods

We give a consistency proof for two subspace methods. We then show the asymptotic equivalence of a special subspace method and the initial estimate proposed by Hannan and Rissanen. Finally, a simulation study comparing two subspace methods and the maximum-likelihood method is performed.