Search

We consider the algorithm for verified integration of piecewise analytic functions presented in Petras’ paper (Petras, 2002). The analysis of the algorithm contained in that paper is limited to a narrow class of functions and gives upper bounds only. We present an estimate of the cost (measured by the number of evaluations of the integrand) of the algorithm, both upper and lower bounds, for a wider class of functions. We show examples of functions with cost Θ ( ∣ ln ε ∣ / ε p − 1 ) , for any p > 1 , where ε is the desired accuracy of the computed integral. [ABSTRACT FROM AUTHOR]

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]

Abstract: The weighted star-discrepancy has been introduced by Sloan and Woźniakowski to reflect the fact that in multidimensional integration problems some coordinates of a function may be more important than others. It provides upper bounds for the error of multidimensional numerical integration algorithms for functions belonging to weighted function spaces of Sobolev type. In the present paper, we prove several tractability results for the weighted star-discrepancy. In particular, we obtain rather sharp sufficient conditions under which the weighted star-discrepancy is strongly tractable. The proofs are probabilistic, and use empirical process theory. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of . In particular, it also enables us to obtain the best known asymptotic bound. To this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over of a Garcia–Stichtenoth tower of algebraic function fields defined over . [Copyright &y& Elsevier]

Multivariate integration of high dimension s occurs in many applications. In many such applications, for example in finance, integrands can be well approximated by sums of functions of just a few variables. In this situation the superposition (or effective) dimension is small, and we can model the problem with finite-order weights, where the weights describe the relative importance of each distinct group of variables up to a given order (where the order is the number of variables in a group), and ignore all groups of variables of higher order.In this paper we consider multivariate integration for the anchored and unanchored (non-periodic) Sobolev spaces equipped with finite-order weights. Our main interest is tractability and strong tractability of QMC algorithms in the worst-case setting. That is, we want to find how the minimal number of function values needed to reduce the initial error by a factor ϵ depends on s and ϵ−1. If there is no dependence on s, and only polynomial dependence on ϵ−1, we have strong tractability, whereas with polynomial dependence on both s and ϵ−1 we have tractability.We show that for the anchored Sobolev space we have strong tractability for arbitrary finite-order weights, whereas for the unanchored Sobolev space we have tractability for all bounded finite-order weights. In both cases, the dependence on ϵ−1 is quadratic. We can improve the dependence on ϵ−1 at the expense of polynomial dependence on s. For finite-order weights, we may achieve almost linear dependence on ϵ−1 with a polynomial dependence on s whose degree is proportional to the order of the weights.We show that these tractability bounds can be achieved by shifted lattice rules with generators computed by the component-by-component (CBC) algorithm. The computed lattice rules depend on the weights. Similar bounds can also be achieved by well-known low discrepancy sequences such as Halton, Sobol and Niederreiter sequences which do not depend on the weights. We prove that these classical low discrepancy sequences lead to error bounds with almost linear dependence on n−1 and polynomial dependence on d. We present explicit worst-case error bounds for shifted lattice rules and for the Niederreiter sequence. Better tractability and error bounds are possible for finite-order weights, and even for general weights if they satisfy certain conditions. We present conditions on general weights that guarantee tractability and strong tractability of multivariate integration. [Copyright &y& Elsevier]