A fast realization of preconditioned Conjugate Gradients for Wiener-Hopf integral equations

We present an efficient implementation of the Conjugate Gradients algorithm for Wiener-Hopf integral equations based on finite rank approximations of the integral operator and the corresponding preconditioner. The resulting algorithm is of linear complexity. Numerical experiments with this implementation of the preconditioned Conjugate Gradients algorithm show significant speed-up in the ill-conditioned case. This algorithm acts on ill-conditioned equations as a regularization algorithm.     

New convolutions and their applicability to integral equations of Wiener-Hopf plus Hankel type

We propose four new convolutions exhibiting convenient factorization properties associated with two finite interval integral transformations of Fourier-type together with their norm inequalities. Moreover, we study the solvability of a class of integral equations of Wiener-Hopf plus Hankel type (on finite intervals) with the help of the factorization identities of such convolutions. Fourier-type series are used to produce the solution formula of such equations, and a Shannon-type sampling formula is also obtained.     

Multilevel Additive Schwarz Method for the Version of the Galerkin Boundary Element Method

We study a multilevel additive Schwarz method for the - version of the Galerkin boundary element method with geometrically graded meshes. Both hypersingular and weakly singular integral equations of the first kind are considered. As it is well known the - version with geometric meshes converges exponentially fast in the energy norm. However, the condition number of the Galerkin matrix in this case blows up exponentially in the number of unknowns . We prove that the condition number of the multilevel additive Schwarz operator behaves like . As a direct consequence of this we also give the results for the -level preconditioner and also for the - version with quasi-uniform meshes. Numerical results supporting our theory are presented.

     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

Parallel Algorithms for Orthotropic Problems

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equations are solved by the conjugate gradient method preconditioned by modified incomplete factorization, MIC. The basic method presented, is based on fronts of uncoupled nodes and unlike earlier methods it has the advantage of no requirement of a specific orientation of the mesh. This method is however, in general, restricted to small degree of anisotropy in the differential equation. Another method, which does not suffer from this limitation, uses rotation of the differential equation and spectral equivalence. The rotation is made in such a way that in the new co-ordinate system, the basic method is applicable. The spectral equivalence property is used for estimation of the condition number of the preconditioned system. Both methods are suitable for implementation on parallel computers. The computer architecture could be single instruction multiple data (SIMD) as well as multiple instruction multiple data (MIMD) with shared or distributed memory. Implementation of the basic method on a shared memory parallel computer shows a significant improvement by use of the MIC method compared with the diagonal scaling preconditioning method.     

The construction of an algebraically reduced system for the acceleration of preconditioned conjugate gradients

In this paper we show how an algebraically reduced system can be constructed, for which the preconditioned conjugate gradient method converges faster than for the original system. For this method it is necessary that the original matrix is symmetric positive-definite. Our approach is based on an efficient projection on a well-chosen subspace and we show an application in which a cyclically reduced system is one step further reduced by this novel technique.     

Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

GENUINE-OPTIMAL CIRCULANT PRECONDITIONERS FOR WIENER-HOPF EQUATIONS

1. IntroductionWienerHopf equations are integral equations defined on the haif line:where rr > 0, a(.) C L1(ro and g(.) E L2(at). Here R = (--oo,oo) and ty [0,oo). Inou-r discussions, we assume that a(.) is colljugate symmetric, i.e. a(--t) = a(t). WienerHop f equations arise in a variety of practical aPplicatiolls in mathematics and ellgineering, forinstance, in the linear prediction problems fOr stationary stochastic processes [8, pp.145--146],diffuSion problems and scattering problems […     

Modified nodal cubic spline collocation for biharmonic equations

We formulate a modified nodal cubic spline collocation scheme for the solution of the biharmonic Dirichlet problem on the unit square. We prove existence and uniqueness of a solution of the scheme and show how the scheme can be solved on an N × N uniform partition of the square at a cost O(N ² log₂ N + mN ²) using fast Fourier transforms and m iterations of the preconditioned conjugate gradient method. We demonstrate numerically that m proportional to log₂ N guarantees the desired convergence rates. Numerical results indicate the fourth order accuracy of the approximations in the global maximum norm and the fourth order accuracy of the approximations to the first order partial derivatives at the partition nodes.      

Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems

This paper is concerned with the numerical solution of a symmetric indefinite system which is a generalization of the Karush–Kuhn–Tucker system. Following the recent approach of Luk?an and Vl?ek, we propose to solve this system by a preconditioned conjugate gradient (PCG) algorithm and we devise two indefinite preconditioners with good theoretical properties. In particular, for one of these preconditioners, the finite termination property of the PCG method is stated. The PCG method combined with a parallel version of these preconditioners is used as inner solver within an inexact Interior‐Point (IP) method for the solution of large and sparse quadratic programs. The numerical results obtained by a parallel code implementing the IP method on distributed memory multiprocessor systems enable us to confirm the effectiveness of the proposed approach for problems with special structure in the constraint matrix and in the objective function. Copyright © 2002 John Wiley & Sons, Ltd.     

Application of Wiener-Hopf technique to linear nonhomogeneous integral equations for a new representation of Chandrasekhar's H-function in radiative transfer, its existence and uniqueness

In this paper, the linear nonhomogeneous integral equation of H-functions is considered to find a new form of H-function as its solution. The Wiener-Hopf technique is used to express a known function into two functions with different zones of analyticity. The linear nonhomogeneous integral equation is thereafter expressed into two different sets of functions having the different zones of regularity. The modified form of Liouville's theorem is thereafter used, Cauchy's integral formulae are used to determine functional representation over the cut region in a complex plane. The new form of H-function is derived both for conservative and nonconservative cases. The existence of solution of linear nonhomogeneous integral equations and its uniqueness are shown. For numerical calculation of this new H-function, a set of useful formulae are derived both for conservative and nonconservative cases.     

Wavelet-based preconditioners for boundary integral equations

We study simple preconditioners for the conjugate gradient method when used to solve matrix systems arising from some hypersingular and weakly singular integral equations. The preconditioners, which are of the type of hierarchical basis preconditioners, are based on the decomposition of the piecewise-linear (respectively piecewise-constant) functions as the sum of prewavelets (respectively derivatives of prewavelets). We prove that with these preconditioners the preconditioned systems have condition numbers uniformly bounded with respect to the degrees of freedom. Numerical experiments support our analysis. This revised version was published online in June 2006 with corrections to the Cover Date.     

改进的预处理共轭斜量法及其在工程有限元分析中的应用

本文就预处理共轭斜量法(PCCG法)给出了两个具有理论和实际意义的定理,它们分别讨论了迭代解的定性性质和迭代矩阵的构造原则.作者提出了新的非M-矩阵的不完全LU分解技术和迭代矩阵的构造方法.用此改进的PCCG法,对病态问题和大型三维有限元问题进行了计算并与其他方法作了对比,分析了PCCG法在求解病态方程组时的反常现象.计算结果表明本文建议的方法是求解大型有限元方程组和病态方程组的一种十分有效的方法.     

四阶微分方程Hermite有限元的预处理共轭梯度法

对一类四阶微分方程两点边值问题的Hermite有限元方法进行了研究.首先讨论了该方程通常意义下的Galerkin有限元离散,考虑到有限元离散得到的线性方程组的对称正定性,文中采用了预处理最速下降法和共轭梯度方法求解线性方程组,通过选择不同的预处理器,使得求解该方程组的迭代次数有了很大的改观.     

On the stability of Volterra integral equations with a lagging argument

Stability properties of numerical methods for Volterra integral equations with lagging argument are considered. Some suitable definitions for the stability of the numerical methods are included, and plots of the stability regions for particular cases are included.     

DOMAIN DECOMPOSITION PRECONDITIONERS FOR SECOND-ORDER HYPERBOLIC EQUATIONS ON L-SHAPED REGIONS

Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations on L-shaped region are considered. We analyse the use of domain deocmposilion preconditioner.s for the solution of linear systems via the preconditioned conjugate gradient method. For the constant-coefficient second-order hyperbolic equaions with initial and Dirichlet boundary conditions,we prove that the conditionnumber of the preconditioned interface system is bounded by 2+x2 2+0.46x2 where x is the quo-tient between the lime and space steps. Such condition number produces a convergence rale that is independent of gridsize and aspect ratios. The results could be extended to parabolic equations.     

SINE TRANSFORM PRECONDITIONERS FOR SECOND-ORDER PARTIAL DIFFERENTIAL EQUATIONS

In this paper, we are concerned with the numerical solution of second-order partial differential equations. We analyse the use of the Sine Transform precondilioners for the solution of linear systems arising from the discretization of p.d.e. via the preconditioned conjugate gradient method. For the second-order partial differential equations with Dirichlel boundary conditions, we prove that the condition number of the preconditioned system is O(1) while the condition number of the original system is O(m 2) Here m is the number of interior gridpoints in each direction. Such condition number produces a linear convergence rale.     

A random integral quadrature method for numerical analysis of the second kind of Volterra integral equations

In this paper, a novel meshless technique termed the random integral quadrature (RIQ) method is developed for the numerical solution of the second kind of the Volterra integral equations. The RIQ method is based on the generalized integral quadrature (GIQ) technique, and associated with the Kriging interpolation function, such that it is regarded as an extension of the GIQ technique. In the GIQ method, the regular computational domain is required, in which the field nodes are scattered along straight lines. In the RIQ method however, the field nodes can be distributed either uniformly or randomly. This is achieved by discretizing the governing integral equation with the GIQ method over a set of virtual nodes that lies along straight lines, and then interpolating the function values at the virtual nodes over all the field nodes which are scattered either randomly or uniformly. In such a way, the governing integral equation is converted approximately into a system of linear algebraic equations, which can be easily solved.     

Reflexive periodic solutions of general periodic matrix equations

Analysis and design of linear periodic control systems are closely related to the periodic matrix equations. The objective of this paper is to provide four new iterative methods based on the conjugate gradient normal equation error (CGNE), conjugate gradient normal equation residual (CGNR), and least‐squares QR factorization (LSQR) algorithms to find the reflexive periodic solutions (X₁,Y₁,X₂,Y₂,…,X_σ,Y_σ) of the general periodic matrix equations for i = 1,2,…,σ. The iterative methods are guaranteed to converge in a finite number of steps in the absence of round‐off errors. Finally, some numerical results are performed to illustrate the efficiency and feasibility of new methods.     

谱HS投影算法求解非线性单调方程组

借助谱梯度法和HS共轭梯度法的结构, 建立一种求解非线性单调方程组问题的谱HS投影算法. 该算法继承了谱梯度法和共轭梯度法储存量小和计算简单的特征, 且不需要任何导数信息, 因此它适应于求解大规模非光滑的非线性单调方程组问题. 在适当的条件下, 证明了该算法的收敛性, 并通过数值实验表明了该算法的有效性.