The finite element solutions of elliptic eigenvalue equations are shown to have a multi-parameter asymptotic error expansion. Based on this expansion and a splitting extrapolation technique, a parallel algorithm for s...
详细信息
The finite element solutions of elliptic eigenvalue equations are shown to have a multi-parameter asymptotic error expansion. Based on this expansion and a splitting extrapolation technique, a parallel algorithm for solving multi-dimensional equations with high order accuracy is developed.
This work is concerned with the convergence/stability analysis of a parallel algorithm which is used to solve the incompressible Navier-Stokes problem. This relies on a splitting of the main differential operator, tha...
详细信息
This work is concerned with the convergence/stability analysis of a parallel algorithm which is used to solve the incompressible Navier-Stokes problem. This relies on a splitting of the main differential operator, thanks to which the most important difficulties (nonlinearity and incompressibility) can be considered independently. Thus, one is led to the formulation of subproblems of two kinds which can be solved simultaneously by two different processors. We prove conditional stability and convergence;this can serve to justify the accuracy of previous numerical results.
The P-4-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P-4 (cographs, P-4-sparse graphs, P-4-lite graphs). Here, we propose an extension of R. Lin and S. Ola...
详细信息
The P-4-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P-4 (cographs, P-4-sparse graphs, P-4-lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. parallel Distributed Computing 22, 26-36.) on cographs, using the modular decomposition. As an application, we show how to obtain a maximum matching parallel algorithm for the family of P-4-tidy graphs (represented by a parse tree) in O(log n) time with O(n/log n) processors in the EREW-PRAM model with n-vertex graphs. (C) 1998 Academic Press, Inc.
Recently Aklet al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for imple...
详细信息
Recently Aklet al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix and other problems. In this paper, we describe constant time solution to the longest common subsequence (LCS) and longest increasing subsequence (LIS) problems using the BSR model. The number of processors used to solve the LCS problem isO(N×M) (whereNandMare the length of the two input sequences). Our BSR solution of the LIS problem needsO(N) processors (whereNis the length of the input sequence). These two solutions use BSR instructions with a constant number of selections. It is an improvement of our former BSR algorithm for the LCS in (Journal of parallel and Distributed Computing, to appear) which uses 3N+ 3 selections.
Clustering is a part of data analysis that is required in many fields. In most applications such as unsupervised pattern recognition and image segmentation, the number of patterns may be very large. Therefore, designi...
详细信息
Clustering is a part of data analysis that is required in many fields. In most applications such as unsupervised pattern recognition and image segmentation, the number of patterns may be very large. Therefore, designing fast and processor efficient parallel algorithms for clustering is definitely of fundamental importance. In this paper, for N patterns and K centers each with M features, we propose several efficient and scalable parallel algorithms for squared error clustering on the arrays with reconfigurable optical buses with various number of processors. Based on the advantages of both optical transmission and electronic computation, the proposed algorithms can be run in O((K/p) log N), O(log N), O((KNM/pqr) + log r + log q), O(K/p), O(1), O(K) and O(KM) time using p x M x N/log N, K x M x N/log N, p x q x r, p x M x N1 + 1/epsilon, K x M x N1 + 1/epsilon, M x N1 + 1/epsilon and N1 + 1/epsilon processors, for some constant epsilon and epsilon greater than or equal to 1, respectively. These results are more efficient and scalable than the previously known algorithms. (C) 2000 Elsevier Science B.V. All rights reserved.
We present a novel method of parallelization of the multiplication operation in GF(2(k)) for an arbitrary value of k and arbitrary irreducible polynomial n(x) generating the field. The parallel algorithm is based on p...
详细信息
We present a novel method of parallelization of the multiplication operation in GF(2(k)) for an arbitrary value of k and arbitrary irreducible polynomial n(x) generating the field. The parallel algorithm is based on polynomial residue arithmetic, and requires that we find L pairwise relatively prime moduli m(i)(x) such that the degree of the product polynomial M(x)=m(1)(x)m(2)(x)\cdots m(L)(x) is at least 2k. The parallel algorithm receives the residue representations of the input operands (elements of the field) and produces the result in its residue form, however, it is guaranteed that the degree of this polynomial is less than k and it is properly reduced by the generating polynomial n(x), i.e., it is an element of the field. In order to perform the reductions, we also describe a new table lookup based polynomial reduction method.
Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control...
详细信息
Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control and Optimization, vol. 33, no. 6, pp. 1916-1925.), are presented for solving convex or nonconvex unconstrained minimization problems. The PSDM algorithms decompose the variable space into subspaces and distribute these decomposed subproblems among parallel processors. It is shown that if all decomposed subproblems are uncoupled of each other, they can be solved independently. Otherwise, the parallel algorithms presented in this paper can be used. Numerical experiments show that these parallel algorithms can save processor time, particularly for medium and large-scale problems. Up to six parallel processors are connected by Ethernet networks to solve four large-scale minimization problems. The results are compared with those obtained by using sequential algorithms run on a single processor. An application of the PSDM algorithms to the training of multilayer Adaptive Linear Neurons (Madaline) and a new parallel architecture for such parallel training are also presented.
We introduce a new two-phase technique to solve highly asymmetric assignment problems. In the first phase, the assignment problem is decomposed into subproblems which are solved in parallel. The first phase is used to...
详细信息
We introduce a new two-phase technique to solve highly asymmetric assignment problems. In the first phase, the assignment problem is decomposed into subproblems which are solved in parallel. The first phase is used to exclude certain suboptimal assignments from consideration in the second phase. In the second phase, the optimal assignment is finalized. We show that the two-phase algorithm can reduce the theoretical time bound for solving an n x k assignment problem (n < k) by a factor of root k/n.
A number of new local acid parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation...
详细信息
A number of new local acid parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.
A preconditioned scheme for solving sparse symmetric eigenproblems is proposed. The solution strategy relies upon the DACG algorithm, which is a Preconditioned Conjugate Gradient algorithm for minimizing the Rayleigh ...
详细信息
A preconditioned scheme for solving sparse symmetric eigenproblems is proposed. The solution strategy relies upon the DACG algorithm, which is a Preconditioned Conjugate Gradient algorithm for minimizing the Rayleigh Quotient. A comparison with the well established ARPACK code shows that when a small number of the leftmost eigenpairs is to be computed, DACG is more efficient than ARPACK. Effective convergence acceleration of DACG is shown to be performed by a suitable approximate inverse preconditioner (AINV). The performance of such a preconditioner is shown to be safe, i.e. not highly dependent on a drop tolerance parameter. On sequential machines, AINV preconditioning proves a practicable alternative to the effective incomplete Cholesky factorization, and is mon efficient than Block Jacobi. Owing to its parallelizability, the AINV preconditioner is exploited for a parallel implementation of the DACG algorithm, Numerical tests account for the high degree of parallelization attainable on a Gray T3E machine and confirm the satisfactory scalability properties of the algorithm. A final comparison with PARPACK shows the (relative) higher efficiency of AINV-DACG. Copyright (C) 2000 John Wiley & Sons, Ltd.
暂无评论