首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 140 毫秒
1.
Applying a finite difference approximation to a biharmonic equation results in a very ill conditioned system of equations. This paper examines the conjugate gradient method used with polynomial preconditioning techniques for solving such linear systems. A new approach using an approximate polynomial preconditioner is described. The preconditioner is constructed from a series approximation based on the Laplacian finite difference matrix. A particularly attractive feature of this approach is that the Laplacian matrix consists of far fewer non-zero entries than the biharmonic finite difference matrix. Moreover, analytical estimates and computational results show that this preconditioner is more effective (in terms of the rate of convergence and the computational work required per iteration) than the polynomial preconditioner based on the original biharmonic matrix operator. The conjugate gradient algorithm and the preconditioning step can be efficiently implemented on a vector super-computer such as the CDC CYBER 205.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada Grant U0375; and in part by NASA (funded under the Space Act Agreement C99066G) while the author was visiting ICOMP, NASA Lewis Research Center.The work of this author was supported by an Izaak Walton Killam Memorial Scholarship.  相似文献   

2.
For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.  相似文献   

3.
Block preconditioner with circulant blocks (BPCB) has been used for solving linear systems with block Toeplitz structure since 1992 [R. Chan, X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. (13) (1992) 1218–1235]. In this new paper, we use BPCBs to general linear systems (with no block structure usually). The BPCBs are constructed by partitioning a general matrix into a block matrix with blocks of the same size and then applying T. Chan’s optimal circulant preconditioner [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. (9) (1988) 766–771] to each block. These BPCBs can be viewed as a generalization of T. Chan’s preconditioner. It is well-known that the optimal circulant preconditioner works well for solving some structured systems such as Toeplitz systems by using the preconditioned conjugate gradient (PCG) method, but it is usually not efficient for solving general linear systems. Unlike T. Chan’s preconditioner, BPCBs used here are efficient for solving some general linear systems by the PCG method. Several basic properties of BPCBs are studied. The relations of the block partition with the cost per iteration and the convergence rate of the PCG method are discussed. Numerical tests are given to compare the cost of the PCG method with different BPCBs.  相似文献   

4.
Techniques based on the idea of preconditioning and on the element-by-element concept have significantly improved the efficiency of classical iterative methods in conventional as well as in parallel hardware environment. In this work two preconditioning approaches based on the incomplete Choleski factorization have been further refined, with the result that both storage requirements and solution times have been greatly improved when processing large structural problems. The partial preconditioning method is also employed to develop a framework for constructing a global preconditioner, without the need to store the complete coefficient matrix, for accelerating an iterative element-by-element solution procedure.  相似文献   

5.
Modern direct solvers have been more and more widely used by computer graphics community for solving sparse linear systems, such as those that arise in cloth simulation. However, external constraints usually prevent a direct method from being used for cloth simulation due to the singularity of the constrained system. This paper makes two major contributions towards the re-introduction of direct methods for cloth dynamics solvers. The first one is an approach which eliminates all the constrained variables from the system so that we obtain a reduced, nonsingular and unconstrained system. As alternatives to the well-known MPCG algorithm, not only the original, unmodified PCG method, but also any direct method can be used to solve the reduced system at a lower cost. Our second contribution is a novel direct-iterative scheme applied for the reduced system, which is basically the conjugate gradient method using a special preconditioner. Specifically, we use the stiff part of the coefficient matrix, which we call the matrix core, as the preconditioner for the PCG. The inverse of this preconditioner is computed by any eligible direct solver. The direct-iterative method has proved to be more efficient than both direct and iterative methods. Our experiments show a factor of two speedup over direct methods when stiff springs are used, even greater improvements over the MPCG iterative method.  相似文献   

6.
The numerical solution of a large-scale variational inequality problem can be obtained using the generalization of an inexact Newton method applied to a semismooth nonlinear system. This approach requires a sparse and large linear system to be solved at each step. In this work we obtain an approximate solution of this system by the LSQR algorithm of Paige and Saunders combined with a convenient preconditioner that is a variant of the incomplete LU–factorization. Since the computation of the factorization of the preconditioning matrix can be very expensive and memory consuming, we propose a preconditioner that admits block-factorization. Thus the direct factorization is only applied to submatrices of smaller sizes. Numerical experiments on a set of test-problems arising from the literature show the effectiveness of this approach.  相似文献   

7.
An implicit time-linearized finite difference discretization of partial differential equations on regular/structured meshes results in an n-diagonal block system of algebraic equations, which is usually solved by means of the Preconditioned Conjugate Gradient (PCG) method. In this paper, an analysis of the parallel implementation of this method on several computer architectures and for several programming paradigms is presented. For three-dimensional regular/structured meshes, a new implementation of the PCG method with Jacobi preconditioner is proposed. For the computer architectures and number of processors employed in this study, it has been found that this implementation is more efficient than the standard one, and can be applied to narrow-band matrices and other preconditioners, such as, for example, polynomial ones.  相似文献   

8.
Iterative solvers and preconditioners are widely used for handling the linear system of equations arising from stochastic finite element method (SFEM) formulations, e.g. galerkin-based polynomial chaos (G-P-C) Expansion method. Especially, Preconditioned Conjugate Gradient (PCG) solver and the Incomplete Cholesky (IC) preconditioner are shown to be adequate choices within this context. In this study, approaches for the automated adjustment of the input parameters for these tools are to be introduced. The proposed algorithms aim to enable the use of the PCG solver and IC preconditioner in a black-box fashion. As a result, the requirement of the expertise for using these tools is removed to a certain extend. Furthermore, these algorithms can be used also for the implementation purposes of SFEM’s within general purpose software by increasing the ease of the use of these tools and hence leading to an improved user-comfort.  相似文献   

9.
For the generalized saddle-point problems, based on a new block-triangular splitting of the saddle-point matrix, we introduce a relaxed block-triangular splitting preconditioner to accelerate the convergence rate of the Krylov subspace methods. This new preconditioner is easily implemented since it has simple block structure. The spectral property of the preconditioned matrix is analysed. Moreover, the degree of the minimal polynomial of the preconditioned matrix is also discussed. Numerical experiments are reported to show the preconditioning effect of the new preconditioner.  相似文献   

10.
We present a polynomial preconditioner that can be used with the conjugate gradient method to solve symmetric and positive definite systems of linear equations. Each step of the preconditioning is achieved by simultaneously taking an iteration of the SOR method and an iteration of the reverse SOR method (equations taken in reverse order) and averaging the results. This yields a symmetric preconditioner that can be implemented on parallel computers by performing the forward and reverse SOR iterations simultaneously. We give necessary and sufficient conditions for additive preconditioners to be positive definite.

We find an optimal parameter, ω, for the SOR-Additive linear stationary iterative method applied to 2-cyclic matrices. We show this method is asymptotically twice as fast as SSOR when the optimal ω is used.

We compare our preconditioner to the SSOR polynomial preconditioner for a model problem. With the optimal ω, our preconditioner was found to be as effective as the SSOR polynomial preconditioner in reducing the number of conjugate gradient iterations. Parallel implementations of both methods are discussed for vector and multiple processors. Results show that if the same number of processors are used for both preconditioners, the SSOR preconditioner is more effective. If twice as many processors are used for the SOR-Additive preconditioner, it becomes more efficient than the SSOR preconditioner when the number of equations assigned to a processor is small. These results are confirmed by the Blue Chip emulator at the University of Washington.  相似文献   


设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号