Iterative methods for solvingAx=b,GMRES/FOM versus QMR/BiCG

We study the convergence of the GMRES/FOM and QMR/BiCG methods for solving nonsymmetric systems of equationsAx=b. We prove, in exact arithmetic, that any type of residual norm convergence obtained using BiCG can also be obtained using FOM but on a different system of equations. We consider practical comparisons of these procedures when they are applied to the same matrices. We use a unitary invariance shared by both methods, to construct test matrices where we can vary the nonnormality of the test matrix by variations in simplified eigenvector matrices. We used these test problems in two sets of numerical experiments. The first set of experiments was designed to study effects of increasing nonnormality on the convergence of GMRES and QMR. The second set of experiments was designed to track effects of the eigenvalue distribution on the convergence of QMR. In these tests the GMRES residual norms decreased significantly more rapidly than the QMR residual norms but without corresponding decreases in the error norms. Furthermore, as the nonnormality ofA was increased, the GMRES residual norms decreased more rapidly. This led to premature termination of the GMRES procedure on highly nonnormal problems. On the nonnormal test problems the QMR residual norms exhibited less sensitivity to changes in the nonnormality. The convergence of either type of procedure, as measured by the error norms, was delayed by the presence of large or small outliers and affected by the type of eigenvalues, real or complex, in the eigenvalue distribution ofA. For GMRES this effect can be seen only in the error norm plots.In honor of the 70th birthday of Ted RivlinThis work was supported by NSF grant GER-9450081.     

By How Much Can Residual Minimization Accelerate the Convergence of Orthogonal Residual Methods?

We capitalize upon the known relationship between pairs of orthogonal and minimal residual methods (or, biorthogonal and quasi-minimal residual methods) in order to estimate how much smaller the residuals or quasi-residuals of the minimizing methods can be compared to those of the corresponding Galerkin or Petrov–Galerkin method. Examples of such pairs are the conjugate gradient (CG) and the conjugate residual (CR) methods, the full orthogonalization method (FOM) and the generalized minimal residual (GMRES) method, the CGNE and BiCG versions of applying CG to the normal equations, as well as the biconjugate gradient (BiCG) and the quasi-minimal residual (QMR) methods. Also the pairs consisting of the (bi)conjugate gradient squared (CGS) and the transpose-free QMR (TFQMR) methods can be added to this list if the residuals at half-steps are included, and further examples can be created easily.The analysis is more generally applicable to the minimal residual (MR) and quasi-minimal residual (QMR) smoothing processes, which are known to provide the transition from the results of the first method of such a pair to those of the second one. By an interpretation of these smoothing processes in coordinate space we deepen the understanding of some of the underlying relationships and introduce a unifying framework for minimal residual and quasi-minimal residual smoothing. This framework includes the general notion of QMR-type methods.     

BiCR variants of the hybrid BiCG methods for solving linear systems with nonsymmetric matrices

We propose Bi-Conjugate Residual (BiCR) variants of the hybrid Bi-Conjugate Gradient (BiCG) methods (referred to as the hybrid BiCR variants) for solving linear systems with nonsymmetric coefficient matrices. The recurrence formulas used to update an approximation and a residual vector are the same as those used in the corresponding hybrid BiCG method, but the recurrence coefficients are different; they are determined so as to compute the coefficients of the residual polynomial of BiCR. From our experience it appears that the hybrid BiCR variants often converge faster than their BiCG counterpart. Numerical experiments show that our proposed hybrid BiCR variants are more effective and less affected by rounding errors. The factor in the loss of convergence speed is analyzed to clarify the difference of the convergence between our proposed hybrid BiCR variants and the hybrid BiCG methods.     

The Breakdowns of BiCGStab

The effects of the three principal possible exact breakdowns which may occur using BiCGStab are discussed. BiCGStab is used to solve large sparse linear systems of equations, such as arise from the discretisation of PDEs. These PDEs often involve a parameter, say . We investigate here how the numerical error grows as breakdown is approached by letting tend to a critical value, say _c, at which the breakdown is numerically exact. We found empirically in our examples that loss of numerical accuracy due stabilisation breakdown and Lanczos breakdown was discontinuous with respect to variation of around _c. By contrast, the loss of numerical accuracy near a critical value _c for pivot breakdown is roughly proportional to |–_c|^–1.     

BiCGStab,VPAStab and an adaptation to mildly nonlinear systems

The key equations of BiCGStab are summarised to show its connections with Padé and vector-Padé approximation. These considerations lead naturally to stabilised vector-Padé approximation of a vector-valued function (VPAStab), and an algorithm for the acceleration of convergence of a linearly generated sequence of vectors. A generalisation of this algorithm for the acceleration of convergence of a nonlinearly generated system is proposed here, and comparative numerical results are given.     

Motzkin树上的保护点的计数问题

In this paper,we enumerate the set of Motzkin trees with n edges according to the number of leaves,the number of vertices adjacent to a leaf,the number of protected nodes,the number of(protected)branch nodes,and the number of(protected)lonely nodes.Explicit formulae as well as generating functions are obtained.We also find that,as n goes to infinity,the proportion of protected branch nodes and protected lonely nodes among all vertices of Motzkin trees with n edges approaches 4/27 and 2/9.     

Generalized global conjugate gradient squared algorithm

In this paper, a generalized global conjugate gradient squared method for solving nonsymmetric linear systems with multiple right-hand sides is presented. The method can be derived by using products of two nearby global BiCG polynomials and formal orthogonal polynomials, of which global CGS and global BiCGSTAB are just particular cases. We also show to apply the method for solving the Sylvester matrix equation. Finally, numerical examples are given to illustrate the effectiveness of the proposed method.     

具有第二大基指数的本原对称带号有向图的刻画

Recently, the primitive symmetric signed digraphs on n vertices with the maximum base 2n and the primitive symmetric loop-free signed digraphs on n vertices with the maximum base 2n-1 are characterized, respectively. In this paper, the primitive symmetric signed digraphs with loops on n vertices with the base 2n-1 are characterized, and then the primitive symmetric signed digraphs on n vertices with the second maximum base 2n-1 are characterized.     

VPAStab: Stabilised Vector-Padé Approximation with Application to Linear Systems

An algorithm called VPAStab is given for the acceleration of convergence of a sequence of vectors. It combines a method of vector-Padé approximation with a successful technique for stabilisation. More generally, this algorithm is designed to find the fixed point of the generating function of the given sequence of vectors, analogously to the way in which ordinary Padé approximants can accelerate the convergence of a given scalar sequence. VPAStab is justified in the context of its application to the solution of a large sparse system of linear equations. The possible breakdowns of the algorithm are listed. Numerical experiments indicate that these breakdowns can be classified either as pivot-type (type L) or as ghost-type (type D).     

求解非对称线性方程组的QMRGCGS方法

1 引言 求解非对称线性方程组Ax=b的双共轭梯度方法(BCG)[3]和它的变形共轭梯度平方方法(CGS)[6]都有典型的不规则收敛行为,后来Freund和Nachtigal提出一种BCG类方法,即拟极小剩余方法(QMR)[7],用来补救BCG方法的收敛性并且产生了光滑的收敛曲线。然而,象BCG方法一样,QMR方法要用到系数矩阵A及其转置A~T与向量的乘积,为了解决这一问题,Freund提出TFQMR方法,此方法具有拟极小剩余性,同时不需用到A~T与向量的乘积。     

通过增强型萨格勒布指数对图排序

Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.     

A Convergence Analysis of Gmres and Fom Methods for Sylvester Equations

We discuss convergence properties of the GMRES and FOM methods for solving large Sylvester equations of the form AX–XB=C. In particular we show the importance of the separation between the fields of values of A and B on the convergence behavior of GMRES. We also discuss the stagnation phenomenon in GMRES and its consequence on FOM. We generalize the issue of breakdown in the block-Arnoldi algorithm and explain its consequence on FOM and GMRES methods. Several numerical tests illustrate the theoretical results.     

On the Complexity of Halfspace Area Queries

Given a nonconvex simple polygon $P$ with $n$ vertices, is it possible to construct a data structure which after preprocessing can answer halfspace area queries (i.e., given a line, determine the area of the portion of the polygon above the line) in $o(n)$ time? We answer negatively, proving an $\Omega(n)$ lower bound on the query time of any data structure performing this task. We then consider the offline version of the same problem: given a polygon $P$ with $n$ vertices, and $k$ query lines, we present an algorithm that computes the area of $P$ on both sides of each line in $O(k^{2/3}n^{2/3+\varepsilon}+(n+k)\polylog{n})$ time. Variants of this method allow the query of a collection of weighted polygons with or without holes, and solve several other related problems within the same time bounds.     

Derivation of BiCG from the conditions defining lanczos' method for solving a system of linear equations

Lanczos' method for solving the system of linear algebraic equations Ax=b consists in constructing a sequence of vectors x _k in such a way that and . This sequence of vectors can be computed by the BiCG (BiOMin) algorithm. In this paper is shown how to obtain the recurrences of BiCG (BiOMin) directly from this conditions.     

Dense Point Sets Have Sparse Delaunay Triangulations or “... But Not Too Nasty”

The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of $n$ points in~$\Real^3$ with spread $\Delta$ has complexity $O(\Delta^3)$. This bound is tight in the worst case for all $\Delta = O(\sqrt{n})$. In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of $k$-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any $n$ and $\Delta = O(n)$, we construct a regular triangulation of complexity $\Omega(n\Delta)$ whose $n$ vertices have spread $\Delta$.     

Bifurcation of Limit Cycles of a Perturbed Pendulum Equation

This paper investigates the limit cycle bifurcation problem of the pendulum equation on the cylinder of the form $\dot{x}=y, \dot{y}=-\sin x$ under perturbations of polynomials of $\sin x$, $\cos x$ and $y$ of degree $n$ with a switching line $y=0$. We first prove that the corresponding first order Melnikov functions can be expressed as combinations of anti-trigonometric functions and the complete elliptic functions of first and second kind with polynomial coefficients in both the oscillatory and rotary regions for arbitrary $n$. We also verify the independence of coefficients of these polynomials. Then, the lower bounds for the number of limit cycles are obtained using their asymptotic expansions with $n=1,2,3$.     

第二大根小于1的简单图

设G为n阶简单图,λ2(G)为G的第二大特征根．我们给出了所有使λ2(G)<1 的偶图,以及使λ2(G)<1、围长不小于4的非偶图．     

拟树图按第二大无符号拉普拉斯特征值排序

A connected graph G=(V,E) is called a quasi-tree graph if there exists a vertex v_0∈V(G) such that G-v_0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.     

Halin图$Q$-谱半径的最大值

The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.