Search

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

The extended Lüroth Theorem says that if the transcendence degree of is 1 then there exists such that is equal to . In this paper we show how to compute with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when is fixed and tends to infinity. We also give an indecomposability test based on gcd computations and Newton’s polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez–Rubio–Sevilla in 2001. [Copyright &y& Elsevier]

Computing large Riemann–Roch spaces for plane projective curves still constitutes a major algorithmic and practical challenge. Seminal applications concern the construction of arbitrarily large algebraic geometry error correcting codes over alphabets with bounded cardinality. Nowadays such codes are increasingly involved in new areas of computer science such as cryptographic protocols and "interactive oracle proofs". In this paper, we design a new probabilistic algorithm of Las Vegas type for computing Riemann–Roch spaces of smooth divisors, in characteristic zero, and with expected complexity exponent 2.373 (a feasible exponent for linear algebra) in terms of the input size. [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]

Abstract: We study the randomized solution of initial value problems for systems of ordinary differential equations Recently Heinrich and Milla (2008)  presented an order optimal randomized algorithm solving this problem for -smooth input data (i.e. : the -th derivatives of satisfy a -Hölder condition). This algorithm uses function values and values of derivatives of . In this paper we present an order optimal randomized algorithm for the class of -smooth functions that uses only values of . For this purpose we show how to obtain an order optimal randomized algorithm from an order (sub)optimal deterministic one. [Copyright &y& Elsevier]

Abstract: In this paper we study planar polynomial differential systems of this form: where and , , and. A lot of properties of planar polynomial differential systems are related to irreducible Darboux polynomials of the corresponding derivation: . Darboux polynomials are usually computed with the method of undetermined coefficients. With this method we have to solve a polynomial system. We show that this approach can give rise to the computation of an exponential number of reducible Darboux polynomials. Here we show that the Lagutinskii–Pereira algorithm computes irreducible Darboux polynomials with degree smaller than , with a polynomial number, relatively to , and , binary operations. We also give a polynomial-time method to compute, if it exists, a rational first integral with bounded degree. [Copyright &y& Elsevier]

Abstract: We study the problem, initiated by Kacewicz [Randomized and quantum algorithms yield a speed-up for initial-value problems, J. Complexity 20 (2004) 821–834; see also http://arXiv.org/abs/quant-ph/0311148], of finding randomized and quantum complexity of initial-value problems. We showed in Kacewicz (2004) that a speed-up in both settings over the worst-case deterministic complexity is possible. In the present paper we prove, by defining new algorithms, that further improvement in upper bounds on the randomized and quantum complexity can be achieved. In the Hölder class of right-hand side functions with r continuous bounded partial derivatives, with rth derivative being a Hölder function with exponent , the -complexity is shown to be in the randomized setting, and on a quantum computer (up to logarithmic factors). This is an improvement for the general problem over the results from Kacewicz (2004). The gap still remaining between upper and lower bounds on the complexity is further discussed for a special problem. We consider scalar autonomous problems, with the aim of computing the solution at the end point of the interval of integration. For this problem, we fill up the gap by establishing (essentially) matching upper and lower complexity bounds. We show that the complexity in this case is in the randomized setting, and in the quantum setting (again up to logarithmic factors). Hence, this problem is essentially as hard as the integration problem. [Copyright &y& Elsevier]

Abstract: Let V be a closed algebraic subvariety of the n-dimensional projective space over the complex or real numbers and suppose that V is non-empty and equidimensional. The classic notion of a polar variety of V associated with a given linear subvariety of the ambient space of V was generalized and motivated in Bank et al. (Kybernetika 40 (2004), to appear). As particular instances of this notion of a generalized polar variety one reobtains the classic one and an alternative type of a polar variety, called dual. As main result of the present paper we show that for a generic choice of their parameters the generalized polar varieties of V are empty or equidimensional and smooth in any regular point of V. In the case that the variety V is affine and smooth and has a complete intersection ideal of definition, we are able, for a generic parameter choice, to describe locally the generalized polar varieties of V by explicit equations. Finally, we indicate how this description may be used in order to design in the context of algorithmic elimination theory a highly efficient, probabilistic elimination procedure for the following task: In case, that the variety V is -definable and affine, having a complete intersection ideal of definition, and that the real trace of V is non-empty and smooth, find for each connected component of the real trace of V an algebraic sample point. [Copyright &y& Elsevier]

We study the complexity of Fredholm problems (I−Tk)u=f of the second kind on Id=[0,1]d, where Tk is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that f∈Wr,p(Id) with r>d/p and that k∈Ws,∞(I2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Θ(n−μ+δ), where μ=min{r/d,s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the ϵ-complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ−t, then the ϵ-complexity is roughly (1/ϵ)t+1/μ. [Copyright &y& Elsevier]