Parallel solvers for the depletion region identification in metal semiconductor field effect transistors

In this work we are interested in a sufficiently accurate approximation of the steady-state potentials in a Metal Semiconductor Field Effect Transistor (MESFET), which can be obtained with the so-called depletion region approximation (see [5]). We propose a robust method based on the shape optimization techniques to analyze and compute the depletion boundary as a function of the applied voltage and the geometry material properties of the device. During the optimization process several intermediate direct problems are solved using the boundary element method (BEM). To accelerate the solutions of of these systems we use a strategy of subdividing the domain into a number of smaller subdomains [11,9]. The scheme is iterative and each subdomain is handled by a separate node in parallel. Test runs comparing the performance of the parallel with the serial code, and other numerical discussions are presented. AMS subject classification 65N55, 65N38, 65K10, 78A55. A. Nachaoui: Corresponding author.     

Numerical performance of parallel group explicit solvers for the solution of fourth order elliptic equations

Many applications in applied mathematics and engineering involve numerical solutions of partial differential equations (PDEs). Various discretisation procedures such as the finite difference method result in a problem of solving large, sparse systems of linear equations. In this paper, a group iterative numerical scheme based on the rotated (skewed) five-point finite difference discretisation is proposed for the solution of a fourth order elliptic PDE which represents physical situations in fluid mechanics and elasticity. The rotated approximation formulas lead to schemes with lower computational complexities compared to the centred approximation formulas since the iterative procedure need only involve nodes on half of the total grid points in the solution domain. We describe the development of the parallel group iterative scheme on a cluster of distributed memory parallel computer using Message-Passing Interface (MPI) programming environment. A comparative study with another group iterative scheme derived from the centred difference formula is also presented. A detailed performance analysis of the parallel implementations of both group methods will be reported and discussed.     

径向基插值BFGP算法的一种异步并行格式

本文研究了多变量散乱数据插值问题,利用径向基函数方法,得到了并行迭代格式及其收敛性,改进了BFGP算法.     

Numerical analysis for the quadratic matrix equations from a modification of fixed‐point type

In this paper, we study the quadratic matrix equations. To improve the application of iterative schemes, we use a transform of the quadratic matrix equation into an equivalent fixed‐point equation. Then, we consider an iterative process of Chebyshev‐type to solve this equation. We prove that this iterative scheme is more efficient than Newton's method. Moreover, we obtain a local convergence result for this iterative scheme. We finish showing, by an application to noisy Wiener‐Hopf problems, that the iterative process considered is computationally more efficient than Newton's method.     

The effect of block red-black ordering on blockILU preconditioner for sparse matrices

It is well known that the ordering of the unknowns can have a significant effect on the convergence of a preconditioned iterative method and on its implementation on a parallel computer. To do so, we introduce a block red-black coloring to increase the degree of parallelism in the application of the blockILU preconditioner for solving sparse matrices, arising from convection-diffusion equations discretized using the finite difference scheme (five-point operator). We study the preconditioned PGMRES iterative method for solving these linear systems.     

Synchronous and asynchronous solution of a 3D transport model in a grid computing environment

Numerical simulation is a common approach to understand many phenomena, usually yielding a computationally intensive problem. To overcome insufficient computer capacity and computational speed, a grid computing environment is a suitable approach. In this paper we focus on the development of parallel algorithms to solve a 3D transport model in such a context. The solver is based on the multisplitting Newton method that provides a coarse-grained scheme. Algorithms are implemented using JACE, a grid-enabled Java Asynchronous Computing Environment. This programming environment allows users to design synchronous and asynchronous parallel iterative algorithms as well. Experiments are carried out on a heterogeneous grid environment in which the behaviour of both parallel iterative algorithms is analysed. The results allow us to draw some conclusions about the use of the programming library JACE and the design of parallel iterative algorithms in a grid computing environment.     

A Robin-type non-overlapping domain decomposition procedure for second order elliptic problems

This article deals with the analysis of an iterative non-overlapping domain decomposition (DD) method for elliptic problems, using Robin-type boundary condition on the inter-subdomain boundaries, which can be solved in parallel with local communications. The proposed iterative method allows us to relax the continuity condition for Lagrange multipliers on the inter-subdomain boundaries. In order to derive the corresponding discrete problem, we apply a non-conforming Galerkin method using lowest order Crouzeix–Raviart elements. The convergence of the iterative scheme is obtained by proving that the spectral radius of the matrix associated with the fixed point iterations is less than 1. Parallel computations have been carried out and the numerical experiments confirm the theoretical results established in this paper.     

An implicit iterative scheme for monotone variational inequalities and fixed point problems

In this paper we introduce an implicit iterative scheme for finding a common element of the set of common fixed points of N$N$ nonexpansive mappings and the set of solutions of the variational inequality problem for a monotone, Lipschitz-continuous mapping. The implicit iterative scheme is based on two well-known methods: extragradient and approximate proximal. We obtain a weak convergence theorem for three sequences generated by this implicit iterative scheme. On the basis of this theorem, we also construct an implicit iterative process for finding a common fixed point of N+1$N+1$ mappings, such that one of these mappings is taken from the more general class of Lipschitz pseudocontractive mappings and the other N$N$ mappings are nonexpansive.     

A tearing-based hybrid parallel banded linear system solver

A new parallel algorithm for the solution of banded linear systems is proposed. The scheme tears the coefficient matrix into several overlapped independent blocks in which the size of the overlap is equal to the system’s bandwidth. A corresponding splitting of the right-hand side is also provided. The resulting independent, and smaller size, linear systems are solved under the constraint that the solutions corresponding to the overlap regions are identical. This results in a linear system whose size is proportional to the sum of the overlap regions which we refer to as the “balance” system. We propose a solution strategy that does not require obtaining this “balance” system explicitly. Once the balance system is solved, retrieving the rest of the solution can be realized with almost perfect parallelism. Our proposed algorithm is a hybrid scheme that combines direct and iterative methods for solving a single banded system of linear equations on parallel architectures. It has broad applications in finite-element analysis, particularly as a parallel solver of banded preconditioners that can be used in conjunction with outer Krylov iterative schemes.     

Parallel Interior-Point Method for Linear and Quadratic Programs with Special Structure

This paper concerns the use of iterative solvers in interior-point methods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linear programming and robust optimization, where the constraint matrix is block-angular and extremely large.     

Grid solution of problem with unilateral constraints

The present study deals with the solution of a problem, defined in a three-dimensional domain, arising in fluid mechanics. Such problem is modelled with unilateral constraints on the boundary. Then, the problem to solve consists in minimizing a functional in a closed convex set. The characterization of the solution leads to solve a time-dependent variational inequality. An implicit scheme is used for the discretization of the time-dependent part of the operator and so we have to solve a sequence of stationary elliptic problems. For the solution of each stationary problem, an equivalent form of a minimization problem is formulated as the solution of a multivalued equation, obtained by the perturbation of the previous stationary elliptic operator by a diagonal monotone maximal multivalued operator. The spatial discretization of such problem by appropriate scheme leads to the solution of large scale algebraic systems. According to the size of these systems, parallel iterative asynchronous and synchronous methods are carried out on distributed architectures; in the present study, methods without and with overlapping like Schwarz alternating methods are considered. The convergence of the parallel iterative algorithms is analysed by contraction approaches. Finally, the parallel experiments are presented.     

Strong Convergence Theorems for Variational Inequalities and Fixed Point Problems of Asymptotically Strict Pseudocontractive Mappings in the Intermediate Sense

The purpose of this paper is to investigate the problem of finding a common element of the set of fixed points of an asymptotically strict pseudocontractive mapping in the intermediate sense and the set of solutions of the variational inequality problem for a monotone, Lipschitz continuous mapping. We introduce a modified hybrid Mann iterative scheme with perturbed mapping which is based on well-known CQ method, Mann iteration method and hybrid (or outer approximation) method. We establish a strong convergence theorem for three sequences generated by this modified hybrid Mann iterative scheme with perturbed mapping. Utilizing this theorem, we also design an iterative process for finding a common fixed point of two mappings, one of which is an asymptotically strict pseudocontractive mapping in the intermediate sense and the other taken from the more general class of Lipschitz pseudocontractive mappings.     

On the Existence and Uniqueness of Solution of MRE and Applications

In this paper, we study the existence and uniqueness of the solution for Markov renewal equation (MRE) of a semi-Markov process with countable state space. This method and its proof are based on an iterative scheme. A numerical solution is also given as well as a case study on system reliability assessment.     

Parallel implementation of hybrid iterative methods for nonsymmetric linear systems

In this paper, we study efficient parallel implementation for hybrid iterative methods BiCGSTAB and BiCGSTAB (?) with ? = 2 on the CRAY C90, and the efficiency of their parallel performance is evaluated. Numerical experiments suggest that on the CRAY C90 a parallel inner product algorithm called PDOTB be used for the parallelization of hybrid iterative methods containing sensitive values of inner products. Lastly, it is shown that the number of iterations in which parallel hybrid iterative methods satisfy a certain convergence criterion depends on the number of processors to be used.     

Convergence analysis of a hybrid Mann iterative scheme with perturbed mapping for variational inequalities and fixed point problems

The purpose of this article is to investigate the problem of finding a common element of the set of fixed points of a non-expansive mapping and the set of solutions of the variational inequality problem for a monotone, Lipschitz continuous mapping. We introduce a hybrid Mann iterative scheme with perturbed mapping which is based on the well-known Mann iteration method and hybrid (or outer approximation) method. We establish a strong convergence theorem for three sequences generated by this hybrid Mann iterative scheme with perturbed mapping. Utilizing this theorem, we also construct an iterative process for finding a common fixed point of two mappings, one of which is non-expansive and the other taken from the more general class of Lipschitz pseudocontractive mappings.     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

Convergence of hybrid viscosity and steepest-descent methods for pseudocontractive mappings and nonlinear Hammerstein equations

In this article, we first introduce an iterative method based on the hybrid viscosity approximation method and the hybrid steepest-descent method for finding a fixed point of a Lipschitz pseudocontractive mapping (assuming existence) and prove that our proposed scheme has strong convergence under some mild conditions imposed on algorithm parameters in real Hilbert spaces. Next, we introduce a new iterative method for a solution of a nonlinear integral equation of Hammerstein type and obtain strong convergence in real Hilbert spaces. Our results presented in this article generalize and extend the corresponding results on Lipschitz pseudocontractive mapping and nonlinear integral equation of Hammerstein type reported by some authors recently. We compare our iterative scheme numerically with other iterative scheme for solving non-linear integral equation of Hammerstein type to verify the efficiency and implementation of our new method.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

High-order accurate iterative solution of the Navier–Stokes equations for incompressible flows

An iterative solution scheme for the incompressible Navier–Stokes equations is presented. It is split into inner and outer iteration cycles, such that the momentum and continuity equations are satisfied within prescribed accuracy. The spatial discretization is based on high-order finite differences which makes it well suited for massively parallel computers. This is demonstrated in a scaling test. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.