共查询到20条相似文献,搜索用时 21 毫秒
1.
Lesley R. Matheson Robert E. Tarjan 《International journal of parallel programming》1996,24(5):397-432
Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad
range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid
methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a
series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms
with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism,
but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms
to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1)
domain-parallel versions of the standard V-cycle and F-cycle algorithms; (2) a multiple coarse grid algorithm, proposed by
Fredrickson and McBryan, which generates several coarse grids for each fine grid; and (3) two Rosendale algorithm, which allow
computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference
techniques on block-structured meshes in two or three dimensions with up to 106 or 109 points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models.
The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which
contain a large number of small (bitserial) processors, and SPMD medium-grain computers, which have a more modest number of
powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than
algorithms utilizing either parallel strategy. Both parallel strategies need too much extra work to compensate for their extra
parallelism. They require a highly impractical number of processors to be competitive with simpler, standard algorithms. The
analysis also suggests that the F-cycle, with the appropriate optimization techniques, is more efficient than the V-cycle
under a broad range of problem, implementation, and machine characteristics, despite the fact that it exhibits even less parallelism
than the V-cycle.
Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office
of Naval Research, Contract No. N0014-91-J-1463. 相似文献
2.
Wilhelm Heinrichs 《Computer Methods in Applied Mechanics and Engineering》1990,80(1-3):281-286
For the Helmholtz equation a spectral discretization with a symmetric and sparse matrix is presented. Certain algebraic spectral multigrid methods can be efficiently used for solving the linear systems. 相似文献
3.
Moshe Dubiner 《Journal of scientific computing》1987,2(1):3-31
A detailed asymptotic analysis of spectral methods for prototype problems is presented. Asymptotic error behavior throughout the solution regime is given. A number of surprising results are presented, including theO(N) boundedness of the eigenvalues of collocation on Legendre points. 相似文献
4.
Comparing spectral color computation methods 总被引:1,自引:0,他引:1
A comparison of several schemes for spectral sampling, computation and the resultant color display reveals the relevant considerations in selecting a color computation space 相似文献
5.
We propose a new stepsize for the gradient method. It is shown that this new stepsize will converge to the reciprocal of the largest eigenvalue of the Hessian, when Dai-Yang's asymptotic optimal gradient method (Computational Optimization and Applications, 2006, 33(1): 73–88) is applied for minimizing quadratic objective functions. Based on this spectral property, we develop a monotone gradient method that takes a certain number of steps using the asymptotically optimal stepsize by Dai and Yang, and then follows by some short steps associated with this new stepsize. By employing one step retard of the asymptotic optimal stepsize, a nonmonotone variant of this method is also proposed. Under mild conditions, R-linear convergence of the proposed methods is established for minimizing quadratic functions. In addition, by combining gradient projection techniques and adaptive nonmonotone line search, we further extend those methods for general bound constrained optimization. Two variants of gradient projection methods combining with the Barzilai-Borwein stepsizes are also proposed. Our numerical experiments on both quadratic and bound constrained optimization indicate that the new proposed strategies and methods are very effective. 相似文献
6.
Wilhelm Heinrichs 《Journal of scientific computing》1991,6(1):1-19
We introduce a stabilized treatment of spectral methods. The condition number of the spectral systems is highly improved. Elliptic and biharmonic problems are considered. Suitable interpolants in the case of inhomogeneous Dirichlet boundary conditions are presented. For a direct solver the improvements with respect to rounding error propagation are numerically demonstrated. 相似文献
7.
A parallel implementation of the preconditioned GMRES method is described. The method is used to solve the discretized incompressible Navier–Stokes equations. A parallel implementation of the inner product is given, which appears to be scalable on a massively parallel computer. The most difficult part to parallelize is the ILU-preconditioner. We parallelize the preconditioner using ideas proposed by Bastian and Horton (P. Bastian, G. Horton, SIAM. J. Stat. Comput. 12 (1991) 1457–1470). Contrary to some other parallel methods, the required number of iterations is independent of the number of processors used. A model is presented to predict the efficiency of the method. Experiments are done on the Cray T3D, computing the solution of a two-dimensional incompressible flow. Predictions of computing time show good correspondence with measurements. 相似文献
8.
We present a distributed algorithm for implementing α-β search on a tree of processors. Each processor is an independent computer with its own memory and is connected by communication lines to each of its nearest neighbors. Measurements of the algorithm's performance on the Arachne distributed operating system are presented. A theoretical model is developed that predicts at least order of speedup with k processors. 相似文献
9.
Raghu Ramakrishnan 《Annals of Mathematics and Artificial Intelligence》1991,3(2-4):295-329
There is a tension between the objectives of avoiding irrelevant computation and extracting parallelism, in that a computational step used to restrict another must precede the latter. Our thesis, following [3], is that evaluation methods can be viewed as implementing a choice ofsideways information propagation graphs, or sips, which determines the set of goals and facts that must be evaluated. Two evaluation methods that implement the same sips can then be compared to see which obtains a greater degree of parallelism, and we provide a formal measure of parallelism to make this comparison.Using this measure, we prove that transforming a program using the Magic Templates algorithm and then evaluating the fixpoint bottom-up provides a most parallel implementation for a given choice of sips, without taking resource constraints into account. This result, taken in conjunction with earlier results from [3,27], which show that bottom-up evaluation performs no irrelevant computation and is sound and complete, suggests that a bottom-up approach to parallel evaluation of logic programs is very promising. A more careful analysis of the relative overheads in the top-down and bottom-up evaluation paradigms is needed, however, and we discuss some of the issues.The abstract model allows us to establish several results comparing other proposed parallel evaluation methods in the logic programming and deductive database literature, thereby showing some natural, and sometimes surprising, connections. We consider the limitations of the abstract model and of the proposed bottom-up evaluation method, including the inability of sips to describe certain evaluation methods, and the effect of resource constraints. Our results shed light on the limits of the sip paradigm of computation, which we extend in the process. 相似文献
10.
The process of gene assembly in ciliates, an ancient group of organisms, is one of the most complex instances of DNA manipulation
known in any organisms. This process is fascinating from the computational point of view, with ciliates even using the linked
lists data structure. Three molecular operations (ld, hi, and dlad) have been postulated for the gene assembly process. We initiate here the study of parallelism in this process, raising several
natural questions, such as: when can a number of operations be applied in parallel to a gene pattern; or how many steps are
needed to assemble (in parallel) a micronuclear gene. In particular, this gives rise to a new measure of complexity for the
process of gene assembly in ciliates.
“One of the oldest forms of life on Earth has been revealed as a natural born computer programmer.” 相似文献
11.
D. J. Clements 《Systems & Control Letters》1993,20(5)
We describe a state-space-based algorithm to find the minimum phase spectral factor of any rational spectral density, whether it be proper, improper, or polynomial. 相似文献
12.
P. Zanolli 《Calcolo》1987,24(3-4):201-240
In this paper we review some multiple-domain decomposition algorithrns for spectral methods. The alternating Schwarz algorithm
and a flux preserving domain decomposition algorithm are considered. For both of them, some theoretical convergence results
are given. These domain decomposition algorithms allow the use of iterative procedures for block matrices that can be efficiently
implemented on parallel processors. Several numerical experiences based on the Chebyshev collocation method are carried out.
A comparison of the performances of the two algorithms on several test problems is presented. 相似文献
13.
A. Quarteroni 《Calcolo》1987,24(2):141-177
The main domain decomposition techniques currently in use in connection with approximation by spectral methods are reviewed.
Their most relevant features concerning both the theoretical and the computational aspects are analyzed. Some applications
to the Helmholtz problem, to the convection-diffusion equation and to the transport equation are shown. 相似文献
14.
15.
O. L. Bandman 《Programming and Computer Software》2001,27(4):170-182
In the paper, a systematic discussion is made of state of the art theory and applications of fine-grained (massive) parallelism, which is permanently being adopted in computational mathematics. All known models of fine-grained computations (cellular automaton, neural and cellular neural networks, statistical automata, etc.) are represented in terms of a unique formalism, the so-called parallel substitution algorithm (PSA), which made it possible, on the one hand, to highlight common properties of the models and, on the other hand, to demonstrate expressiveness capabilities of the PSA. Theoretical and experimental results of studies on applications of fine-grained algorithms to modeling of spatial dynamics of reaction–diffusion and molecular processes are presented. Promising prospects of their application are substantiated both for the creation of special processors designed for the implementation of the algorithms and for the implementation of the algorithms on multiprocessor systems. 相似文献
16.
17.
18.
Versatile spectral methods for point set matching 总被引:1,自引:0,他引:1
Alberto Silletti Alessandro Abate Jeffrey D. Axelrod 《Pattern recognition letters》2011,32(5):731-739
This work is concerned with the problem of point set matching over features extracted from images. A novel approach to the problem is proposed which leverages different techniques from the literature. It combines a number of similarity metrics that quantify measures of correspondence between the two sets of features and introduces a non-iterative algorithm for feature matching based on spectral methods. The flexibility of the technique allows its straightforward application in a number of diverse scenarios, thus overcoming domain-specific limitations of known techniques. The proposed approach is tested in a number of heterogeneous case studies: of synthetic nature; drawn from experimental biological data; and taken from known benchmarks in computer vision. 相似文献
19.
Recent years have witnessed great success of manifold learning methods in understanding the structure of multidimensional patterns. However, most of these methods operate in a batch mode and cannot be effectively applied when data are collected sequentially. In this paper, we propose a general incremental learning framework, capable of dealing with one or more new samples each time, for the so-called spectral embedding methods. In the proposed framework, the incremental dimensionality reduction problem reduces to an incremental eigen-problem of matrices. Furthermore, we present, using this framework as a tool, an incremental version of Hessian eigenmaps, the IHLLE method. Finally, we show several experimental results on both synthetic and real world datasets, demonstrating the efficiency and accuracy of the proposed algorithm. 相似文献
20.
S.H. Momeni-Masuleh 《Computers & Fluids》2004,33(8):1075-1095
The flow of a viscoelastic fluid through an undulating tube is considered. The fluid is modelled using the UCM constitutive equation. The governing set of equations is solved using a time-splitting technique. This is based on separate treatments of the convection and generalised Stokes operators. The spatial discretisation is based on a spectral discretisation in which the radial basis functions satisfy the conditions along the axis of symmetry of the tube explicitly. Compatible approximation spaces are chosen for velocity, pressure and extra-stress. The convection problem is solved in a type-sensitive manner using a high-order Runge-Kutta method. The weak formulation of the generalised Stokes problem is discretised and solved using a nested conjugate gradient technique. The effect of elasticity on flow resistance is investigated and comparisons made with other results in the literature. 相似文献