On the perturbation of the zeros of complex polynomials

We investigate the deviation of the zeros of a polynomial. Thedeviation grows with the nth root of the perturbation of thepolynomial, where n is the degree of the polynomial, and thetask is to determine the factor in front of this root. We improveupon earlier results by Ostrowski and Schönhage and givesharp estimates. Applications are given in estimating the differencesof root-radii, which is important for the computation of thezeros of polynomials.     

On condition numbers in hp-FEM with Gauss–Lobatto-based shape functions

Sharp bounds on the condition number of stiffness matrices arising in hp/spectral discretizations for two-dimensional problems elliptic problems are given. Two types of shape functions that are based on Lagrange interpolation polynomials in the Gauss–Lobatto points are considered. These shape functions result in condition numbers O(p) and $\text{O(p}\text{ln}\text{p)}$ for the condensed stiffness matrices, where p is the polynomial degree employed. Locally refined meshes are analyzed. For the discretization of Dirichlet problems on meshes that are refined geometrically toward singularities, the conditioning of the stiffness matrix is shown to be independent of the number of layers of geometric refinement.     

Comparison of multigrid algorithms for high‐order continuous finite element discretizations

We present a comparison of different multigrid approaches for the solution of systems arising from high‐order continuous finite element discretizations of elliptic partial differential equations on complex geometries. We consider the pointwise Jacobi, the Chebyshev‐accelerated Jacobi, and the symmetric successive over‐relaxation smoothers, as well as elementwise block Jacobi smoothing. Three approaches for the multigrid hierarchy are compared: (1) high‐order h‐multigrid, which uses high‐order interpolation and restriction between geometrically coarsened meshes; (2) p‐multigrid, in which the polynomial order is reduced while the mesh remains unchanged, and the interpolation and restriction incorporate the different‐order basis functions; and (3) a first‐order approximation multigrid preconditioner constructed using the nodes of the high‐order discretization. This latter approach is often combined with algebraic multigrid for the low‐order operator and is attractive for high‐order discretizations on unstructured meshes, where geometric coarsening is difficult. Based on a simple performance model, we compare the computational cost of the different approaches. Using scalar test problems in two and three dimensions with constant and varying coefficients, we compare the performance of the different multigrid approaches for polynomial orders up to 16. Overall, both h‐multigrid and p‐multigrid work well; the first‐order approximation is less efficient. For constant coefficients, all smoothers work well. For variable coefficients, Chebyshev and symmetric successive over‐relaxation smoothing outperform Jacobi smoothing. While all of the tested methods converge in a mesh‐independent number of iterations, none of them behaves completely independent of the polynomial order. When multigrid is used as a preconditioner in a Krylov method, the iteration number decreases significantly compared with using multigrid as a solver. Copyright © 2015 John Wiley & Sons, Ltd.     

Numerical study of the HP version of mixed discontinuous finite element methods for reaction‐diffusion problems: The 1D case

This article studies the stability and convergence of the hp version of the three families of mixed discontinuous finite element (MDFE) methods for the numerical solution of reaction‐diffusion problems. The focus of this article is on these problems for one space dimension. Error estimates are obtained explicitly in the grid size h, the polynomial degree p, and the solution regularity; arbitrary space grids and polynomial degree are allowed. These estimates are asymptotically optimal in both h and p for some of these methods. Extensive numerical results to show convergence rates in h and p of the MDFE methods are presented. Theoretical and numerical comparisons between the three families of MDFE methods are described. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 525–553, 2003     

Mixed hp-DGFEM for incompressible flows II: Geometric edge meshes

We consider the Stokes problem of incompressible fluid flowin three-dimensional polyhedral domains discretized on hexahedralmeshes with hp-discontinuous Galerkin finite elements of typeQ_k for the velocity and Q_k–1 for the pressure. We provethat these elements are inf-sup stable on geometric edge meshesthat are refined anisotropically and non-quasiuniformly towardsedges and corners. The discrete inf-sup constant is shown tobe independent of the aspect ratio of the anisotropic elementsand is of O(k^–3/2) in the polynomial degree k, as in thecase of conforming Q_k–Q_k–2 approximations on thesame meshes.     

奇异摄动问题内罚间断有限方法的最优阶一致收敛性分析

本文在Bakhvalov-Shishkin网格上分析了采用高次元的内罚间断有限元方法求解一维对流扩散型奇异摄动问题的最优阶一致收敛性. 取k(k≥1)次分片多项式和网格剖分单元数为N时,在能量范数度量下, Bakhvalov-Shishkin网格上可获得O(N^-k)的一致误差估计. 在数值算例部分对理论分析结果进行了验证.     

A non-conforming finite element method with anisotropic mesh grading for the Stokes problem in domains with edges

The solution of the Stokes problem in three-dimensional domainswith edges has anisotropic singular behaviour which is treatednumerically by using anisotropic finite element meshes. Thevelocity is approximated by Crouzeix–Raviart (nonconformingP₁ ) elements and the pressure by piecewise constants. Thismethod is stable for general meshes (without minimal or maximalangle condition). Denoting by N_e the number of elements in themesh, the interpolation and consistency errors are of the optimalorder h N_e^–1/3 which is proved for tensor product meshes.As a by-product, we analyse also nonconforming prismatic elementswith P₁ [oplus ] span {x₃²} as the local space for the velocitywhere x₃ is the direction of the edge.     

A Lobatto interpolation grid in the tetrahedron

A sequence of increasingly refined interpolation grids insidethe tetrahedron is proposed with the goal of achieving uniformconvergence and ensuring high interpolation accuracy. The numberof interpolation nodes, N, corresponds to the number of termsin the complete mth-order polynomial expansion with respectto the three tetrahedral barycentric coordinates. The proposedgrid is constructed by deploying Lobatto interpolation nodesover the faces of the tetrahedron, and then computing interiornodes using a simple formula that involves the zeros of theLobatto polynomials. Numerical computations show that the Lebesgueconstant and interpolation accuracy of the proposed grid comparefavourably with those of alternative grids constructed by solvingoptimization problems. The condition number of the mass matrixis significantly lower than that of the uniform grid and comparableto that of optimal grids proposed by previous authors.     

Error expansion for a first-order upwind difference scheme applied to a model convection-diffusion problem

A singularly perturbed convection–diffusion problem isconsidered. The problem is discretized using a simple first-orderupwind difference scheme on general meshes. We derive an expansionof the error of the scheme that enables uniform error boundswith respect to the perturbation parameter in the discrete maximumnorm for both a defect correction method and the Richardsonextrapolation technique. This generalizes and simplifies resultsobtained in earlier publications by Fröhner et al.(2001,Numer. Algorithms, 26, 281–299) and by Natividad &Stynes (2003, Appl. Numer. Math., 45, 315–329). Numericalexperiments complement our theoretical results.     

Geometric meshes in collocation methods for Volterra integral equations with proportional delays

In this paper we analyse the local superconvergence propertiesof iterated piecewise polynomial collocation solutions for linearsecond-kind Volterra integral equations with (vanishing) proportionaldelays qt (0 < q < 1). It is shown that on suitable geometricmeshes depending on q, collocation at the Gauss points leadsto almost optimal superconvergence at the mesh points. Thiscontrasts with collocation on uniform meshes where the problemregarding the attainable order of local superconvergence remainsopen.     

The Parity Problem for Reducible Cubic Forms

Let f Z[x,y] be a reducible homogeneous polynomial of degree3. We show that f(x,y) has an even number of prime factors asoften as an odd number of prime factors.     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

The two-level local projection stabilization as an enriched one-level approach

The two-level local projection stabilization is considered as a one-level approach in which the enrichments on each element are piecewise polynomial functions. The dimension of the enrichment space can be significantly reduced without losing the convergence order. On triangular meshes, for example, using continuous piecewise polynomials of degree r ≥ 1, only 2r − 1 functions per macro-cell are needed for the enrichment compared to r ² in the two-level approach. In case of the Stokes problem r − 1 functions per macro-cell are already sufficient to guarantee stability and to preserve convergence order. On quadrilateral meshes the corresponding reduction rates are even higher. We give examples of “reduced” two-level approaches and study how the constant in the local inf-sup condition for the one-level and different two-level approaches, respectively, depends on the polynomial degree r.     

Improvements for some condition number estimates for preconditioned system in p‐FEM

In this paper, we consider domain decomposition preconditioners for a system of linear algebraic equations arising from the p‐version of the FEM. We analyse several multi‐level preconditioners for the Dirichlet problems in the sub‐domains in two and three dimensions. It is proved that the condition number of the preconditioned system is bounded by a constant independent of the polynomial degree. Relations between the p‐version of the FEM and the h‐version are helpful in the interpretations of the results. Copyright © 2006 John Wiley & Sons, Ltd.     

Uniform Convergence of Adaptive Multigrid Methods for Elliptic Problems and Maxwell's Equations

We consider the convergence theory of adaptive multigrid methods for second-order elliptic problems and Maxwell's equations. The multigrid algorithm only performs pointwise Gauss-Seidel relaxations on new degrees of freedom and their "immediate" neighbors. In the context of lowest order conforming finite element approximations, we present a unified proof for the convergence of adaptive multigrid V-cycle algorithms. The theory applies to any hierarchical tetrahedral meshes with uniformly bounded shape-regularity measures. The convergence rates for both problems are uniform with respect to the number of mesh levels and the number of degrees of freedom. We demonstrate our convergence theory by two numerical experiments.     

Counting alternating knots by genus

It is shown that the number of alternating knots of given genus g>1 grows as a polynomial of degree 6g−4 in the crossing number. The leading coefficient of the polynomial, which depends on the parity of the crossing number, is related to planar trivalent graphs with a Bieulerian path. The rate of growth of the number of such graphs is estimated.     

Group Actions and Asymptotic Behavior of Graded Polynomial Identities

Let F be an algebraically closed field of characteristic 0,and let A be a G-graded algebra over F for some finite abeliangroup G. Through G being regarded as a group of automorphismsof A, the duality between graded identities and G-identitiesof A is exploited. In this framework, the space of multilinearG-polynomials is introduced, and the asymptotic behavior ofthe sequence of G-codimensions of A is studied. Two characterizations are given of the ideal of G-graded identitiesof such algebra in the case in which the sequence of G-codimensionsis polynomially bounded. While the first gives a list of G-identitiessatisfied by A, the second is expressed in the language of therepresentation theory of the wreath product G S_n, where S_nis the symmetric group of degree n. As a consequence, it is proved that the sequence of G-codimensionsof an algebra satisfying a polynomial identity either is polynomiallybounded or grows exponentially.     

SUB-OPTIMAL CONVERGENCE OF DISCONTINUOUS GALERKIN METHODS WITH CENTRAL FLUXES FOR LINEAR HYPERBOLIC EQUATIONS WITH EVEN DEGREE POLYNOMIAL APPROXIMATIONS

In this paper,we theoretically and numerically verify that the discontinuous Galerkin(DG)methods with central fluxes for linear hyperbolic equations on non-uniform meshes have sub-optimal convergence properties when measured in the L2-norm for even degree polynomial approximations.On uniform meshes,the optimal error estimates are provided for arbitrary number of cells in one and multi-dimensions,improving previous results.The theoretical findings are found to be sharp and consistent with numerical results.     

Optimal algebraic multilevel preconditioning for local refinement along a line

The application of some recently proposed algebraic multilevel methods for the solution of two-dimensional finite element problems on nonuniform meshes is studied. The locally refined meshes are created by the newest vertex mesh refinement method. After the introduction of this refinement technique it is shown that, by combining levels of refinement, a preconditioner of optimal order can be constructed for the case of local refinement along a line. Its relative condition number is accurately estimated. Numerical tests demonstrating the performance of the proposed preconditioners will be reported in a forthcoming paper.     

Optimal error estimates for the hp-version interior penalty discontinuous Galerkin finite element method

We consider the hp-version interior penalty discontinuous Galerkinfinite-element method (hp-DGFEM) for second-order linear reaction–diffusionequations. To the best of our knowledge, the sharpest knownerror bounds for the hp-DGFEM are due to Rivière et al.(1999,Comput. Geosci., 3, 337–360) and Houston et al.(2002,SIAM J. Numer. Anal., 99, 2133–2163). These are optimalwith respect to the meshsize h but suboptimal with respect tothe polynomial degree p by half an order of p. We present improvederror bounds in the energy norm, by introducing a new functionspace framework. More specifically, assuming that the solutionsbelong element-wise to an augmented Sobolev space, we deducefully hp-optimal error bounds.