共查询到20条相似文献,搜索用时 375 毫秒
1.
Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated
by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without
requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are
uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore
the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14],
it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper
is to give a complete convergence proof of the method in [10,14] for this class of generating functions.
Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001 相似文献
2.
In earlier papers Tyrtyshnikov [42] and the first author [14] considered the analysis of clustering properties of the spectra
of specific Toeplitz preconditioned matrices obtained by means of the best known matrix algebras. Here we generalize this
technique to a generic Banach algebra of matrices by devising general preconditioners related to “convergent” approximation
processes [36]. Finally, as case study, we focus our attention on the Tau preconditioning by showing how and why the best
matrix algebra preconditioners for symmetric Toeplitz systems can be constructed in this class.
Received April 25, 1997 / Revised version received March 13, 1998 相似文献
3.
Xiao-Qing Jin 《Journal of Computational and Applied Mathematics》1996,70(2):225-230
We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained. 相似文献
4.
Zhi-Ru Ren 《计算数学(英文版)》2012,30(5):533-543
We give general expressions, analyze algebraic properties and derive eigenvalue bounds for a sequence of Toeplitz matrices associated with the sinc discretizations of various orders of differential operators. We demonstrate that these Toeplitz matrices can be satisfactorily preconditioned by certain banded Toeplitz matrices through showing that the spectra of the preconditioned matrices are uniformly bounded. In particular, we also derive eigenvalue bounds for the banded Toeplitz preconditioners. These results are elementary in constructing high-quality structured preconditioners for the systems of linear equations arising from the sinc discretizations of ordinary and partial differential equations, and are useful in analyzing algebraic properties and deriving eigenvalue bounds for the corresponding preconditioned matrices. Numerical examples are given to show effectiveness of the banded Toeplitz preconditioners. 相似文献
5.
J. Karátson 《Numerical Functional Analysis & Optimization》2013,34(5-6):590-611
The superlinear convergence of the preconditioned CGM is studied for nonsymmetric elliptic problems (convection-diffusion equations) with mixed boundary conditions. A mesh independent rate of superlinear convergence is given when symmetric part preconditioning is applied to the FEM discretizations of the BVP. This is the extension of a similar result of the author for Dirichlet problems. The discussion relies on suitably developed Hilbert space theory for linear operators. 相似文献
6.
R. E. Ewing R. D. Lazarov P. S. Vassilevski 《Numerical Linear Algebra with Applications》1994,1(4):337-368
Two preconditioning techniques for solving difference equations arising in finite difference approximation of elliptic problems on cell-centered grids are studied. It is proven that the BEPS and the FAC preconditioners are spectrally equivalent to the corresponding finite difference schemes, including a nonsymmetric one, which is of higher-order accuracy. Numerical experiments that demonstrate the fast convergence of the preconditioned iterative methods (CG and GCG-LS in the nonsymmetric case) are presented. 相似文献
7.
M.R. Mokhtarzadeh A. Golbabaee R. Mokhtary N.G. Chegini 《Applied mathematics and computation》2005,170(2):741
There are two approaches for applying substructuring preconditioner for the linear system corresponding to the discrete Steklov–Poincaré operator arising in the three fields domain decomposition method for elliptic problems. One of them is to apply the preconditioner in a common way, i.e. using an iterative method such as preconditioned conjugate gradient method [S. Bertoluzza, Substructuring preconditioners for the three fields domain decomposition method, I.A.N.-C.N.R, 2000] and the other one is to apply iterative methods like for instance bi-conjugate gradient method, conjugate gradient square and etc. which are efficient for nonsymmetric systems (the preconditioned system will be nonsymmetric). In this paper, second approach will be followed and extensive numerical tests will be presented which imply that the considered iterative methods are efficient. 相似文献
8.
Preconditioned Krylov subspace (KSP) methods are widely used for solving large‐scale sparse linear systems arising from numerical solutions of partial differential equations (PDEs). These linear systems are often nonsymmetric due to the nature of the PDEs, boundary or jump conditions, or discretization methods. While implementations of preconditioned KSP methods are usually readily available, it is unclear to users which methods are the best for different classes of problems. In this work, we present a comparison of some KSP methods, including GMRES, TFQMR, BiCGSTAB, and QMRCGSTAB, coupled with three classes of preconditioners, namely, Gauss–Seidel, incomplete LU factorization (including ILUT, ILUTP, and multilevel ILU), and algebraic multigrid (including BoomerAMG and ML). Theoretically, we compare the mathematical formulations and operation counts of these methods. Empirically, we compare the convergence and serial performance for a range of benchmark problems from numerical PDEs in two and three dimensions with up to millions of unknowns and also assess the asymptotic complexity of the methods as the number of unknowns increases. Our results show that GMRES tends to deliver better performance when coupled with an effective multigrid preconditioner, but it is less competitive with an ineffective preconditioner due to restarts. BoomerAMG with a proper choice of coarsening and interpolation techniques typically converges faster than ML, but both may fail for ill‐conditioned or saddle‐point problems, whereas multilevel ILU tends to succeed. We also show that right preconditioning is more desirable. This study helps establish some practical guidelines for choosing preconditioned KSP methods and motivates the development of more effective preconditioners. 相似文献
9.
Zhong-Zhi Bai 《中国科学 数学(英文版)》2013,56(12):2523-2538
Based on the PMHSS preconditioning matrix, we construct a class of rotated block triangular preconditioners for block two-by-two matrices of real square blocks, and analyze the eigen-properties of the corresponding preconditioned matrices. Numerical experiments show that these rotated block triangular preconditioners can be competitive to and even more efficient than the PMHSS pre-conditioner when they are used to accelerate Krylov subspace iteration methods for solving block two-by-two linear systems with coefficient matrices possibly of nonsymmetric sub-blocks. 相似文献
10.
Hong-Kui Pang Ying-Ying Zhang Xiao-Qing Jin 《Linear algebra and its applications》2011,434(11):2325-2342
We use the normalized preconditioned conjugate gradient method with Strang’s circulant preconditioner to solve a nonsymmetric Toeplitz system Anx=b, which arises from the discretization of a partial integro-differential equation in option pricing. By using the definition of family of generating functions introduced in [16], we prove that Strang’s circulant preconditioner leads to a superlinear convergence rate under certain conditions. Numerical results exemplify our theoretical analysis. 相似文献
11.
Iterative methods to solve systems of linear equations Ax = b usually require preconditioners M to speed convergence. But the calculation of many preconditioners can be notoriously sequential. The sparse approximate inverse preconditioner (SPAI) has particular potential for high performance computing [1]. We have ported the SPAI algorithm to graphical processing units (GPUs) within NVIDIA's CUSP library [2] for sparse linear algebra. GPUs perform well on dense linear algebra problems where data resides for long periods on the device. Since the underlying minimization problems are independent, they are mapped to separate thread-blocks, and an optimized QR algorithm implemented using NVIDIA's CUBLAS library is employed on each. Traditionally the challenge has been to determine a sparsity pattern Sp( M ) of the preconditioner dynamically [3], which reduces the condition number of MA to a degree where a preconditioned iterative solver such as GMRES becomes computationally viable. Due to the extremely high performance of the GPU, it is possible to consider initial sparsity patterns much denser than have been previously considered. We therefore consider a fixed sparsity patterns to simplify the GPU implementation. We evaluate the performance of the resulting preconditioner on a standard set of sparse matrices, and compare SPAI to other preconditioners. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
12.
Gerhard Starke 《Numerische Mathematik》1997,78(1):103-117
Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES
or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of
values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from
the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular,
the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations
of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners
which constitute popular preconditioning strategies for such problems.
Received May 3, 1996 相似文献
13.
Xiao-Chuan Cai William D. Gropp David E. Keyes 《Numerical Linear Algebra with Applications》1994,1(5):477-504
In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer. 相似文献
14.
In this paper, we consider preconditioners for generalized saddle point systems with a nonsymmetric coefficient matrix. A constraint preconditioner for this systems is constructed, and some spectral properties of the preconditioned matrix are given. Our results extend the corresponding ones in [3] and [4]. 相似文献
15.
In [A new nonlinear Uzawa algorithm for generalized saddle point problems, Appl. Math. Comput., 175(2006), 1432–1454], a nonlinear Uzawa algorithm for solving symmetric saddle point problems iteratively, which was defined by two nonlinear approximate inverses, was considered. In this paper, we extend it to the nonsymmetric case. For the nonsymmetric case, its convergence result is deduced. Moreover, we compare the convergence rates of three nonlinear Uzawa methods and show that our method is more efficient than other nonlinear Uzawa methods in some cases. The results of numerical experiments are presented when we apply them to Navier-Stokes equations discretized by mixed finite elements. 相似文献
16.
Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations 下载免费PDF全文
The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients. 相似文献
17.
本文研究Toeplitz+Hankel线性方程组的预处理迭代解法.我们提出了几个新的预条件子,并分析了预处理矩阵的谱性质,当生成函数在Wiener类中时,预处理矩阵的特征值聚集在1附近.数值实验表明该预处理子比文[5]中的预处理子更有效. 相似文献
18.
Xian-Ming Gu Yong-Liang Zhao Xi-Le Zhao Bruno Carpentieri & Yu-Yun Huang 《高等学校计算数学学报(英文版)》2021,14(4):893-919
The $p$-step backward difference formula (BDF) for solving systems of
ODEs can be formulated as all-at-once linear systems that are solved by parallel-in-time preconditioned Krylov subspace solvers (see McDonald et al. [36] and Lin
and Ng [32]). However, when the BDF$p$ (2 ≤ $p$ ≤ 6) method is used to solve time-dependent PDEs, the generalization of these studies is not straightforward as $p$-step
BDF is not selfstarting for $p$ ≥ 2. In this note, we focus on the 2-step BDF which is
often superior to the trapezoidal rule for solving the Riesz fractional diffusion equations, and show that it results into an all-at-once discretized system that is a low-rank
perturbation of a block triangular Toeplitz system. We first give an estimation of the
condition number of the all-at-once systems and then, capitalizing on previous work,
we propose two block circulant (BC) preconditioners. Both the invertibility of these
two BC preconditioners and the eigenvalue distributions of preconditioned matrices
are discussed in details. An efficient implementation of these BC preconditioners is
also presented, including the fast computation of dense structured Jacobi matrices.
Finally, numerical experiments involving both the one- and two-dimensional Riesz
fractional diffusion equations are reported to support our theoretical findings. 相似文献
19.
C. Estatico 《Numerical Linear Algebra with Applications》2009,16(3):237-257
Both theoretical analysis and numerical experiments in the literature have shown that the Tyrtyshnikov circulant superoptimal preconditioner for Toeplitz systems can speed up the convergence of iterative methods without amplifying the noise of the data. Here we study a family of Tyrtyshnikov‐based preconditioners for discrete ill‐posed Toeplitz systems with differentiable generating functions. In particular, we show that the distribution of the eigenvalues of these preconditioners has good regularization features, since the smallest eigenvalues stay well separated from zero. Some numerical results confirm the regularization effectiveness of this family of preconditioners. Copyright © 2009 John Wiley & Sons, Ltd. 相似文献
20.
Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations. 相似文献