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.     

The generalized superoptimal preconditioner

For any given n-by-n matrix A, a specific circulant preconditioner t_F(A) introduced by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459-473] is defined to be the solution of

     

A preconditioning approach to the pagerank computation problem

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ER_U method, and we observe that ER_U can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ER_U superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

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.     

On Schröder’s families of root-finding methods

Schröder’s methods of the first and second kind for solving a nonlinear equation f(x)=0, originally derived in 1870, are of great importance in the theory and practice of iteration processes. They were rediscovered several times and expressed in different forms during the last 130 years. It was proved in the paper of Petkovi? and Herceg (1999) [7] that even seven families of iteration methods for solving nonlinear equations are mutually equivalent. In this paper we show that these families are also equivalent to another four families of iteration methods and find that all of them have the origin in Schröder’s generalized method (of the second kind) presented in 1870. In the continuation we consider Smale’s open problem from 1994 about possible link between Schröder’s methods of the first and second kind and state the link in a simple way.     

Dynamics of a new family of iterative processes for quadratic polynomials

In this work we show the presence of the well-known Catalan numbers in the study of the convergence and the dynamical behavior of a family of iterative methods for solving nonlinear equations. In fact, we introduce a family of methods, depending on a parameter m∈N∪{0}. These methods reach the order of convergence m+2 when they are applied to quadratic polynomials with different roots. Newton’s and Chebyshev’s methods appear as particular choices of the family appear for m=0 and m=1, respectively. We make both analytical and graphical studies of these methods, which give rise to rational functions defined in the extended complex plane. Firstly, we prove that the coefficients of the aforementioned family of iterative processes can be written in terms of the Catalan numbers. Secondly, we make an incursion into its dynamical behavior. In fact, we show that the rational maps related to these methods can be written in terms of the entries of the Catalan triangle. Next we analyze its general convergence, by including some computer plots showing the intricate structure of the Universal Julia sets associated with the methods.     

Convergence analysis of non-conforming Trigonometric Finite Wave Elements

Trigonometric Finite Wave Elements (TFWE) are finite elements for solving problems in computational optics. The solution of those problems consist of highly oscillatory waves. TFWE are designed for obtaining optimal approximation properties for such kinds of waves with a changing wave number k. In this article, we study the convergence properties of 2-dimensional non-conforming TFWE by applying Strang’s Lemma.     

Left-definite theory with applications to orthogonal polynomials

In the past several years, there has been considerable progress made on a general left-definite theory associated with a self-adjoint operator A that is bounded below in a Hilbert space H; the term ‘left-definite’ has its origins in differential equations but Littlejohn and Wellman [L. L. Littlejohn, R. Wellman, A general left-definite theory for certain self-adjoint operators with applications to differential equations, J. Differential Equations, 181 (2) (2002) 280-339] generalized the main ideas to a general abstract setting. In particular, it is known that such an operator A generates a continuum {H_r}_r>0 of Hilbert spaces and a continuum of {A_r}_r>0 of self-adjoint operators. In this paper, we review the main theoretical results in [L. L. Littlejohn, R. Wellman, A general left-definite theory for certain self-adjoint operators with applications to differential equations, J. Differential Equations, 181 (2) (2002) 280-339]; moreover, we apply these results to several specific examples, including the classical orthogonal polynomials of Laguerre, Hermite, and Jacobi.     

Efficient numerical solution of the generalized Dirichlet-Neumann map for linear elliptic PDEs in regular polygon domains

A new and novel approach for analyzing boundary value problems for linear and for integrable nonlinear PDEs was recently introduced. For linear elliptic PDEs, an important aspect of this approach is the characterization of a generalized Dirichlet-Neumann map: given the derivative of the solution along a direction of an arbitrary angle to the boundary, the derivative of the solution perpendicularly to this direction is computed without solving on the interior of the domain. For this computation, a collocation-type numerical method has been recently developed. Here, we study the collocation’s coefficient matrix properties. We prove that, for the Laplace’s equation on regular polygon domains with the same type of boundary conditions on each side, the collocation matrix is block circulant, independently of the choice of basis functions. This leads to the deployment of the FFT for the solution of the associated collocation linear system, yielding significant computational savings. Numerical experiments are included to demonstrate the efficiency of the whole computation.     

A note on skewcirculant preconditioners for elliptic problems

In a recent paper Chan and Chan study the use of circulant preconditioners for the solution of elliptic problems. They prove that circulant preconditioners can be chosen so that the condition number of the preconditioned system can be reduced fromO(n ² ) toO(n). In addition, using the Fast Fourier Transform, the computation of the preconditioner is highly parallelizable. To obtain their result, Chan and Chan introduce a shift /p/n ² for some >0. The aim of this paper is to consider skewcirculant preconditioners, and to show that in this case the condition number ofO(n) can easily be shown without using the somewhat unsatisfactory shift /p/n ². Furthermore, our estimates are more precise.     

Partial regularity for degenerate subelliptic systems associated with Hörmander’s vector fields

The paper is devoted to partial Hölder estimates for weak solutions of a class of degenerate subelliptic systems constructed by Hörmander’s vector fields. Assumptions on the systems are that coefficient matrix satisfies VMO condition in the sense of Carnot-Carathéodory distance in variables x for fixed u, and lower order terms satisfy the natural growth condition and the controllable growth condition, respectively.     

A sparse counterpart of Reichel and Gragg’s package QRUP

We describe how to maintain the triangular factor of a sparse QR factorization when columns are added and deleted and Q cannot be stored for sparsity reasons. The updating procedures could be thought of as a sparse counterpart of Reichel and Gragg’s package QRUP. They allow us to solve a sequence of sparse linear least squares subproblems in which each matrix B_k is an independent subset of the columns of a fixed matrix A, and B_k+1 is obtained by adding or deleting one column. Like Coleman and Hulbert [T. Coleman, L. Hulbert, A direct active set algorithm for large sparse quadratic programs with simple bounds, Math. Program. 45 (1989) 373-406], we adapt the sparse direct methodology of Björck and Oreborn of the late 1980s, but without forming A^TA, which may be only positive semidefinite. Our Matlab 5 implementation works with a suitable row and column numbering within a static triangular sparsity pattern that is computed in advance by symbolic factorization of A^TA and preserved with placeholders.     

Stable solutions of linear systems involving long chain of matrix multiplications

This paper is concerned with solving linear system (I_n+B_L?B₂B₁)x=b arising from the Green’s function calculation in the quantum Monte Carlo simulation of interacting electrons. The order of the system and integer L are adjustable. Also adjustable is the conditioning of the coefficient matrix to give rise an extreme ill-conditioned system. Two numerical methods based on the QR decomposition with column pivoting and the singular value decomposition, respectively, are studied in this paper. It is proved that the computed solution by each of the methods is weakly backward stable in the sense that the computed is close to the exact solution of a nearby linear system

     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

On the time discretization for the globally modified three dimensional Navier-Stokes equations

In this work, we analyze the discrete in time 3D system for the globally modified Navier-Stokes equations introduced by Caraballo (2006) [1]. More precisely, we consider the backward implicit Euler scheme, and prove the existence of a sequence of solutions of the resulting equations by implementing the Galerkin method combined with Brouwer’s fixed point approach. Moreover, with the aid of discrete Gronwall’s lemmas we prove that for the time step small enough, and the initial velocity in the domain of the Stokes operator, the solution is H² uniformly stable in time, depends continuously on initial data, and is unique. Finally, we obtain the limiting behavior of the system as the parameter N is big enough.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

Circulant integral operators as preconditioners for Wiener-Hopf equations

In this paper, we study the solutions of finite-section Wiener-Hopf equations by the preconditioned conjugate gradient method. Our main aim is to give an easy and general scheme of constructing good circulant integral operators as preconditioners for such equations. The circulant integral operators are constructed from sequences of conjugate symmetric functions {C }. Letk(t) denote the kernel function of the Wiener-Hopf equation and be its Fourier transform. We prove that for sufficiently large if {C } is uniformly bounded on the real lineR and the convolution product of the Fourier transform ofC with uniformly onR, then the circulant preconditioned Wiener-Hopf operator will have a clustered spectrum. It follows that the conjugate gradient method, when applied to solving the preconditioned operator equation, converges superlinearly. Several circulant integral operators possessing the clustering and fast convergence properties are constructed explicitly. Numerical examples are also given to demonstrate the performance of different circulant integral operators as preconditioners for Wiener-Hopf operators.Research supported in part by HKRGC grant no. 221600070.