Bounds for the Roots of Lacunary Polynomials

A polynomial P(X)  = X^d + a_d − 1X^d − 1 + ⋯ is called lacunary when a_d − 1 =  0. We give bounds for the roots of such polynomials with complex coefficients. These bounds are much smaller than for general polynomials.     

Some Methods for Simultaneous Extraction of a Part of All Multiple Roots of Algebraic Polynomials

In this paper, the new methods being generalizations of Weierstrass-Dochev method have been demonstrated. These methods possess quadratic convergence if the multiplicities of the roots, which we seek, are known and they can be used for simultaneous determination of all roots or only part of all roots.     

Finite Element-Based Level Set Methods for Higher Order Flows

In this paper we shall discuss the numerical simulation of geometric flows by level set methods. Main examples under considerations are higher order flows, such as surface diffusion and Willmore flow as well as variants of them with more complicated surface energies. Such problems find various applications, e.g. in materials science (thin film growth, grain boundary motion), biophysics (membrane shapes), and computer graphics (surface smoothing and restoration). We shall use spatial discretizations by finite element methods and semi-implicit time stepping based on local variational principles, which allows to maintain dissipation properties of the flows by the discretization. In order to compensate for the missing maximum principle, which is indeed a major hurdle for the application of level set methods to higher order flows, we employ frequent redistancing of the level set function. Finally we also discuss the solution of the arising discretized linear systems in each time step and some particular advantages of the finite element approach such as the variational formulation which allows to handle the higher order and various anisotropies efficiently and the possibility of local adaptivity around the zero level set.     

Algorithms for Modular Counting of Roots of Multivariate Polynomials

Given a multivariate polynomial P(X ₁,…,X _n ) over a finite field , let N(P) denote the number of roots over . The modular root counting problem is given a modulus r, to determine N _r (P)=N(P)mod r. We study the complexity of computing N _r (P), when the polynomial is given as a sum of monomials. We give an efficient algorithm to compute N _r (P) when the modulus r is a power of the characteristic of the field. We show that for all other moduli, the problem of computing N _r (P) is -hard. We present some hardness results which imply that our algorithm is essentially optimal for prime fields. We show an equivalence between maximum-likelihood decoding for Reed-Solomon codes and a root-finding problem for symmetric polynomials. P. Gopalan’s and R.J Lipton’s research was supported by NSF grant CCR-3606B64. V. Guruswami’s research was supported in part by NSF grant CCF-0343672 and a Sloan Research Fellowship.     

Higher Order Convergence for Multidimensional Functions with a New Taylor-Bernstein Form as Inclusion Function

Recently, Lin and Rokne (Interval Approximation of Higher Order to the Ranges of Functions, Computers Math. Applic. 31(7) (1996), pp. 101-109) introduced the so-called Taylor-Bernstein (TB) form as an inclusion function form for multidimensional functions. This form was theoretically shown to have the property of higher order convergence. In this paper, we present an improvement of Lin and Rokne's TB form to make it more effective in practice. We test and compare the higher order convergence behavior of the proposed TB form with that of Lin and Rokne's TB form and also with that of the Taylor model of Berz et al. (Computation and Application of Taylor Polynomials with Interval Remainder Bounds, Reliable Computing 4(1) (1998), pp. 83-97). For the testing, we consider six benchmark examples with dimensions varying from 1 to 6. In all examples, unlike with the Taylor model and Lin and Rokne's TB form, we obtain higher order convergence of orders up to 9 with the proposed TB form. Moreover, with the proposed TB form we quite easily obtain such high orders of convergence for up to 5-dim problems.     

Radial Basis Function Methods for the Rosenau Equation and Other Higher Order PDEs

Meshfree methods based on radial basis function (RBF) approximation are of interest for numerical solution of partial differential equations because they are flexible with respect to the geometry of the computational domain, they can provide high order convergence, they are not more complicated for problems with many space dimensions and they allow for local refinement. The aim of this paper is to show that the solution of the Rosenau equation, as an example of an initial-boundary value problem with multiple boundary conditions, can be implemented using RBF approximation methods. We extend the fictitious point method and the resampling method to work in combination with an RBF collocation method. Both approaches are implemented in one and two space dimensions. The accuracy of the RBF fictitious point method is analyzed partly theoretically and partly numerically. The error estimates indicate that a high order of convergence can be achieved for the Rosenau equation. The numerical experiments show that both methods perform well. In the one-dimensional case, the accuracy of the RBF approaches is compared with that of the corresponding pseudospectral methods, showing similar or slightly better accuracy for the RBF methods. In the two-dimensional case, the Rosenau problem is solved both in a square domain and in an irregular domain with smooth boundary, to illustrate the capability of the RBF-based methods to handle irregular geometries.     

Local Discontinuous Galerkin Methods for Partial Differential Equations with Higher Order Derivatives

In this paper we review the existing and develop new local discontinuous Galerkin methods for solving time dependent partial differential equations with higher order derivatives in one and multiple space dimensions. We review local discontinuous Galerkin methods for convection diffusion equations involving second derivatives and for KdV type equations involving third derivatives. We then develop new local discontinuous Galerkin methods for the time dependent bi-harmonic type equations involving fourth derivatives, and partial differential equations involving fifth derivatives. For these new methods we present correct interface numerical fluxes and prove L ² stability for general nonlinear problems. Preliminary numerical examples are shown to illustrate these methods. Finally, we present new results on a post-processing technique, originally designed for methods with good negative-order error estimates, on the local discontinuous Galerkin methods applied to equations with higher derivatives. Numerical experiments show that this technique works as well for the new higher derivative cases, in effectively doubling the rate of convergence with negligible additional computational cost, for linear as well as some nonlinear problems, with a local uniform mesh.     

Implementations of a New Theorem for Computing Bounds for Positive Roots of Polynomials

Finding an upper bound for the positive roots of univariate polynomials is an important step of the continued fractions real root isolation algorithm. The revived interest in this algorithm has highlighted the need for better estimations of upper bounds of positive roots. In this paper we present a new theorem, based on a generalization of a theorem by D. Stefanescu, and describe several implementations of it – including Cauchy's and Kioustelidis' rules as well as two new rules recently developed by us. From the empirical results presented here we see that applying various implementations of our theorem – and taking the minimum of the computed values – greatly improves the estimation of the upper bound and hopefully that will affect the performance of the continued fractions real root isolation method.     

A Generic Stabilization Approach for Higher Order Discontinuous Galerkin Methods for Convection Dominated Problems

In this paper we present a stabilized Discontinuous Galerkin (DG) method for hyperbolic and convection dominated problems. The presented scheme can be used in several space dimension and with a wide range of grid types. The stabilization method preserves the locality of the DG method and therefore allows to apply the same parallelization techniques used for the underlying DG method. As an example problem we consider the Euler equations of gas dynamics for an ideal gas. We demonstrate the stability and accuracy of our method through the detailed study of several test cases in two space dimension on both unstructured and cartesian grids. We show that our stabilization approach preserves the advantages of the DG method in regions where stabilization is not necessary. Furthermore, we give an outlook to adaptive and parallel calculations in 3d.     

Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients

We present a method for discretizing and solving general elliptic partial differential equations on sparse grids employing higher order finite elements. On the one hand, our approach is charactarized by its simplicity. The calculation of the occurring functionals is composed of basic pointwise or unidirectional algorithms. On the other hand, numerical experiments prove our method to be robust and accurate. Discontinuous coefficients can be treated as well as curvilinearly bounded domains. When applied to adaptively refined sparse grids, our discretization results to be highly efficient, yielding balanced errors on the computational domain.     

Superconvergence of Local Discontinuous Galerkin Methods for Partial Differential Equations with Higher Order Derivatives

In this paper, we present a unified approach to study superconvergence behavior of the local discontinuous Galerkin (LDG) method for high-order time-dependent partial differential equations. We select the third and fourth order equations as our models to demonstrate this approach and the main idea. Superconvergence results for the solution itself and the auxiliary variables are established. To be more precise, we first prove that, for any polynomial of degree k, the errors of numerical fluxes at nodes and for the cell averages are superconvergent under some suitable initial discretization, with an order of \(O(h^{2k+1})\). We then prove that the LDG solution is \((k+2)\)-th order superconvergent towards a particular projection of the exact solution and the auxiliary variables. As byproducts, we obtain a \((k+1)\)-th and \((k+2)\)-th order superconvergence rate for the derivative and function value approximation separately at a class of Radau points. Moreover, for the auxiliary variables, we, for the first time, prove that the convergence rate of the derivative error at the interior Radau points can reach as high as \(k+2\). Numerical experiments demonstrate that most of our error estimates are optimal, i.e., the error bounds are sharp.     

Global Optimization with Higher Order Inclusion Function Forms Part 1: A Combined Taylor-Bernstein Form

Recently, two versions of the so-called Taylor-Bernstein (TB) form having the property of higher order convergence were proposed in [5] and [10]. However, in many application problems, both these TB forms encounter difficulties in computing the range enclosures for some domain widths, due to excessive memory and/or time requirements. In this paper, we present a combined TB form that is more successful in computing the range enclosures as the domain shrinks from large to small widths. We test and compare the performance of the proposed form with those of the existing TB forms, the Taylor model of Berz et al. [1], and the simple natural inclusion function form. For the testing, we consider six benchmark examples with dimensions varying from 1 to 6. The results of the tests show that the proposed combined TB form is indeed more effective than the existing TB forms and the Taylor model, over the entire range of domain widths considered. This revised version was published online in June 2006 with corrections to the Cover Date.     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

Weierstrass-like Methods with Corrections for the Inclusion of Polynomial Zeros

In this paper, we present iterative methods of Weierstress’ type for the simultaneous inclusion of all simple zeros of a polynomial. The main advantage of the proposed methods is the increase of the convergence rate attained by applying suitable correction terms. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods. Numerical examples are given.     

求复函数方程根的遗传算法

遗传算法(GA)作为一门新兴学科,从20世纪80代开始迅速发展,得到了越来越多专家们的重视。文章提出了一种用基于模拟退火思想的GA,实现求复函数方程根,并得到令人满意的结果;研究和探讨了该算法实现的数学理论、关键技术。该算法优于解复函数方程根常用的迭代法、下山法等方法。     

Galerkin Methods for Stochastic Hyperbolic Problems Using Bi-Orthogonal Polynomials

This work is concerned with scalar transport equations with random transport velocity. We first give some sufficient conditions that can guarantee the solution to be in appropriate random spaces. Then a Galerkin method using bi-orthogonal polynomials is proposed, which decouples the equation in the random spaces, yielding a sequence of uncoupled equations. Under the assumption that the random wave field has a structure of the truncated KL expansion, a principle on how to choose the orders of the approximated polynomial spaces is given based on the sensitivity analysis in the random spaces. By doing this, the total degree of freedom can be reduced significantly. Numerical experiments are carried out to illustrate the efficiency of the proposed method.