Search

This paper focuses on the approximation of continuous functions on the unit sphere by spherical polynomials of degree n via hyperinterpolation. Hyperinterpolation of degree n is a discrete approximation of the L 2 -orthogonal projection of the same degree with its Fourier coefficients evaluated by a positive-weight quadrature rule that exactly integrates all spherical polynomials of degree at most 2 n. This paper aims to bypass this quadrature exactness assumption by replacing it with the Marcinkiewicz–Zygmund property proposed in a previous paper. Consequently, hyperinterpolation can be constructed by a positive-weight quadrature rule (not necessarily with quadrature exactness). This scheme is referred to as unfettered hyperinterpolation. This paper provides a reasonable error estimate for unfettered hyperinterpolation. The error estimate generally consists of two terms: a term representing the error estimate of the original hyperinterpolation of full quadrature exactness and another introduced as compensation for the loss of exactness degrees. A guide to controlling the newly introduced term in practice is provided. In particular, if the quadrature points form a quasi-Monte Carlo (QMC) design, then there is a refined error estimate. Numerical experiments verify the error estimates and the practical guide. [ABSTRACT FROM AUTHOR]

In this paper we provide a characterization of the complexity class PSPACE by using a purely continuous model defined with polynomial ordinary differential equations. [ABSTRACT FROM AUTHOR]

We improve the algorithms of Lauder-Wan [11] and Harvey [8] to compute the zeta function of a system of m polynomial equations in n variables, over the q element finite field F q , for large m. The dependence on m in the original algorithms was exponential in m. Our main result is a reduction of the dependence on m from exponential to polynomial. As an application, we speed up a doubly exponential algorithm from a recent software verification paper [3] (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective, finite field version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a polynomial system over F q when q is suitably large. [ABSTRACT FROM AUTHOR]

We establish the Central Limit Theorem, as the degree goes to infinity, for the normalized volume of the zero set of a rectangular Kostlan–Shub–Smale random polynomial system. This paper is a continuation of Central Limit Theorem for the number of real roots of Kostlan–Shub–Smale random polynomial systems by the same authors in which the case of square systems was considered. Our main tools are Kac-Rice formula and an expansion of the volume of the level set into the Itô-Wiener Chaos. [ABSTRACT FROM AUTHOR]

Results on asymptotic characteristics of classes of functions with mixed smoothness are obtained in the paper. Our main interest is in estimating the Kolmogorov widths in the uniform norm of classes with small mixed smoothness. We prove the corresponding bounds for the unit balls of the trigonometric polynomials with frequencies from a hyperbolic cross. We demonstrate how our results on the Kolmogorov widths imply new upper bounds for the optimal sampling recovery in the L 2 norm of functions with small mixed smoothness. [ABSTRACT FROM AUTHOR]

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and "sufficiently generic". Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices. [ABSTRACT FROM AUTHOR]

In this paper, we study tractability of L 2 -approximation of one-periodic functions from weighted Korobov spaces in the worst-case setting. The considered weights are of product form. For the algorithms we allow information from the class Λ all consisting of all continuous linear functionals and from the class Λ std , which only consists of function evaluations. We provide necessary and sufficient conditions on the weights of the function space for quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ , τ) -weak tractability. Together with the already known results for strong polynomial and polynomial tractability, our findings provide a complete picture of the weight conditions for all current standard notions of tractability. [ABSTRACT FROM AUTHOR]

Let Π n d denote the space of spherical polynomials of degree at most n on the unit sphere S d ⊂ R d + 1 that is equipped with the surface Lebesgue measure d σ normalized by ∫ S d d σ (x) = 1. This paper establishes a close connection between the asymptotic Nikolskii constant, L ∗ (d) ≔ lim n → ∞ 1 dim Π n d sup f ∈ Π n d ‖ f ‖ L ∞ (S d) ‖ f ‖ L 1 (S d) , and the following extremal problem: I α ≔ inf a k ‖ j α + 1 (t) − ∑ k = 1 ∞ a k j α ( q α + 1 , k t ∕ q α + 1 , 1 ) ‖ L ∞ (R +) with the infimum being taken over all sequences { a k } k = 1 ∞ ⊂ R such that the infinite series converges absolutely a.e. on R +. Here j α denotes the Bessel function of the first kind normalized so that j α (0) = 1 , and { q α + 1 , k } k = 1 ∞ denotes the strict increasing sequence of all positive zeros of j α + 1. We prove that for α ≥ − 0. 272 , I α = ∫ 0 q α + 1 , 1 j α + 1 (t) t 2 α + 1 d t ∫ 0 q α + 1 , 1 t 2 α + 1 d t = 1 F 2 (α + 1 ; α + 2 , α + 2 ; − q α + 1 , 1 2 4 ). As a result, we deduce that the constant L ∗ (d) goes to zero exponentially fast as d → ∞ : 0. 5 d ≤ L ∗ (d) ≤ (0. 857 ⋯) d (1 + ε d) with ε d = O (d − 2 ∕ 3). [ABSTRACT FROM AUTHOR]