Search

We consider discretizations of the stationary Stokes equation in three spatial dimensions by non-conforming Crouzeix-Raviart elements. The original definition in the seminal paper by M. Crouzeix and P.-A. Raviart in 1973 [Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge 7 (1973), pp. 33–75] is implicit and also contains substantial freedom for a concrete choice. In this paper, we introduce basic Crouzeix-Raviart spaces in 3D in analogy to the 2D case in a fully explicit way. We prove that this basic Crouzeix-Raviart element for the Stokes equation is inf-sup stable for polynomial degree k=2 (quadratic velocity approximation). We identify spurious pressure modes for the conforming \left (k,k-1\right) 3D Stokes element and show that these are eliminated by using the basic Crouzeix-Raviart space. [ABSTRACT FROM AUTHOR]

In nice cases, a zero-dimensional complete intersection ideal over a field has a Shape Lemma. There are also cases where the ideal is generated by the resultant and first subresultant polynomials of the generators. This paper explores the relation between these representations and studies when the resultant generates the elimination ideal. We also prove a Poisson formula for resultants arising from the hidden variable method. [ABSTRACT FROM AUTHOR]

As one myth of polynomial interpolation and quadrature, Trefethen [Math. Today (Southend-on-Sea) 47 (2011), pp. 184–188] revealed that the Chebyshev interpolation of |x-a| (with |a|<1) at the Clenshaw-Curtis points exhibited a much smaller error than the best polynomial approximation (in the maximum norm) in about 95% range of [-1,1] except for a small neighbourhood near the singular point x=a. In this paper, we rigorously show that the Jacobi expansion for a more general class of \Phi-functions also enjoys such a local convergence behaviour. Our assertion draws on the pointwise error estimate using the reproducing kernel of Jacobi polynomials and the Hilb-type formula on the asymptotic of the Bessel transforms. We also study the local superconvergence and show the gain in order and the subregions it occurs. As a by-product of this new argument, the undesired \log n-factor in the pointwise error estimate for the Legendre expansion recently stated in Babus̆ka and Hakula [Comput. Methods Appl. Mech Engrg. 345 (2019), pp. 748–773] can be removed. Finally, all these estimates are extended to the functions with boundary singularities. We provide ample numerical evidences to demonstrate the optimality and sharpness of the estimates. [ABSTRACT FROM AUTHOR]

A classical technique to construct polynomial preserving extensions of scalar functions defined on the boundary of an n simplex to the interior is to use so-called rational blending functions. The purpose of this paper is to generalize the construction by blending to the de Rham complex. More precisely, we define polynomial preserving extensions which map traces of k-forms defined on the boundary of the simplex to k-forms defined in the interior. Furthermore, the extensions are cochain maps, i.e., they commute with the exterior derivative. [ABSTRACT FROM AUTHOR]

Let N be one of the 38 distinct square-free integers such that the arithmetic group \Gamma _0(N)^+ has genus one. We constructed canonical generators x_N and y_N for the associated function field (see Jorgenson, L. Smajlović, and H. Then [Exp. Math. 25 (2016), pp. 295–319]). In this article we study the Schwarzian derivative of x_N, which we express as a polynomial in y_N with coefficients that are rational functions in x_N. As a corollary, we prove that for any point e in the upper half-plane which is fixed by an element of \Gamma _0(N)^+, one can explicitly evaluate x_N(e) and y_N(e). As it turns out, each value x_N(e) and y_N(e) is an algebraic integer which we are able to understand in the context of explicit class field theory. When combined with our previous article (see Jorgenson, L. Smajlović, and H. Then [Exp. Math. 29 (2020), pp. 1–27]), we now have a complete investigation of x_N(\tau) and y_N(\tau) at any CM point \tau, including elliptic points, for any genus one group \Gamma _0(N)^+. Furthermore, the present article when combined with the two aforementioned papers leads to a procedure which we expect to yield generators of class fields, and certain subfields, using the Schwarzian derivative and which does not use either modular polynomials or Shimura reciprocity. [ABSTRACT FROM AUTHOR]

This paper presents a new framework for computing Gröbner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Gröbner basis for this module contains Gröbner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gröbner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing Göbner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice. [ABSTRACT FROM AUTHOR]

This paper presents regularity results and associated high order numerical methods for one-dimensional fractional-Laplacian boundary-value problems. On the basis of a factorization of solutions as a product of a certain edge-singular weight ω times a "regular" unknown, a characterization of the regularity of solutions is obtained in terms of the smoothness of the corresponding right-hand sides. In particular, for right-hand sides which are analytic in a Bernstein ellipse, analyticity in the same Bernstein ellipse is obtained for the "regular" unknown. Moreover, a sharp Sobolev regularity result is presented which completely characterizes the co-domain of the fractional-Laplacian operator in terms of certain weighted Sobolev spaces introduced in (Babuska and Guo, SIAM J. Numer. Anal. 2002). The present theoretical treatment relies on a full eigendecomposition for a certain weighted integral operator in terms of the Gegenbauer polynomial basis. The proposed Gegenbauer-based Nystr¨om numerical method for the fractional-Laplacian Dirichlet problem, further, is significantly more accurate and efficient than other algorithms considered previously. The sharp error estimates presented in this paper indicate that the proposed algorithm is spectrally accurate, with convergence rates that only depend on the smoothness of the right-hand side. In particular, convergence is exponentially fast (resp. faster than any power of the mesh-size) for analytic (resp. infinitely smooth) right-hand sides. The properties of the algorithm are illustrated with a variety of numerical results. [ABSTRACT FROM AUTHOR]

We study function approximation in the average case setting for spaces of ∞-variate functions that have a weighted tensor product form and are endowed with a Gaussian measure that also has a weighted tensor product form. Moreover, we assume that the cost of function evaluation depends on the number of active variables and we allow it to be from linear to exponential. We provide a necessary and sufficient condition for the problem to be polynomially tractable and derive the exact value of the tractability exponent. In particular, the approximation problem is polynomially tractable under modest conditions on weights even if the function evaluation cost is exponential in the number of active variables. The problem is weakly tractable even if this cost is doubly exponential. These results hold for algorithms that can use unrestricted linear information. Similar results hold for weighted L2 approximation, a special case of function approximation problems considered in this paper, and algorithms restricted to those that use only function samplings. [ABSTRACT FROM AUTHOR]

We say a power series ∑n=0∞ anqn is multiplicative if the sequence 1,a2/a1, . . . ,an/a1, . . . is so. In this paper, we consider multiplicative power series ƒ such that ƒ2 is also multiplicative. We find a number of examples for which ƒ is a rational function or a theta series and prove that the complete set of solutions is the locus of a (probably reducible) affine variety over C. The precise determination of this variety turns out to be a finite computational problem, but it seems to be beyond the reach of current computer algebra systems. The proof of the theorem depends on a bound on the logarithmic capacity of the Mandelbrot set. [ABSTRACT FROM AUTHOR]

This paper develops and analyzes two local discontinuous Galerkin (LDG) methods using piecewise linear polynomials for the Helmholtz equation with the first order absorbing boundary condition in the high frequency regime. It is shown that the proposed LDG methods are stable for all positive wave number k and all positive mesh size h. Energy norm and L2-norm error estimates are derived for both LDG methods in all mesh parameter regimes including pre-asymptotic regime (i.e., k2h ≳ 1). To analyze the proposed LDG methods, they are recast and treated as (nonconforming) mixed finite element methods. The crux of the analysis is to show that the sesquilinear form associated with each LDG method satisfies a coercivity property in all mesh parameter regimes. These coercivity properties then easily infer the desired discrete stability estimates for the solutions of the proposed LDG methods. In return, the discrete stabilities not only guarantee the well-posedness of the LDG methods but also play a crucial role in the error analysis. Numerical experiments are also presented in the paper to validate the theoretical results and to compare the performance of the proposed two LDG methods. [ABSTRACT FROM AUTHOR]

We propose an approach to constructing iterative methods for finding polynomial roots simultaneously. One feature of this approach is using the fundamental theorem of symmetric polynomials. Within this framework, we reconstruct many of the existing root finding methods. The new results presented in this paper are some modifications of the Durand-Kerner method. [ABSTRACT FROM AUTHOR]

A characteristic pair is a pair (G, C) of polynomial sets in which G is a reduced lexicographic Gröbner basis and C is the minimal triangular set contained in G. It is said to be normal (or strong normal) if C is normal (or C is normal and its saturated ideal equals the ideal generated by G). In this paper, we show that any finite polynomial set P can be decomposed algorithmically into finitely many (strong) normal characteristic pairs with associated zero relations, which provide representations for the zero set of P in terms of those of Gröbner bases and those of triangular sets. The algorithm we propose for the decomposition makes use of the inherent connection between Ritt characteristic sets and lexicographic Gröbner bases and is based essentially on the structural properties and the computation of lexicographic Gröbner bases. Several nice properties about the decomposition and the resulting (strong) normal characteristic pairs, in particular relationships between the Gröbner basis and the triangular set in each pair, are established. Examples are given to illustrate the algorithm and some of the properties. [ABSTRACT FROM AUTHOR]

The standard way to solve polynomial eigenvalue problems is through linearizations. The family of Fiedler linearizations, which includes the classical Frobenius companion forms, presents many interesting properties from both the theoretical and the applied point of view. These properties make the Fiedler pencils a very attractive family of linearizations to be used in the solution of polynomial eigenvalue problems. However, their numerical features for general matrix polynomials had not yet been fully investigated. In this paper, we analyze the backward error of eigenpairs and the condition number of eigenvalues of Fiedler linearizations in the solution of polynomial eigenvalue problems. We get bounds for: (a) the ratio between the backward error of an eigenpair of the matrix polynomial and the backward error of the corresponding (computed) eigenpair of the linearization, and (b) the ratio between the condition number of an eigenvalue in the linearization and the condition number of the same eigenvalue in the matrix polynomial. A key quantity in these bounds is \rho , the ratio between the maximum norm of the coefficients of the polynomial and the minimum norm of the leading and trailing coefficient. If the matrix polynomial is well scaled (i. e., all its coefficients have a similar norm, which implies ρ ≈ 1), then solving the Polynomial Eigenvalue Problem with any Fiedler linearization will give a good performance from the point of view of backward error and conditioning. In the more general case of badly scaled matrix polynomials, dividing the coefficients of the polynomial by the maximum norm of its coefficients allows us to get better bounds. In particular, after this scaling, the ratio between the eigenvalue condition number in any two Fiedler linearizations is bounded by a quantity that depends only on the size and the degree of the polynomial. We also analyze the effect of parameter scaling in these linearizations, which improves significantly the backward error and conditioning in some cases where ρ is large. Several numerical experiments are provided to support our theoretical results. [ABSTRACT FROM AUTHOR]

The Crouzeix-Raviart triangular finite elements are \inf-\sup stable for the Stokes equations for any mesh with at least one interior vertex. This result affirms a conjecture of Crouzeix-Falk from 1989 for p=3. Our proof applies to any odd degree p\ge 3 and concludes the overall stability analysis: Crouzeix-Raviart triangular finite elements of degree p in two dimensions and the piecewise polynomials of degree p-1 with vanishing integral form a stable Stokes pair for all positive integers p. [ABSTRACT FROM AUTHOR]

Braid combing is a procedure defined by Emil Artin to solve the word problem in braid groups. It is well known to have exponential complexity. In this paper, we use the theory of straight line programs to give a polynomial algorithm which performs braid combing. This procedure can be applied to braids on surfaces, providing the first algorithm (to our knowledge) which solves the word problem for braid groups on surfaces with boundary in polynomial time and space. In the case of surfaces without boundary, braid combing needs to use a section from the fundamental group of the surface to the braid group. Such a section was shown to exist by Gonçalves and Guaschi, who also gave a geometric description. We propose an algebraically simpler section, which we describe explicitly in terms of generators of the braid group, and we show why the above procedure to comb braids in polynomial time does not work in this case. [ABSTRACT FROM AUTHOR]

We define an Artin prime for an integer g to be a prime such that g is a primitive root modulo that prime. Let g ∊ Z \ {-1} and not a perfect square. A conjecture of Artin states that the set of Artin primes for g has a positive density. In this paper we study a generalization of this conjecture for the primes produced by a polynomial and explore its connection with the problem of finding a fixed integer g and a prime producing polynomial f(x) with the property that a long string of consecutive primes produced by f(x) are Artin primes for g. By employing some results of Moree, we propose a general method for finding such polynomials f(x) and integers g. We then apply this general procedure for linear, quadratic, and cubic polynomials to generate many examples of polynomials with very large Artin prime production length. More specifically, among many other examples, we exhibit linear, quadratic, and cubic (respectively) polynomials with 6355, 37951, and 10011 (respectively) consecutive Artin primes for certain integers g. [ABSTRACT FROM AUTHOR]

In this paper, we consider computational methods for optimizing a multivariate inhomogeneous polynomial function over a general convex set. The focus is on the design and analysis of polynomial-time approximation algorithms. The methods are able to deal with optimization models with polynomial objective functions in any fixed degrees. In particular, we first study the problem of maximizing an inhomogeneous polynomial over the Euclidean ball. A polynomial-time approximation algorithm is proposed for this problem with an assured (relative) worst-case performance ratio, which is dependent only on the dimensions of the model. The method and approximation ratio are then generalized to optimize an inhomogeneous polynomial over the intersection of a finite number of co-centered ellipsoids. Furthermore, the constraint set is extended to a general convex compact set. Specifically, we propose a polynomial-time approximation algorithm with a (relative) worst-case performance ratio for polynomial optimization over some convex compact sets, e.g., a polytope. Finally, numerical results are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated instances. [ABSTRACT FROM AUTHOR]

In this paper we introduce a working generalization of the theory of Gröbner bases for algebras of partial difference polynomials with constant coefficients. One obtains symbolic (formal) computation for systems of linear or non-linear partial difference equations arising, for instance, as discrete models or by the discretization of systems of differential equations. From an algebraic viewpoint, the algebras of partial difference polynomials are free objects in the category of commutative algebras endowed with the action by endomorphisms of a monoid isomorphic to ℕr. Then, the investigation of Gröbner bases in this context contributes also to the current research trend consisting in studying polynomial rings under the action of suitable symmetries that are compatible with effective methods. Since the algebras of difference polynomials are not Noetherian, we propose in this paper a theory for grading them that provides a Noetherian subalgebra filtration. This implies that the variants of Buchberger's algorithm we developed for difference ideals terminate in the finitely generated graded case when truncated up to some degree. Moreover, even in the non-graded case, we provide criterions for certifying completeness of eventually finite Gröbner bases when they are computed within sufficiently large bounded degrees. We generalize also the concepts of homogenization and saturation, and related algorithms, to the context of difference ideals. The feasibility of the proposed methods is shown by an implementation in Maple that is the first to provide computations for systems of non-linear partial difference equations. We make use of a test set based on the discretization of concrete systems of non-linear partial differential equations. [ABSTRACT FROM AUTHOR]

A spherical t-design is a set of points on the unit sphere that are nodes of a quadrature rule with positive equal weights that is exact for all spherical polynomials of degree ≤ t. The existence of a spherical t-design with (t+1)2 points in a set of interval enclosures on the unit sphere S2 ⊂ R3 for any 0 ≤ t ≤ 100 is proved by Chen, Frommer, and Lang (2011). However, how to choose a set of points from the set of interval enclosures to obtain a spherical t-design with (t + 1)2 points is not given in loc. cit. It is known that (t + 1)2 is the dimension of the space of spherical polynomials of degree at most t in 3 variables on S2. In this paper we investigate a new concept of point sets on the sphere named spherical tϵ-design (0 ≤ ϵ < 1), which are nodes of a positive, but not necessarily equal, weight quadrature rule exact for polynomials of degree ≤ t. The parameter ϵ is used to control the variation of the weights, while the sum of the weights is equal to the area of the sphere. A spherical tϵ-design is a spherical t-design when ϵ = 0, and a spherical t-design is a spherical t ϵ- design for any 0 < ϵ < 1. We show that any point set chosen from the set of interval enclosures (loc. cit.) is a spherical tϵ-design. We then study the worstcase error in a Sobolev space for quadrature rules using spherical tϵ-designs, and investigate a model of polynomial approximation with l 1-regularization using spherical tϵ-designs. Numerical results illustrate the good performance of spherical tϵ-designs for numerical integration and function approximation on the sphere. [ABSTRACT FROM AUTHOR]

In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers N. His method is based on fast polynomial arithmetic techniques and runs in time Õ(N1/4), which has been state of the art for the last forty years. In this paper, we will combine Strassen's approach with a babystep-giantstep method to improve the currently best known bound by a superpolynomial factor. The runtime complexity of our algorithm is of the form Õ(N1/4 exp(-C log N/ log logN) ) . [ABSTRACT FROM AUTHOR]

Assume that Vh is a space of piecewise polynomials of a degree less than r ⩾ 1 on a family of quasi-uniform triangulation of size h. There exists the well-known upper bound of the approximation error by Vh for a sufficiently smooth function. In this paper, we prove that, roughly speaking, if the function does not belong to Vh, the upper-bound error estimate is also sharp. This result is further extended to various situations including general shape regular grids and many different types of finite element spaces. As an application, the sharpness of finite element approximation of elliptic problems and the corresponding eigenvalue problems is established. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general framework for defining and studying essentially nonoscillatory reconstruction procedures of arbitrarily high order of accuracy, interpolating data in the central stencil around a given computational cell (CWENO). This technique relies on the same selection mechanism of smooth stencils adopted in WENO, but here the pool of candidates for the selection includes polynomials of different degrees. This seemingly minor difference allows us to compute the analytic expression of a polynomial interpolant, approximating the unknown function uniformly within a cell, instead of only at one point at a time. For this reason this technique is particularly suited for balance laws for finite volume schemes, when averages of source terms require high order quadrature rules based on several points; in the computation of local averages, during refinement in h-adaptive schemes; or in the transfer of the solution between grids in moving mesh techniques, and in general when a globally defined reconstruction is needed. Previously, these needs have been satisfied mostly by ENO reconstruction techniques, which, however, require a much wider stencil than the CWENO reconstruction studied here, for the same accuracy. [ABSTRACT FROM AUTHOR]

The dimension of planar splines on polygonal subdivisions of degree at most d is known to be a degree two polynomial for d » 0. For planar Cr splines on triangulations this formula is due to Alfeld and Schumaker; the formulas for planar splines with varying smoothness conditions across edges on convex polygonal subdvisions are due to Geramita, McDonald, and Schenck. In this paper we give a bound on how large d must be for the known polynomial formulas to give the correct dimension of the spline space. Bounds are given for central polytopal complexes in three dimensions, or polytopal cells, with varying smoothness across two-dimensional faces. In the case of tetrahedral cells with uniform smoothness r we show that the known polynomials give the correct dimension for d ≥ 3r +2; previously Hong and separately Ibrahim and Schumaker had shown that this bound holds for planar triangulations. All bounds are derived using techniques from computational commutative algebra. [ABSTRACT FROM AUTHOR]

Given a nontrivial Borel measure μ on the unit circle T, the corresponding reproducing (or Christoffel-Darboux) kernels with one of the variables fixed at z = 1 constitute a family of so-called para-orthogonal polynomials, whose zeros belong to T. With a proper normalization they satisfy a three-term recurrence relation determined by two sequences of real coefficients, {cn} and {dn}, where {dn} is additionally a positive chain sequence. Coefficients (cn, dn) provide a parametrization of a family of measures related to μ by addition of a mass point at z = 1. In this paper we estimate the location of the extreme zeros (those closest to z = 1) of the para-orthogonal polynomials from the (cn, dn)-parametrization of the measure, and use this information to establish sufficient conditions for the existence of a gap in the support of μ at z = 1. These results are easily reformulated in order to find gaps in the support of μ at any other z ∈ T. We provide also some examples showing that the bounds are tight and illustrate their computational applications. [ABSTRACT FROM AUTHOR]

In this paper we show how we can compute in a deterministic way the decomposition of a multivariate rational function with a recombination strategy. The key point of our recombination strategy is the use of Darboux polynomials. We study the complexity of this strategy and we show that this method improves the previous ones. In the appendix, we explain how the strategy proposed recently by J. Berthomieu and G. Lecerf for the sparse factorization can be used in the decomposition setting. Then we deduce a decomposition algorithm in the sparse bivariate case and we give its complexity. [ABSTRACT FROM AUTHOR]

In this concluding part of a series of papers on tetrahedral polynomial extension operators, the existence of a polynomial extension operator in the Sobolev space H(div) is proven constructively. Specifically, on any tetrahedron K, given a function w on the boundary ∂K that is a polynomial on each face, the extension operator applied to w gives a vector function whose components are polynomials of at most the same degree in the tetrahedron. The vector function is an extension in the sense that the trace of its normal component on the boundary ∂K coincides with w. Furthermore, the extension operator is continuous from H-½(∂K) into H(div,K). The main application of this result and the results of this series of papers is the existence of commuting projectors with good hp-approximation properties. [ABSTRACT FROM AUTHOR]

In this paper we study convergence of the L2-projection onto the space of polynomials up to degree p on a simplex in Rd, d ≥ 2. Optimal error estimates are established in the case of Sobolev regularity and illustrated on several numerical examples. The proof is based on the collapsed coordinate transform and the expansion into various polynomial bases involving Jacobi polynomials and their antiderivatives. The results of the present paper generalize corresponding estimates for cubes in Rd from [P. Houston, C. Schwab, E. Süli, Discontinuous hp-finite element methods for advectiondiffusion- reaction problems. SIAM J. Numer. Anal. 39 (2002), no. 6, 2133- 2163]. [ABSTRACT FROM AUTHOR]

Ariyawansa and Zhu have recently proposed a new class of optimization problems termed stochastic semidefinite programs (SSDPs). SSDPs may be viewed as an extension of two-stage stochastic (linear) programs with recourse (SLPs). Zhao has derived a decomposition algorithm for SLPs based on a logarithmic barrier and proved its polynomial complexity. Mehrotra and Özevin have extended the work of Zhao to the case of SSDPs to derive a polynomial logarithmic barrier decomposition algorithm for SSDPs. An alternative to the logarithmic barrier is the volumetric barrier of Vaidya. There is no work based on the volumetric barrier analogous to that of Zhao for SLPs or to the work of Mehrotra and Özevin for SSDPs. The purpose of this paper is to derive a class of volumetric barrier decomposition algorithms for SSDPs, and to prove polynomial complexity of certain members of the class. [ABSTRACT FROM AUTHOR]

We construct infinite families of elliptic curves with given torsion group structures over quartic number fields. In a 2006 paper, the first two authors and Park determined all of the group structures which occur infinitely often as the torsion of elliptic curves over quartic number fields. Our result presents explicit examples of their theoretical result. This paper also presents an efficient way of finding such families of elliptic curves with prescribed torsion group structures over quadratic or quartic number fields. [ABSTRACT FROM AUTHOR]

In this paper we develop and analyze some interior penalty hpdiscontinuous Galerkin (hp-DG) methods for the Helmholtz equation with first order absorbing boundary condition in two and three dimensions. The proposed hp-DG methods are defined using a sesquilinear form which is not only mesh-dependent (or h-dependent) but also degree-dependent (or p-dependent). In addition, the sesquilinear form contains penalty terms which not only penalize the jumps of the function values across the element edges but also the jumps of the first order tangential derivatives as well as jumps of all normal derivatives up to order p. Furthermore, to ensure the stability, the penalty parameters are taken as complex numbers with positive imaginary parts, so essentially and practically no constraint is imposed on the penalty parameters. It is proved that the proposed hp-discontinuous Galerkin methods are stable (hence, well-posed) without any mesh constraint. For each fixed wave number k, sub-optimal order (with respect to h and p) error estimates in the broken H1-norm and the L2-norm are derived without any mesh constraint. The error estimates as well as the stability estimates are improved to optimal order under the mesh condition k3h2p-2 ⩽ C0 by utilizing these stability and error estimates and using a stability-error iterative procedure, where C0 is some constant independent of k, h, p, and the penalty parameters. To overcome the difficulty caused by strong indefiniteness (and non-Hermitian nature) of the Helmholtz problems in the stability analysis for numerical solutions, our main ideas for stability analysis are to make use of a local version of the Rellich identity (for the Laplacian) and to mimic the stability analysis for the PDE solutions given in [19, 20, 33], which enable us to derive stability estimates and error bounds with explicit dependence on the mesh size h, the polynomial degree p, the wave number k, as well as all the penalty parameters for the numerical solutions. [ABSTRACT FROM AUTHOR]

In this paper we introduce an algorithm for computing the Stanley depth of a finitely generated multigraded module M over the polynomial ring K[X1, . . . , Xn]. As an application, we give an example of a module whose Stanley depth is strictly greater than the depth of its syzygy module. In particular, we obtain complete answers for two open questions raised by Herzog. Moreover, we show that the question whether M has Stanley depth at least r can be reduced to the question whether a certain combinatorially defined polytope P contains a Zn-lattice point. [ABSTRACT FROM AUTHOR]

Simulating wave propagation is one of the fundamental problems in scientific computing. In this paper, we consider one-dimensional two-way wave equations, and investigate a family of L2 stable high order discontinuous Galerkin methods defined through a general form of numerical fluxes. For these L2 stable methods, we systematically establish stability (hence energy conservation), error estimates (in both L2 and negative-order norms), and dispersion analysis. One novelty of this work is to identify a sub-family of the numerical fluxes, termed αβ-fluxes. Discontinuous Galerkin methods with αβ-fluxes are proven to have optimal L2 error estimates and superconvergence properties. Moreover, both the upwind and alternating fluxes belong to this sub-family. Dispersion analysis, which examines both the physical and spurious modes, provides insights into the sub-optimal accuracy of the methods using the central flux and the odd degree polynomials, and demonstrates the importance of numerical initialization for the proposed non-dissipative schemes. Numerical examples are presented to illustrate the accuracy and the long-term behavior of the methods under consideration. [ABSTRACT FROM AUTHOR]

For every modulus q ≥ 3, we define a family of subsets A of the multiplicative group (Z/q Z)× for which the Euler product ∏p+qZ∈A(1−p−s) can be computed with high numerical precision, where s >1 is some given real number. We provide a Sage script to do so, and extend our result to compute Euler products ∏p+qZ∈AF(1/ps)/H(1/ps) where F and H are polynomials with real coefficients, when this product converges absolutely. This enables us to give precise values of several Euler products occurring in number theory. [ABSTRACT FROM AUTHOR]

We study the polynomial approximation of symmetric multivariate functions and of multi-set functions. Specifically, we consider f(x_1, \dots, x_N), where x_i \in \mathbb {R}^d, and f is invariant under permutations of its N arguments. We demonstrate how these symmetries can be exploited to improve the cost versus error ratio in a polynomial approximation of the function f, and in particular study the dependence of that ratio on d, N and the polynomial degree. These results are then used to construct approximations and prove approximation rates for functions defined on multi-sets where N becomes a parameter of the input. [ABSTRACT FROM AUTHOR]

Let f_t(z)=z^2+t. For any z\in \mathbb {Q}, let S_z be the collection of t\in \mathbb {Q} such that z is preperiodic for f_t. In this article, assuming a well-known conjecture of Flynn, Poonen, and Schaefer [Duke Math. J. 90 (1997), pp. 435–463], we prove a uniform result regarding the size of S_z over z\in \mathbb {Q}. In order to prove it, we need to determine the set of rational points on a specific non-hyperelliptic curve C of genus 4 defined over \mathbb {Q}. We use Chabauty's method, which requires us to determine the Mordell-Weil rank of the Jacobian J of C. We give two proofs that the rank is 1: an analytic proof, which is conditional on the BSD rank conjecture for J and some standard conjectures on L-series, and an algebraic proof, which is unconditional, but relies on the computation of the class groups of two number fields of degree 12 and degree 24, respectively. We finally combine the information obtained from both proofs to provide a numerical verification of the strong BSD conjecture for J. [ABSTRACT FROM AUTHOR]

A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polynomial basis). For the monomial case, many studies exist on the stability of linearization-based rootfinding algorithms. By contrast, little seems to be known for other polynomial bases. This paper studies the stability of algorithms that compute the roots via linearization in nonmonomial bases, and has three goals. First we prove normwise stability when the polynomial is properly scaled and the QZ algorithm (as opposed to the more commonly used QR algorithm) is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. Second, we extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis we suggest how to choose between QR and QZ. Finally, we focus on the special case of the Chebyshev basis and finding real roots of a general function on an interval, and discuss how to compute accurate roots. The main message is that to guarantee backward stability QZ applied to a properly scaled pencil is necessary. [ABSTRACT FROM AUTHOR]

In this paper we introduce a novel approach to searching for rank- 1 lattice rules. The idea is to separate the search into two steps, first finding good generating vectors and then finding the corresponding optimal N value. For the trigonometric degree δ = 5 we establish a simple criterion on the generating vectors. By using the theory for Golomb rulers and B2-series we construct efficient algorithms for finding good generating vectors. Combined with our own home-brewed algorithm for finding the corresponding optimal N, we produce new good rank-1 lattice rules of high dimension. [ABSTRACT FROM AUTHOR]

Judicious use of interval arithmetic, combined with careful pen and paper estimates, leads to effective strategies for computer assisted analysis of nonlinear operator equations. The method of radii polynomials is an efficient tool for bounding the smallest and largest neighborhoods on which a Newton-like operator associated with a nonlinear equation is a contraction mapping. The method has been used to study solutions of ordinary, partial, and delay differential equations such as equilibria, periodic orbits, solutions of initial value problems, heteroclinic and homoclinic connecting orbits in the Ck category of functions. In the present work we adapt the method of radii polynomials to the analytic category. For ease of exposition we focus on studying periodic solutions in Cartesian products of infinite sequence spaces. We derive the radii polynomials for some specific application problems and give a number of computer assisted proofs in the analytic framework. [ABSTRACT FROM AUTHOR]

Let α be an algebraic integer of degree d, not 0 or a root of unity, all of whose conjugates αi lie in a sector ∣arg z∣ ≤ θ. In 1995, G. Rhin and C. Smyth computed the greatest lower bound c(θ) of the absolute Mahler measure (∏id=1 max(1, ∣αi∣))1/d of α, for θ belonging to nine subintervals of [0, 2π/3]. More recently, in 2004, G. Rhin and Q. Wu improved the result to thirteen subintervals of [0, π] and extended some existing subintervals. In this paper, for the first time we find a complete subinterval where c(θ) is known exactly, as well as a fourteenth subinterval. Moreover, we slightly extend further all the existing subintervals. [ABSTRACT FROM AUTHOR]

We give algorithms to compute isomorphism classes of ordinary abelian varieties defined over a finite field Fq whose characteristic polynomial (of Frobenius) is square-free and of abelian varieties defined over the prime field Fp whose characteristic polynomial is square-free and does not have real roots. In the ordinary case we are also able to compute the polarizations and the group of automorphisms (of the polarized variety) and, when the polarization is principal, the period matrix. [ABSTRACT FROM AUTHOR]

The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties. [ABSTRACT FROM AUTHOR]

Anisotropic triangulations provide efficient geometrical methods for sparse representations of bivariate functions from discrete data, in particular from image data. In previous work, we have proposed a locally adaptive method for efficient image approximation, called adaptive thinning, which relies on linear splines over anisotropic Delaunay triangulations. In this paper, we prove asymptotically optimal N-term approximation rates for linear splines over anisotropic Delaunay triangulations, where our analysis applies to relevant classes of target functions: (a) piecewise linear horizon functions across α-Hölder smooth boundaries, (b) functions of Wα,p regularity, where α > 2/p-1, (c) piecewise regular horizon functions of Wα,2 regularity, where α > 1. [ABSTRACT FROM AUTHOR]

Over the past few years considerable attention has been given to the role played by the Zernike polynomials (ZPs) in many different fields of geometrical optics, optical engineering, and astronomy. The ZPs and their applications to corneal surface modeling played a key role in this development. These polynomials are a complete set of orthogonal functions over the unit circle and are commonly used to describe balanced aberrations. In the present paper we introduce the Zernike spherical polynomials within quaternionic analysis ((R)QZSPs), which refine and extend the Zernike moments (defined through their polynomial counterparts). In particular, the underlying functions are of three real variables and take on either values in the reduced and full quaternions (identified, respectively, with ℝ3 and ℝ4). (R)QZSPs are orthonormal in the unit ball. The representation of these functions in terms of spherical monogenics over the unit sphere are explicitly given, from which several recurrence formulae for fast computer implementations can be derived. A summary of their fundamental properties and a further second order homogeneous differential equation are also discussed. As an application, we provide the reader with plot simulations that demonstrate the effectiveness of our approach. (R)QZSPs are new in literature and have some consequences that are now under investigation. [ABSTRACT FROM AUTHOR]

In the first (theoretical) part of this paper, we prove a number of constraints on hypothetical counterexamples to the Casas-Alvero conjecture, building on ideas of Graf von Bothmer, Labs, Schicho and van de Woestijne that were recently reinterpreted by Draisma and de Jong in terms of p-adic valuations. In the second (computational) part, we present ideas improving upon Diaz-Toca and Gonzalez-Vega's Gröbner basis approach to the Casas- Alvero conjecture. One application is an extension of the proof of Graf von Bothmer et al. to the cases 5pk, 6pk and 7pk (that is, for each of these cases, we determine the finite list of primes p to which their proof is not applicable). Finally, by combining both parts, we settle the Casas-Alvero conjecture in degree 12 (the smallest open case). [ABSTRACT FROM AUTHOR]

We establish how the coefficients of a sparse polynomial system influence the sum (or the trace) of its zeros. As an application, we develop numerical tests for verifying whether a set of solutions to a sparse system is complete. These algorithms extend the classical trace test in numerical algebraic geometry. Our results rely on both the analysis of the structure of sparse resultants as well as an extension of Esterov's results on monodromy groups of sparse systems. [ABSTRACT FROM AUTHOR]

Strongly stable monomial ideals are important in algebraic geometry, commutative algebra, and combinatorics. Prompted, for example, by combinatorial approaches for studying Hilbert schemes and the existence of maximal total Betti numbers among saturated ideals with a given Hilbert polynomial, in this paper we present three algorithms to produce all strongly stable ideals with certain prescribed properties: the saturated strongly stable ideals with a given Hilbert polynomial, the almost lexsegment ideals with a given Hilbert polynomial, and the saturated strongly stable ideals with a given Hilbert function. We also establish results for estimating the complexity of our algorithms. [ABSTRACT FROM AUTHOR]