Higher-order quadratures for circulant preconditioned Wiener-Hopf equations

In this paper, we consider solving matrix systems arising from the discretization of Wiener-Hopf equations by preconditioned conjugate gradient (PCG) methods. Circulant integral operators as preconditioners have been proposed and studied. However, the discretization of these preconditioned equations by employing higher-order quadratures leads to matrix systems that cannot be solved efficiently by using fast Fourier transforms (FFTs). The aim of this paper is to propose new preconditioners for Wiener-Hopf equations. The discretization of these preconditioned operator equations by higher-order quadratures leads to matrix systems that involve only Toeplitz, circulant and diagonal matrix-vector multiplications and hence can be computed efficiently by FFTs in each iteration. We show that with the proper choice of kernel functions of Wiener-Hopf equations, the resulting preconditioned operators will have clustered spectra and therefore the PCG method converges very fast. Numerical examples are given to illustrate the fast convergence of the method and the improvement of the accuracy of the computed solutions with using higher-order quadratures.Research supported by the Cooperative Research Centre for Advanced Computational Systems.Research supported in part by Lee Ka Shing scholarship.     

Preconditioners for non‐Hermitian Toeplitz systems

In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(N^α) the corresponding PCG method requires at most 𝒪(N log² N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.     

A variant of block incomplete factorization preconditioners for a symmetricH-matrix

We propose a variant of parallel block incomplete factorization preconditioners for a symmetric block-tridiagonalH-matrix. Theoretical properties of these block preconditioners are compared with those of block incomplete factorization preconditioners for the corresponding comparison matrix. Numerical results of the preconditioned CG(PCG) method using these block preconditioners are compared with those of PCG using other types of block incomplete factorization preconditioners. Lastly, parallel computations of the block incomplete factorization preconditioners are carried out on the Cray C90.     

MATRIX ANALYSIS ON LEADING TERM OF CONDITION NUMBER FOR ADDITIVE SCHWARZ METHODS

1. IntroductionLet us consider the following second order elliptic boundary value problem:where C is a self-adjoint positive operator andis a polyhedral domain.Using weak solution it leads to a discrete equationwithwhere {of i} could be nodal basis consisting of piece--wise linear functions or other spline func-tions. It is well known that the coefficient matrix A is symmetry positive definite matrix withcondition numberFulthermore, under rectangle deform mesh it is easy to obtain the leading…     

A preconditioned domain decomposition algorithm for the solution of the elliptic Neumann problem

A new preconditioned conjugate gradient (PCG)-based domain decomposition method is given for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem. The novelty of the proposed method is in the recommended preconditioner which is constructed by using cyclic matrix. The resulting preconditioned algorithms are well suited to parallel computation.     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZ MATRICES FROM SINC METHODS

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.     

DIRECT ITERATIVE METHODS FOR RANK DEFICIENT GENERALIZED LEAST SQUARES PROBLEMS

1. IntroductionThe generalized LS problemis frequently found in solving problems from statistics, engineering, economics, imageand signal processing. Here A e Rmxn with m 2 n, b E Re and W E Rmxm issymmetric positive definite. The large sparse rank deficient generalized LS problemsappeal in computational genetics when we consider mited linear model for tree oranimal genetics [2], [31, [5].Recentlyg Yuan [9] and [10], Yuan and lusem [11] considered direct iterative methodsfor the problem …     

A note on an SOR-like method for augmented systems

Golub et al. (2001, BIT, 41, 71–85) gave a generalizedsuccessive over-relaxation method for the augmented systems.In this paper, the connection between the SOR-like method andthe preconditioned conjugate gradient (PCG) method for the augmentedsystems is investigated. It is shown that the PCG method isat least as accurate (fast) as the SOR-like method. Numericalexamples demonstrate that the PCG method is much faster thanthe SOR-like method.     

Schwarz preconditioned CG algorithm for the mortar finite element

We propose a simple and effective hybrid (multiplicative) Schwarz precondtioner for solving systems of algebraic equations resulting from the mortar finite element discretization of second order elliptic problems on nonmatching meshes. The preconditioner is embedded in a variant of the classical preconditioned conjugate gradient (PCG) for an effective implementation reducing the cost of computing the matrix-vector multiplication in each iteration of the PCG. In fact, it serves as a framework for effective implementation of a class of hybrid Schwarz preconditioners. The preconditioners of this class are based on solving a sequence of non-overlapping local subproblems exactly, and the coarse problems either exactly or inexactly (approximately). The classical PCG algorithm is reformulated in order to make reuse of the results of matrix-vector multiplications that are already available from the preconditioning step resulting in an algorithm which is cost effective. An analysis of the proposed preconditioner, with numerical results, showing scalability with respect to the number of subdomains, and a convergence which is independent of the jumps of the coefficients are given.     

A Legendre spectral quadrature Galerkin method for the Cauchy-Navier equations of elasticity with variable coefficients

We solve the Dirichlet and mixed Dirichlet-Neumann boundary value problems for the variable coefficient Cauchy-Navier equations of elasticity in a square using a Legendre spectral Galerkin method. The resulting linear system is solved by the preconditioned conjugate gradient (PCG) method with a preconditioner which is shown to be spectrally equivalent to the matrix of the resulting linear system. Numerical tests demonstrating the convergence properties of the scheme and PCG are presented.     

On the solution of indefinite systems arising in nonlinear programming problems

This work is concerned with the convergence properties and the numerical analysis of the preconditioned conjugate gradient (PCG) method applied to the solution of indefinite linear systems arising in nonlinear optimization. Our approach is based on the choice of quasidefinite preconditioners and of a suitable factorization routine. Some theoretical and numerical results about these preconditioners are obtained. Furthermore, we show the behaviour of the PCG method for different formulations of the indefinite system and we compare the effectiveness of the proposed variants. Copyright © 2007 John Wiley & Sons, Ltd.     

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.     

Band Toeplitz preconditioners for block Toeplitz systems

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.     

Sharp upper and lower bounds for the Laplacian spectral radius and the spectral radius of graphs

In this paper, sharp upper bounds for the Laplacian spectral radius and the spectral radius of graphs are given, respectively. We show that some known bounds can be obtained from our bounds. For a bipartite graph G, we also present sharp lower bounds for the Laplacian spectral radius and the spectral radius, respectively.     

Realistic Eigenvalue Bounds for the Galerkin Mass Matrix

In time-dependent finite-element calculations, a mass matrixnaturally arises. To avoid the solution of the correspondingalgebraic equation system at each time step, ‘mass lumping’is widely used, even though this pragmatic diagonalization ofthe mass matrix often reduces accuracy. We show how the unassembled form of finite-element equationscan be used to establish (in an element-by-element manner) realisticupper and lower bounds on the eigenvalues of the fully consistentmass matrix when preconditioned by its diagonal entries. Weuse this technique to give specific results for a number ofdifferent types of finite elements in one, two, and three dimensions.The bounds are found by independent calculations on the elements,and, for certain element types, are independent of mesh irregularity.We give examples of when some of the bounds are attained. These results indicate that the preconditioned conjugate-gradientmethod is appropriate and very rapid for the solution of Galerkinmass-matrix equations.     

Error Control in Polytope Computations

This paper presents solutions for numerical computation on convex hulls; computational algorithms that ensure logical consistency and accuracy are proposed. A complete numerical error analysis is presented. It is shown that a global error bound for vertex-facet adjacency does not exist under logically consistent procedures. To cope with practical requirements, vertex preconditioned polytope computations are introduced using point and hyperplane adjustments. A global bound on vertex-facet adjacency error is affected by the global bound on vertices; formulas are given for a conservative choice of global error bounds.     

HSAGA and its application for the construction of near-Moore digraphs

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions.This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems.     

Hartley preconditioners for Toeplitz systems generated by positive continuous functions

In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT _n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM _n is defined to be the minimizer of T _n –B _{n F} over allB _n H _n whereH _n is the Hartley algebra. We show that if the generating functionf ofT _n is a positive 2-periodic continuous even function, then the spectrum of the preconditioned systemM _n ^–1 T _n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.