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]

Abstract In this paper, we investigate optimal linear approximations (n -approximation numbers) of the embeddings from the Sobolev spaces H r (r > 0) for various equivalent norms and the Gevrey type spaces G α , β (α , β > 0) on the sphere S d and on the ball B d , where the approximation error is measured in the L 2 -norm. We obtain preasymptotics, asymptotics, and strong equivalences of the above approximation numbers as a function in n and the dimension d. We emphasize that all equivalence constants in the above preasymptotics and asymptotics are independent of the dimension d and n. As a consequence we obtain that for the absolute error criterion the approximation problems I d : H r → L 2 are weakly tractable if and only if r > 1 , not uniformly weakly tractable, and do not suffer from the curse of dimensionality. We also prove that for any α , β > 0 , the approximation problems I d : G α , β → L 2 are uniformly weakly tractable, not polynomially tractable, and quasi-polynomially tractable if and only if α ≥ 1. [ABSTRACT FROM AUTHOR]

Abstract The paper is devoted to discretization of integral norms of functions from a given collection of finite dimensional subspaces. For natural collections of subspaces of the multivariate trigonometric polynomials we construct sets of points, which are optimally (in the sense of order) good for each subspace of a collection from the point of view of the integral norm discretization. We call such sets universal. Our construction of the universal sets is based on deep results on existence of special nets, known as (t , r , d) -nets. [ABSTRACT FROM AUTHOR]

In this paper we study tractability properties of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give exact characterizations of the weight sequences ( γ j ) j ≥ 1 such that the regular grid with different mesh-sizes achieves weak, uniform weak, quasi polynomial, polynomial or strong polynomial tractability for the γ -weighted star discrepancy. For example, a necessary and sufficient condition such that the regular grid with different mesh-sizes achieves weak tractability for the γ -weighted star discrepancy is lim j → ∞ j γ j = 0 . [ABSTRACT FROM AUTHOR]

We call shifted power a polynomial of the form ( x − a ) e . The main goal of this paper is to obtain broadly applicable criteria ensuring that the elements of a finite family F of shifted powers are linearly independent or, failing that, to give a lower bound on the dimension of the space of polynomials spanned by F . In particular, we give simple criteria ensuring that the dimension of the span of F is at least c . | F | for some absolute constant c < 1 . We also propose conjectures implying the linear independence of the elements of F . These conjectures are known to be true for the field of real numbers, but not for the field of complex numbers. The verification of these conjectures for complex polynomials directly imply new lower bounds in algebraic complexity. [ABSTRACT FROM AUTHOR]

The main result of this paper is a proof that for any integrable function f on the torus, any sequence of its orthogonal projections ( P ˜ n f ) onto periodic spline spaces with arbitrary knots Δ ˜ n and arbitrary polynomial degree converges to f almost everywhere with respect to the Lebesgue measure, provided the mesh diameter ∣ Δ ˜ n ∣ tends to zero. We also give a new and simpler proof of the fact that the operators P ˜ n are bounded on L ∞ independently of the knots Δ ˜ n . [ABSTRACT FROM AUTHOR]

Let F ( x ) : = ( f i j ( x ) ) i = 1 , … , p ; j = 1 , … , q , be a ( p × q )-real polynomial matrix and let f ( x ) be the smallest singular value function of F ( x ) . In this paper, we first give the following nonsmooth version of Łojasiewicz gradient inequality for the function f with an explicit exponent: For any x ̄ ∈ R n , there exist c > 0 and ϵ > 0 such that we have for all ‖ x − x ̄ ‖ < ϵ , inf { ‖ w ‖ : w ∈ ∂ f ( x ) } ≥ c | f ( x ) − f ( x ̄ ) | 1 − τ , where ∂ f ( x ) is the limiting subdifferential of f at x , d : = max i = 1 , … , p ; j = 1 , … , q deg f i j , ℛ ( n , d ) : = d ( 3 d − 3 ) n − 1 if d ≥ 2 and ℛ ( n , d ) : = 1 if d = 1 , and τ : = 1 ℛ ( n + p , 2 d + 2 ) . Then we establish some versions of Łojasiewicz inequality for the distance function with explicit exponents, locally and globally, for the smallest singular value function f ( x ) of the matrix F ( x ) . [ABSTRACT FROM AUTHOR]

The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. (Arora et al., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition. We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models. [ABSTRACT FROM AUTHOR]

In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d . This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω ( d ) , and were obtained from arguments based on Wronskian determinants and “shifted derivatives”. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as “lacunary polynomial interpolation”). [ABSTRACT FROM AUTHOR]

In 1941, Claude Shannon introduced the General Purpose Analog Computer (GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later on electronic) machines of that time. Following Shannon’s arguments, functions generated by the GPAC must satisfy a polynomial differential algebraic equation (DAE). As it is known that some computable functions like Euler’s Γ ( x ) = ∫ 0 ∞ t x − 1 e − t d t or Riemann’s Zeta function ζ ( x ) = ∑ k = 0 ∞ 1 k x do not satisfy any polynomial DAE, this argument has often been used to demonstrate in the past that the GPAC is less powerful than digital computation. It was proved in Bournez et al. (2007), that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines. Our purpose is first to discuss the robustness of the notion of computation involved in Bournez et al. (2007), by establishing that many natural variants of the notion of computation from this paper lead to the same computability result. Second, to go from these computability results towards considerations about (time) complexity: we explore several natural variants for measuring time/space complexity of a computation. Quite surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations. Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can actually be used as a kind of programming model, and that there is a rather nice and robust notion of ordinary differential equation (ODE) programming. [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]

We study approximation properties of sequences of centered random elements X d , d ∈ N , with values in separable Hilbert spaces. We focus on sequences of tensor product-type random elements, which have covariance operators of corresponding tensor product form. The average case approximation complexity n X d ( ε ) is defined as the minimal number of evaluations of arbitrary linear functionals that is needed to approximate X d with relative 2 -average error not exceeding a given threshold ε ∈ ( 0 , 1 ) . The growth of n X d ( ε ) as a function of ε − 1 and d determines whether a sequence of corresponding approximation problems for X d , d ∈ N , is tractable or not. Different types of tractability were studied in the paper by Lifshits et al. (J. Complexity, 2012), where for each type the necessary and sufficient conditions were found in terms of the eigenvalues of the marginal covariance operators. We revise the criterion of quasi-polynomial tractability and provide a simplified version. We illustrate our result by applying it to random elements corresponding to tensor products of squared exponential kernels. We also extend a recent result of Xu (2014) concerning weighted Korobov kernels. [ABSTRACT FROM AUTHOR]

Periodic sequences over finite fields have been used as key streams in private-key cryptosystems since the 1950s. Such periodic sequences should have a series of cryptographic properties in order to resist many attack methods. The binary generalized cyclotomic periodic sequences, constructed by the cyclotomic classes over finite fields, have good pseudo-random properties and correlation properties. In this paper, the linear complexity and minimal polynomials of some generalized cyclotomic sequences over GF( q ) have been determined where q = p m and p is an odd prime. Results show that these sequences have high linear complexity over GF( q ) for a large part of odd prime power q , which means they can resist the linear attack method. [ABSTRACT FROM AUTHOR]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we present error estimates for the approximation of multivariate periodic functions in periodic Hilbert spaces of isotropic and dominating mixed smoothness by trigonometric polynomials. The approximation is based on sampling of the multivariate functions on rank-1 lattices. We use reconstructing rank-1 lattices with generating vectors of Korobov form for the sampling and generalize the technique from Temlyakov (1986), in order to show that the aliasing error of that approximation is of the same order as the error of the approximation using the partial sum of the Fourier series. The main advantage of our method is that the computation of the Fourier coefficients of such a trigonometric polynomial, which we use as approximant, is based mainly on a one-dimensional fast Fourier transform, cf. Kämmerer et al. (2013), Kämmerer (2014). This means that the arithmetic complexity of the computation depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Numerical results are presented up to dimension d = 10 . [ABSTRACT FROM AUTHOR]

In this paper we investigate multivariate integration in weighted unanchored Sobolev spaces of smoothness of arbitrarily high order. As quadrature points we employ higher order polynomial lattice point sets over F 2 which are randomly digitally shifted and then folded using the tent transformation. We first prove the existence of good higher order polynomial lattice rules which achieve the optimal rate of the mean square worst-case error, while reducing the required degree of modulus by half as compared to higher order polynomial lattice rules whose quadrature points are randomly digitally shifted but not folded using the tent transformation. Thus we are able to restrict the search space of generating vectors significantly. We then study the component-by-component construction as an explicit means of obtaining good higher order polynomial lattice rules. In a way analogous to Baldeaux et al. (2012), we show how to calculate the quality criterion efficiently and how to obtain the fast component-by-component construction using the fast Fourier transform. Our result generalizes the previous result shown by Cristea et al. (2007), in which the degree of smoothness is fixed at 2 and classical polynomial lattice rules are considered. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate the asymptotic behavior of the Gelfand, Kolmogorov and Weyl numbers of Sobolev embeddings in weighted function spaces of Besov and Triebel–Lizorkin type with polynomial weights. The exact estimates for the Gelfand and Kolmogorov numbers are obtained in the so-called non-limiting case and complement those previous results in the quasi-Banach setting. Also, the asymptotic order of the Weyl numbers is established by means of the basic Weyl estimates in the finite-dimensional spaces improved recently as well as flexible uses of the operator ideal technique. [Copyright &y& Elsevier]

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an ε -approximation for the d -variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on d and logarithmically on ε − 1. The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on d and logarithmic dependence on ε − 1 , we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential (s , t) -weak tractability with max (s , t) ≥ 1. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential (s , t) -weak tractability with max (s , t) < 1 is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019). [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]

In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time. [ABSTRACT FROM AUTHOR]

In 2008, Kedlaya and Umans designed the first multivariate multi-point evaluation algorithm over finite fields with an asymptotic complexity that can be made arbitrarily close to linear. However, it remains a major challenge to make their algorithm efficient for practical input sizes. In this paper, we revisit and improve their algorithm, while keeping this ultimate goal in mind. In addition we sharpen the known complexity bounds for modular composition of univariate polynomials over finite fields. [ABSTRACT FROM AUTHOR]