349 results
Search Results
2. Bernd Carl, Aicke Hinrichs, and Philipp Rudolph share the 2014 Best Paper Award
- Author
-
Joseph F. Traub, Henryk Wozniakowski, Ian H. Sloan, Erich Novak, and Klaus Ritter
- Subjects
Statistics and Probability ,Czech ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Banach space ,language ,Art history ,Kepler ,language.human_language ,Mathematics - Abstract
The Award Committee – Peter Kritzer, Johannes Kepler University Linz, Austria and Jan Vybiral, Charles University, Czech Republic – determined that the following paper exhibits exceptional merit and therefore awarded the prize to: Bernd Carl, Aicke Hinrichs, and Philipp Rudolph for their paper ‘‘Entropy numbers of convex hulls in Banach spaces and applications’’, which appeared in October, 2014. Vol. 30, pp. 555–587. The $3000 prize will be divided between the winners. Each author will also receive a plaque.
- Published
- 2015
3. Dmitriy Bilyk, Lutz Kämmerer, Stefan Kunis, Daniel Potts, Volodya Temlyakov and Rui Yu share the 2012 Best Paper Award
- Author
-
Joseph F. Traub, Henryk Wozniakowski, Ian H. Sloan, and Erich Novak
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,Operations research ,General Mathematics ,Applied Mathematics ,Art history ,Mathematics - Published
- 2013
- Full Text
- View/download PDF
4. Thomas Müller-Gronbach, Klaus Ritter and Larisa Yaroslavtseva share the 2015 Best Paper Award
- Author
-
Erich Novak
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,biology ,Applied Mathematics ,General Mathematics ,Larisa ,biology.organism_classification ,Classics ,Mathematics - Published
- 2016
5. Aicke Hinrichs, Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich win the 2010 Best Paper Award
- Author
-
Joseph F. Traub, Henryk Wozniakowski, Erich Novak, and Ian H. Sloan
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Art history ,Mathematics - Published
- 2011
- Full Text
- View/download PDF
6. Frank Aurzada, Steffen Dereich, Michael Scheutzow, and Christian Vormoor win the 2009 best paper award
- Author
-
Ian H. Sloan, Joseph F. Traub, Henryk Wozniakowski, and Erich Novak
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Management ,Mathematics - Published
- 2010
- Full Text
- View/download PDF
7. Shu Tezuka, Joos Heintz, Bart Kuijpers, and Andrés Rojas Paredes Share the 2013 Best Paper Award
- Author
-
Ian H. Sloan, Joseph F. Traub, Henryk Wozniakowski, and Erich Novak
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Humanities ,Mathematics - Abstract
The Award Committee – Michael Gnewuch, University of Kaiserslautern, Germany and Friedrich Pillichshammer, Johannes Kepler University, Austria – determined that the following two papers exhibited exceptional merit and therefore awarded the prize to: ShuTezuka for his paper ‘‘On the discrepancy of generalizedNiederreiter sequences’’, which appeared in June–August, 2013. Vol. 29, pp. 240–247. Joos Heintz, Bart Kuijpers, and Andres Rojas Paredes for their paper ‘‘Software engineering and complexity in effective Algebraic Geometry’’, which appeared in February, 2013. Vol. 29, pp. 92–138. The $3000 prize will be divided between the winners. Each author will also receive a plaque.
- Published
- 2014
8. 2001 Best Paper Award
- Author
-
Henryk Woźniakowski, Joseph F. Traub, and Harald Niederreiter
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Mathematics education ,Mathematics - Published
- 2002
- Full Text
- View/download PDF
9. ANNOUNCEMENT: 2000 Best Paper Award
- Author
-
Joseph F. Traub, Harald Niederreiter, and Henryk Woźniakowski
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Mathematics ,Management - Published
- 2001
- Full Text
- View/download PDF
10. ANNOUNCEMENT: 1999 Best Paper Award
- Author
-
Henryk Wozniakowski, Joseph F. Traub, and Harald Niederreiter
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Mathematics ,Management - Published
- 2000
- Full Text
- View/download PDF
11. J.Dick, F. Pillichshammer, and Y.Yomdin Share the 2005 Best Paper Award
- Author
-
Joseph F. Traub, Harald Niederreiter, and Henryk Woźniakowski
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,business.industry ,Applied Mathematics ,General Mathematics ,Telecommunications ,business ,Management ,Mathematics - Published
- 2006
12. 2005 Best Paper Award Committee
- Author
-
K. Sikorski and Luis Miguel Pardo
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,GeneralLiterature_MISCELLANEOUS ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Management - Published
- 2005
13. Stefan Heinrich wins the 2004 Best Paper Award
- Author
-
Joseph F. Traub, Harald Niederreiter, and Henryk Wozniakowski
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Operations research ,Applied Mathematics ,General Mathematics ,Management ,Mathematics - Published
- 2005
14. 2002 Best Paper Award Committee
- Author
-
Fred J. Hickernell and Peter Mathé
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Management ,Mathematics - Published
- 2002
15. ANNOUNCEMENT: 2001 Best Paper Award Committee
- Author
-
Ian H. Sloan and Arthur G. Werschultz
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Management ,Mathematics - Published
- 2001
16. ANNOUNCEMENT: 2000 Best Paper Award Committee
- Author
-
Erich Novak and Vladimir Temlyakov
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,ComputingMilieux_THECOMPUTINGPROFESSION ,General Mathematics ,Applied Mathematics ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,GeneralLiterature_MISCELLANEOUS ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Management - Full Text
- View/download PDF
17. Thomas Daun, Leszek Plaskota, Greg W. Wasilkowski Win the 2011 Best Paper Award
- Author
-
Ian H. Sloan, Joseph F. Traub, Henryk Wozniakowski, and Erich Novak
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Theology ,Mathematics - Full Text
- View/download PDF
18. On the relation of the spectral test to isotropic discrepancy and L-approximation in Sobolev spaces
- Author
-
Mathias Sonnleitner and Friedrich Pillichshammer
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Isotropy ,Mathematical analysis ,Convex set ,Boundary (topology) ,010103 numerical & computational mathematics ,01 natural sciences ,Upper and lower bounds ,Spectral test ,Sobolev space ,Dimension (vector space) ,Unit cube ,0101 mathematics ,Mathematics - Abstract
This paper is a follow-up to the recent paper of Pillichshammer and Sonnleitner (2020) [12] . We show that the isotropic discrepancy of a lattice point set is at most d 2 2 ( d + 1 ) times its spectral test, thereby correcting the dependence on the dimension d and an inaccuracy in the proof of the upper bound in Theorem 2 of the mentioned paper. The major task is to bound the volume of the neighbourhood of the boundary of a convex set contained in the unit cube. Further, we characterize averages of the distance to a lattice point set in terms of the spectral test. As an application, we infer that the spectral test – and with it the isotropic discrepancy – is crucial for the suitability of the lattice point set for the approximation of Sobolev functions.
- Published
- 2021
19. How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
- Author
-
Tino Ullrich, Winfried Sickel, and Thomas Kühn
- Subjects
Statistics and Probability ,Numerical Analysis ,Pure mathematics ,Control and Optimization ,Algebra and Number Theory ,Smoothness (probability theory) ,Applied Mathematics ,General Mathematics ,Field (mathematics) ,Function (mathematics) ,Sobolev space ,Range (mathematics) ,Tensor product ,Dimension (vector space) ,Constant (mathematics) ,Mathematics - Abstract
We continue the research on the asymptotic and preasymptotic decay of singular numbers for tensor product Hilbert–Sobolev type embeddings in high dimensions with special emphasis on the influence of the underlying dimension d . The main focus in this paper lies on tensor products involving univariate Sobolev type spaces with different smoothness. We study the embeddings into L 2 and H 1 . In other words, we investigate the worst-case approximation error measured in L 2 and H 1 when only n linear measurements of the function are available. Recent progress in the field shows that accurate bounds on the singular numbers are essential for recovery bounds using only function values. The asymptotic bounds in our setting are known for a long time. In this paper we contribute the correct asymptotic constant and explicit bounds in the preasymptotic range for n . We complement and improve on several results in the literature. In addition, we refine the error bounds coming from the setting where the smoothness vector is moderately increasing, which has been already studied by Papageorgiou and Woźniakowski.
- Published
- 2021
20. Weyl and Bernstein numbers of embeddings of Sobolev spaces with dominating mixed smoothness
- Author
-
Van Kien Nguyen
- Subjects
Statistics and Probability ,Mathematics::Functional Analysis ,Numerical Analysis ,Pure mathematics ,Control and Optimization ,Algebra and Number Theory ,Smoothness (probability theory) ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Functional Analysis (math.FA) ,Mathematics - Functional Analysis ,Sobolev space ,Continuation ,FOS: Mathematics ,0101 mathematics ,Mathematics::Representation Theory ,Lp space ,Mathematics - Abstract
This paper is a continuation of the papers [21] and [22]. Here we shall investigate the asymptotic behaviour of Weyl and Bernstein numbers of embeddings of Sobolev spaces with dominating mixed smoothness into Lebesgue spaces., 33 pages
- Published
- 2016
21. On the fixed volume discrepancy of the Fibonacci sets in the integral norms
- Author
-
Vladimir Temlyakov and Mario Ullrich
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Fibonacci number ,Logarithm ,Applied Mathematics ,General Mathematics ,Mathematical analysis ,Sense (electronics) ,Unit square ,Upper and lower bounds ,Infimum and supremum ,Numerical integration ,Statistical dispersion ,Mathematics - Abstract
This paper is devoted to the study of a discrepancy-type characteristic – the fixed volume discrepancy – of the Fibonacci point set in the unit square. It was observed recently that this new characteristic allows us to obtain optimal rate of dispersion from numerical integration results. This observation motivates us to thoroughly study this new version of discrepancy, which seems to be interesting by itself. The new ingredient of this paper is the use of the average over the shifts of hat functions instead of taking the supremum over the shifts. We show that this change in the setting results in an improvement of the upper bound for the smooth fixed volume discrepancy, similarly to the well-known results for the usual L p -discrepancy. That is, the power of the logarithm in the upper bound decreases. Interestingly, this shows that “bad boxes” for the usual discrepancy cannot be “too small”. The known results on smooth discrepancy show that the obtained bounds cannot be improved in a certain sense.
- Published
- 2020
22. Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals
- Author
-
Peter Kritzer, Henryk Woźniakowski, and Friedrich Pillichshammer
- Subjects
Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Polynomial ,Control and Optimization ,Algebra and Number Theory ,Logarithm ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Hilbert space ,010103 numerical & computational mathematics ,01 natural sciences ,Exponential polynomial ,Exponential function ,Singular value ,symbols.namesake ,Tensor product ,Bounded function ,symbols ,0101 mathematics ,Mathematics - Abstract
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 e -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 e − 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 e − 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).
- Published
- 2020
23. A note on tractability of multivariate analytic problems
- Author
-
Yongping Liu and Guiqiao Xu
- Subjects
Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Multivariate statistics ,Matching (statistics) ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Algebra ,Random variate ,Linear problem ,0101 mathematics ,Eigenvalues and eigenvectors ,Mathematics - Abstract
In this paper we study d -variate approximation for weighted Korobov spaces in the worst-case setting. The considered algorithms use finitely many evaluations of arbitrary linear functionals. We give matching necessary and sufficient conditions for some notions of tractability in terms of two weight parameters. Our result is an affirmative answer to a problem which is left open in a recent paper of Kritzer, Pillichshammer and Wo?niakowski.
- Published
- 2016
24. Stability of the elastic net estimator
- Author
-
Yi Shen, Bin Han, and Elena Braverman
- Subjects
Statistics and Probability ,Elastic net regularization ,Numerical Analysis ,Mathematical optimization ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Design matrix ,Estimator ,020206 networking & telecommunications ,02 engineering and technology ,Sparse approximation ,01 natural sciences ,Stability (probability) ,Restricted isometry property ,010104 statistics & probability ,Compressed sensing ,Lasso (statistics) ,0202 electrical engineering, electronic engineering, information engineering ,Applied mathematics ,0101 mathematics ,Mathematics - Abstract
The elastic net is a regularized least squares regression method that has been widely used in learning and variable selection. The elastic net regularization linearly combines an l 1 penalty term (like the lasso) and an l 2 penalty term (like ridge regression). The l 1 penalty term enforces sparsity of the elastic net estimator, whereas the l 2 penalty term ensures democracy among groups of correlated variables. Compressed sensing is currently an extensively studied technique for efficiently reconstructing a sparse vector from much fewer samples/observations. In this paper we study the elastic net in the setting of sparse vector recovery. For recovering sparse vectors from few observations by employing the elastic net regression, we prove in this paper that the elastic net estimator is stable provided that the underlying measurement/design matrix satisfies the commonly required restricted isometry property or the sparse approximation property. It is well known that many independent random measurement matrices satisfy the restricted isometry property while random measurement matrices generated by highly correlated Gaussian random variables satisfy the sparse approximation property. As a byproduct, we establish a uniform bound for the grouping effect of the elastic net. Some numerical experiments are provided to illustrate our theoretical results on stability and grouping effect of the elastic net estimator.
- Published
- 2016
25. Sampling discretization error of integral norms for function classes
- Author
-
Vladimir N. Temlyakov
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Discretization ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Supervised learning ,010103 numerical & computational mathematics ,Discretization error ,01 natural sciences ,Numerical integration ,Approximation error ,Norm (mathematics) ,Applied mathematics ,0101 mathematics ,Mathematics - Abstract
The new ingredient of this paper is that we consider infinitely dimensional classes of functions and instead of the relative error setting, which was used in previous papers on norm discretization, we consider the absolute error setting. We demonstrate how known results from two areas of research – supervised learning theory and numerical integration – can be used in sampling discretization of the square norm on different function classes.
- Published
- 2019
26. Fast CBC construction of randomly shifted lattice rules achievingO(n−1+δ)convergence for unbounded integrands overRsin weighted spaces with POD weights
- Author
-
Frances Y. Kuo and James A. Nichols
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Function space ,Applied Mathematics ,General Mathematics ,Cumulative distribution function ,Univariate ,Inverse ,Probability density function ,Sobolev space ,Combinatorics ,Unit cube ,Lattice (order) ,Mathematics - Abstract
This paper provides the theoretical foundation for the component-by-component (CBC) construction of randomly shifted lattice rules that are tailored to integrals over R s arising from practical applications. For an integral of the form ∫ R s f ( y ) ∏ j = 1 s ϕ ( y j ) d y with a univariate probability density ϕ , our general strategy is to first map the integral into the unit cube [ 0 , 1 ] s using the inverse of the cumulative distribution function of ϕ , and then apply quasi-Monte Carlo (QMC) methods. However, the transformed integrand in the unit cube rarely falls within the standard QMC setting of Sobolev spaces of functions with mixed first derivatives. Therefore, a non-standard function space setting for integrands over R s , previously considered by Kuo, Sloan, Wasilkowski and Waterhouse (2010), is required for the analysis. Motivated by the needs of three applications, the present paper extends the theory of the aforementioned paper in several non-trivial directions, including a new error analysis for the CBC construction of lattice rules with general non-product weights, the introduction of an unanchored variant for the setting, the use of coordinate-dependent weight functions in the norm, and the strategy for fast CBC construction with POD (“product and order dependent”) weights.
- Published
- 2014
27. Mixture discrepancy for quasi-random point sets
- Author
-
Kai-Tai Fang, Yong-Dao Zhou, and Jian-Hui Ning
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Center (group theory) ,Star (graph theory) ,Projection (linear algebra) ,Set (abstract data type) ,Discrepancy function ,Statistics ,Point (geometry) ,Hypercube ,Statistical physics ,Mathematics ,Curse of dimensionality - Abstract
There are various discrepancies that are measures of uniformity for a set of points on the unit hypercube. The discrepancies have played an important role in quasi-Monte Carlo methods. Each discrepancy has its own characteristic and some weakness. In this paper we point out some unreasonable phenomena associated with the commonly used discrepancies in the literature such as the L p -star discrepancy, the center L 2 -discrepancy (CD) and the wrap-around L 2 -discrepancy (WD). Then, a new discrepancy, called the mixture discrepancy (MD), is proposed. As shown in this paper, the mixture discrepancy is more reasonable than CD and WD for measuring the uniformity from different aspects such as the intuitive view, the uniformity of subdimension projection, the curse of dimensionality and the geometric property of the kernel function. Moreover, the relationships between MD and other design criteria such as the balance pattern and generalized wordlength pattern are also given.
- Published
- 2013
28. Adaptive parameter choice for one-sided finite difference schemes and its application in diabetes technology
- Author
-
Sergei V. Pereverzyev, Valeriya Naumova, and S. Sivananthan
- Subjects
Statistics and Probability ,Numerical Analysis ,Mathematical optimization ,Control and Optimization ,Algebra and Number Theory ,Current (mathematics) ,One-sided finite difference schemes ,Applied Mathematics ,General Mathematics ,Adaptive parameter choice ,Finite difference ,Interval (mathematics) ,Function (mathematics) ,Fixed point ,Regularization (mathematics) ,Numerical differentiation ,Quasi-optimality criterion ,Point (geometry) ,Balancing principle ,Mathematics - Abstract
In this paper we discuss the problem of approximation of the first derivative of a function at the endpoint of its definition interval. This problem is motivated by diabetes therapy management, where it is important to provide estimations of the future blood glucose trend from current and past measurements. A natural way to approach the problem is to use one-sided finite difference schemes for numerical differentiation, but, following this way, one should be aware that the values of the function to be differentiated are noisy and available only at given fixed points. Then (as we argue in the paper) the number of used point values is the only parameter to be employed for regularization of the above mentioned ill-posed problem of numerical differentiation. In this paper we present and theoretically justify an adaptive procedure for choosing such a parameter. We also demonstrate some illustrative tests, as well as the results of numerical experiments with simulated clinical data.
- Published
- 2012
29. Liberating the dimension for function approximation: Standard information
- Author
-
Grzegorz W. Wasilkowski and Henryk Woniakowski
- Subjects
Function approximation ,Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Pure mathematics ,Polynomial ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Tractability ,Complexity ,Function (mathematics) ,Constructive ,Random variate ,Dimension (vector space) ,Standard information ,Focus (optics) ,Value (mathematics) ,Mathematics - 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.
- Published
- 2011
30. On the effectiveness of a generalization of Miller’s primality theorem
- Author
-
Zhenxiang Zhang
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Primality certificate ,Solovay–Strassen primality test ,Algebra ,Combinatorics ,Miller–Rabin primality test ,Strong pseudoprime ,Primality test ,Provable prime ,Industrial-grade prime ,Mathematics ,Lucas primality test - Abstract
Berrizbeitia and Olivieri showed in a recent paper that, for any integer r, the notion of @w-prime to base a leads to a primality test for numbers n=1 mod r, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4^+^o^(^1^)). They conjectured that their test is more effective than the MPT if r is large. In this paper, we show that their conjecture is not true by showing that the Berrizbeitia-Olivieri primality test (BOPT) has no advantage over the MPT, either for proving primality of a prime under the ERH, or for detecting compositeness of a composite. In particular, we point out that the complexity of the BOPT depends not only on n but also on r and that in the worst cases (usually when n is prime) for both tests, the BOPT is in general at least twice slower than the MPT, and in some cases (usually when n is composite) the BOPT may be much slower. Moreover, the BOPT needs O(rlogn) bit memories. We also give facts and numerical examples to show that, for some composites n and for some r, the rth roots of unity @w do not exist, and thus outputs of the BOPT are ERH conditional, whereas the MPT always quickly and definitely (without ERH) detects compositeness for all odd composites.
- Published
- 2010
31. On strata of degenerate polyhedral cones, II: Relations between condition measures
- Author
-
Felipe Cucker, Javier Peña, and Dennis Cheung
- Subjects
Statistics and Probability ,Numerical Analysis ,021103 operations research ,Control and Optimization ,Algebra and Number Theory ,Condition numbers ,Applied Mathematics ,General Mathematics ,0211 other engineering and technologies ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Combinatorics ,Complementarity problems ,Linear programming ,0101 mathematics ,Mathematics - Abstract
In a paper Cheung, Cucker and Peña (in press) [5] that can be seen as the first part of this one, we extended the well-known condition numbers for polyhedral conic systems C(A) Renegar (1994, 1995) [7–9] and C(A) Cheung and Cucker (2001) [3] to versions C¯(A) and C¯(A) that are finite for all input matrices A∈Rn×m. In this paper we compare C¯(A) and C¯(A) with other condition measures for the same problem that are also always finite.
- Published
- 2010
32. Optimal approximation of elliptic problems by linear and nonlinear mappings IV: Errors in L2 and other norms
- Author
-
Stephan Dahlke, Erich Novak, and Winfried Sickel
- Subjects
Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Nonlinear system ,Control and Optimization ,Algebra and Number Theory ,Worst case error ,Wavelet ,Rate of convergence ,Applied Mathematics ,General Mathematics ,Mathematics - Abstract
We study the optimal approximation of the solution of an operator equation A(u)=f by linear and different types of nonlinear mappings. In our earlier papers we only considered the error with respect to a certain H^s-norm where s was given by the operator since we assumed that A:H"0^s(@W)->H^-^s(@W) is an isomorphism. The most typical case here is s=1. It is well known that for certain regular problems the order of convergence is improved if one takes the L"2-norm. In this paper we study error bounds with respect to such a weaker norm, i.e., we assume that H"0^s(@W) is continuously embedded into a space X and we measure the error in the norm of X. A major example is X=L"2(@W) or X=H^r(@W) with r
- Published
- 2010
33. Tensor-product approximation to operators and functions in high dimensions
- Author
-
Boris N. Khoromskij and Wolfgang Hackbusch
- Subjects
Statistics and Probability ,Numerical Analysis ,Newtonian potential ,Collocation ,Algebra and Number Theory ,Control and Optimization ,Discretization ,Basis (linear algebra) ,General Mathematics ,Applied Mathematics ,Mathematics::Numerical Analysis ,Algebra ,Tensor product ,Dimension (vector space) ,Kernel (statistics) ,Applied mathematics ,Focus (optics) ,Mathematics - Abstract
In recent papers tensor-product structured Nystrom and Galerkin-type approximations of certain multi-dimensional integral operators have been introduced and analysed. In the present paper, we focus on the analysis of the collocation-type schemes with respect to the tensor-product basis in a high spatial dimension d. Approximations up to an accuracy O(N^-^@a^/^d) are proven to have the storage complexity O(dN^1^/^dlog^qN) with q independent of d, where N is the discrete problem size. In particular, we apply the theory to a collocation discretisation of the Newton potential with the kernel 1|x-y|, x,y@?R^d, d>=3. Numerical illustrations are given in the case of d=3.
- Published
- 2007
- Full Text
- View/download PDF
34. Generalized tractability for multivariate problems Part I
- Author
-
Henryk Woźniakowski and Michael Gnewuch
- Subjects
Discrete mathematics ,Statistics and Probability ,Polynomial ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,Information-based complexity ,General Mathematics ,media_common.quotation_subject ,Applied Mathematics ,010103 numerical & computational mathematics ,Function (mathematics) ,Space (mathematics) ,Infinity ,01 natural sciences ,010101 applied mathematics ,Combinatorics ,Set (abstract data type) ,Tensor product ,Bounded function ,0101 mathematics ,Mathematics ,media_common - Abstract
Many papers study polynomial tractability for multivariate problems. Let n(@?,d) be the minimal number of information evaluations needed to reduce the initial error by a factor of @? for a multivariate problem defined on a space of d-variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that n(@?,d) is bounded by a polynomial in @?^-^1 and d and this holds for all (@?^-^1,d)@?[1,~)xN. In this paper we study generalized tractability by verifying when n(@?,d) can be bounded by a power of T(@?^-^1,d) for all (@?^-^1,d)@[email protected], where @W can be a proper subset of [1,~)xN. Here T is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set @W=[1,~)x{1,2,...,d^*}@?[1,@?"0^-^1)xN for some d^*>=1 and @?"[email protected]?(0,1). We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on T such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does.
- Published
- 2007
- Full Text
- View/download PDF
35. Cubature formulas, discrepancy, and nonlinear approximation
- Author
-
Vladimir Temlyakov
- Subjects
Statistics and Probability ,Class (set theory) ,Approximation theory ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,Generalization ,General Mathematics ,Applied Mathematics ,010102 general mathematics ,010103 numerical & computational mathematics ,Function (mathematics) ,Mathematical proof ,01 natural sciences ,Numerical integration ,Algebra ,Bounded function ,Applied mathematics ,0101 mathematics ,Discrepancy theory ,Mathematics - Abstract
The main goal of this paper is to demonstrate connections between the following three big areas of research: the theory of cubature formulas (numerical integration), the discrepancy theory, and nonlinear approximation. In Section 1, we discuss a relation between results on cubature formulas and on discrepancy. In particular, we show how standard in the theory of cubature formulas settings can be translated into the discrepancy problem and into a natural generalization of the discrepancy problem. This leads to a concept of the r-discrepancy. In Section 2, we present results on a relation between construction of an optimal cubature formula with m knots for a given function class and best nonlinear m-term approximation of a special function determined by the function class. The nonlinear m-term approximation is taken with regard to a redundant dictionary also determined by the function class. Sections 3 and 4 contain some known results on the lower and the upper estimates of errors of optimal cubature formulas for the class of functions with bounded mixed derivative. One of the important messages (well known in approximation theory) of this paper is that the theory of discrepancy is closely connected with the theory of cubature formulas for the classes of functions with bounded mixed derivative. We have included in the paper both new results (Section 2) and known results. We included some known results with their proofs for the following two reasons. First of all we want to make the paper self-contained (within reasonable limits). Secondly, we selected the proofs which demonstrate different methods and are not very much technically involved. Section 5 contains historical notes on discrepancy and cubature formulas, some further comments and remarks. Historical remarks on nonlinear approximation are included in Section 2. We want to point out that this paper is not a complete survey in any of the above-mentioned areas. We did not even try to provide a complete list of results in those areas. We rather wanted to highlight the most typical results in cubature formulas (Sections 3 and 4) and show their relation to the discrepancy theory.
- Published
- 2003
- Full Text
- View/download PDF
36. The Infinite-Dimensional Widths and Optimal Recovery of Generalized Besov Classes
- Author
-
Liu Yongping and Xu Guiqiao
- Subjects
Statistics and Probability ,Pure mathematics ,Numerical Analysis ,Polynomial splines ,Algebra and Number Theory ,Control and Optimization ,Representation theorem ,General Mathematics ,Applied Mathematics ,Mathematical analysis ,Besov space ,Extension (predicate logic) ,Mathematics - Abstract
The purpose of the present paper is to consider some weak asymptotic problems concerning the infinite-dimensional Kolmogorov widths, the infinite-dimensional linear widths, the infinite-dimensional Gel'fand widths and optimal recovery in Besov space. It is obvious to be found that the results obtained and methods used in Besov space are easily generalized, and hence in this paper these results in an extension of Besov spaces on Rd are stated and proved. Meantime, the representation theorem and approximation of these spaces by polynomial splines are discussed.
- Published
- 2002
- Full Text
- View/download PDF
37. Extra-Updates Criterion for the Limited Memory BFGS Algorithm for Large Scale Nonlinear Optimizatio
- Author
-
M. Al-Baali
- Subjects
Hessian matrix ,Statistics and Probability ,Mathematical optimization ,Control and Optimization ,Scale (ratio) ,General Mathematics ,media_common.quotation_subject ,MathematicsofComputing_NUMERICALANALYSIS ,Unconstrained optimization ,Physics::Data Analysis ,Measure (mathematics) ,large scale optimization ,quasi-Newton methods ,symbols.namesake ,limited memory BFGS method ,Quasi-Newton method ,Quality (business) ,media_common ,Mathematics ,Numerical Analysis ,Algebra and Number Theory ,Applied Mathematics ,Statistics::Computation ,Nonlinear system ,Broyden–Fletcher–Goldfarb–Shanno algorithm ,symbols - Abstract
This paper studies recent modifications of the limited memory BFGS (L-BFGS) method for solving large scale unconstrained optimization problems. Each modification technique attempts to improve the quality of the L-BFGS Hessian by employing (extra) updates in a certain sense. Because at some iterations these updates might be redundant or worsen the quality of this Hessian, this paper proposes an updates criterion to measure this quality. Hence, extra updates are employed only to improve the poor approximation of the L-BFGS Hessian. The presented numerical results illustrate the usefulness of this criterion and show that extra updates improve the performance of the L-BFGS method substantially.
- Published
- 2002
- Full Text
- View/download PDF
38. Pricing Algorithms of Multivariate Path Dependent Options
- Author
-
Yue Kuen Kwok, Hoi Ying Wong, and Ka Wo Lau
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Monte Carlo methods for option pricing ,Applied Mathematics ,Trinomial tree ,Black–Scholes model ,Binary option ,Valuation of options ,Asian option ,Binomial options pricing model ,Finite difference methods for option pricing ,Algorithm ,Mathematics - Abstract
Financial derivatives which are multivariate in nature are abundant in the financial markets. The underlying state variables may be the stock prices, interest rates, exchange rates, stochastic volatility, average of stock prices, extremum values of stock priors, etc. Option contracts whose life and payoff depend on the stochastic movement of the underlying asset prices are termed path dependent options. In this paper, we examine the pricing methods of several prototype path dependent options. These include options with sequential barriers, options with an external barrier and two-asset lookback options. The governing equations for the option prices are seen to resemble the diffusion type equations but with cross derivative terms, a feature which differs from the usual diffusion equations in engineering. Various techniques to reduce the complexity of the multivariate nature of these prototype option pricing models are discussed. It is illustrated that the dimensionality of a path dependent option model may be reduced by some ingenious choices of similarity variables. We also examine the design of pricing algorithms of these multivariate options, in particular, with regard to the treatment of discrete monitoring feature and the prescription of numerical boundary conditions. The possible generalizations of the numerical techniques presented in this paper to other models with more complicated path dependent payoff structures are also discussed.
- Published
- 2001
- Full Text
- View/download PDF
39. Complexity of Weighted Approximation over Rd
- Author
-
Henryk Woźniakowski and G. W. Wasilkowski
- Subjects
Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Weight function ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Approximation algorithm ,integration ,020206 networking & telecommunications ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Continuation ,worst case complexity ,Approximation error ,Norm (mathematics) ,weighted multivariate approximation ,0202 electrical engineering, electronic engineering, information engineering ,Worst-case complexity ,Uniform boundedness ,Partial derivative ,0101 mathematics ,Mathematics - Abstract
We study approximation of multivariate functions defined over Rd. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms U(f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted Lq norm with a weight function ρ. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error ε. We provide necessary and sufficient conditions in terms of the weight ρ and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q=1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over R was studied.
- Published
- 2001
40. Uniform Distribution, Discrepancy, and Reproducing Kernel Hilbert Spaces
- Author
-
Clemens Amstler and Peter Zinterhof
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Hilbert manifold ,Representer theorem ,Applied Mathematics ,General Mathematics ,Mathematical analysis ,Hilbert space ,abstract uniform distribution ,symbols.namesake ,reproducing kernel Hilbert spaces ,Kernel embedding of distributions ,Unit cube ,Kernel (statistics) ,discrepancy ,numerical integration ,symbols ,Reproducing kernel Hilbert space ,Mathematics ,Bergman kernel - Abstract
In this paper we define a notion of uniform distribution and discrepancy of sequences in an abstract set E through reproducing kernel Hilbert spaces of functions on E. In the case of the finite-dimensional unit cube these discrepancies are very closely related to the worst case error obtained for numerical integration of functions in a reproducing kernel Hilbert space. In the compact case we show that the discrepancy tends to zero if and only if the sequence is uniformly distributed in our sense. Next we prove an existence theorem for such uniformly distributed sequences and investigate the relation to the classical notion of uniform distribution. Some examples conclude this paper.
- Published
- 2001
41. Time-Space Tradeoffs in Algebraic Complexity Theory
- Author
-
Joos Heintz, M. Aldaz, Luis Miguel Pardo, José Luis Montaña, and Guillermo Matera
- Subjects
Statistics and Probability ,Discrete mathematics ,time-space tradeoff ,Numerical Analysis ,Polynomial ,straight-line program ,Control and Optimization ,Algebra and Number Theory ,Degree (graph theory) ,Physical constant ,Applied Mathematics ,General Mathematics ,Univariate ,Elimination theory ,pebble game ,Function (mathematics) ,Space (mathematics) ,Combinatorics ,Algebraic complexity theory ,elimination theory ,Pebble game ,Mathematics - Abstract
We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS2. We show that for "almost all" univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS2≥d8. From this we conclude that for "almost all" degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S≥cd, where c>0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree). © 2000 Academic Press. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
- Published
- 2000
42. Approximating Fixed Points of Weakly Contracting Mappings
- Author
-
K. Sikorski, Leonid Khachiyan, and Z. Huang
- Subjects
Discrete mathematics ,Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,Iterative method ,General Mathematics ,Applied Mathematics ,Dimension (graph theory) ,010103 numerical & computational mathematics ,Function (mathematics) ,Fixed point ,01 natural sciences ,Ellipsoid ,Upper and lower bounds ,010101 applied mathematics ,Combinatorics ,Approximation error ,Simple (abstract algebra) ,0101 mathematics ,Mathematics - Abstract
We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al. , J. Complexity 9 , 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute e -approximations is O( n 3 (ln(1/ e )+ln(1/(1− q ))+ln n )) in the worst case, where 0 q n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O( n (ln(1/ e )+ln(1/(1− q )))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ e )/ln(1/ q )⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O( n 2 (log(1/ e )+log(1/(1− q )))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that ‖ f ( x )− x ‖⩽ δ , with O( n ln(1/ δ )) function evaluations for every q ⩽1.
- Published
- 1999
- Full Text
- View/download PDF
43. Relaxation of Product Markov Chains on Product Spaces
- Author
-
Mathé, Peter
- Subjects
Discrete mathematics ,Statistics and Probability ,Numerical Analysis ,Markov kernel ,Markov chain mixing time ,Algebra and Number Theory ,Control and Optimization ,Markov chain ,General Mathematics ,Applied Mathematics ,Product Markov chains ,Statistics::Computation ,Absorbing Markov chain ,Mixing Time ,Markov renewal process ,60J15 ,Balance equation ,Metropolis sampler ,Examples of Markov chains ,Markov property ,Statistical physics ,Mathematics - Abstract
The purpose of the paper is studying the relaxation time of product-type Markov chains on product spaces which approach a product distribution. We determine bounds to approach stationarity for such Markov chains in terms of the mixing times of the component Markov chains. In cases where the component mixing times vary much we propose an optimized visiting scheme which makes such product-type Markov chains comparative to Gibbs-type samplers. We conclude the paper by a discussion of the relaxation of Metropolis-type samplers applied to separable energy functions.
- Published
- 1998
- Full Text
- View/download PDF
44. Lyapunov Exponents versus Expansivity and Sensitivity in Cellular Automata
- Author
-
Michele Finelli, Giovanni Manzini, and Luciano Margara
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Mathematical analysis ,Lyapunov exponent ,Space (mathematics) ,Cellular automaton ,Connection (mathematics) ,symbols.namesake ,Dimension (vector space) ,Phase space ,Elementary proof ,symbols ,Sensitivity (control systems) ,Mathematics - Abstract
We establish a connection between the theory of Lyapunov exponents and the properties of expansivity and sensitivity to initial conditions for a particular class of discrete time dynamical systems; cellular automata (CA). The main contribution of this paper is the proof that all expansive cellular automata have positive Lyapunov exponents for almost all the phase space configurations. In addition, we provide an elementary proof of the non-existence of expansive CA in any dimension greater than 1. In the second part of this paper we prove that expansivity in dimension greater than 1 can be recovered by restricting the phase space to asuitablesubset of the whole space. To this extent we describe a 2-dimensional CA which is expansive over adense uncountablesubset of the whole phase space. Finally, we highlight the different behavior of expansive and sensitive CA for what concerns the speed at which perturbations propagate.
- Published
- 1998
45. Hilbert's Nullstellensatz Is in the Polynomial Hierarchy
- Author
-
Pascal Koiran
- Subjects
Discrete mathematics ,Polynomial hierarchy ,Statistics and Probability ,Class (set theory) ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,General Mathematics ,Applied Mathematics ,Hilbert's Nullstellensatz ,System of polynomial equations ,Computer Science::Computational Complexity ,Upper and lower bounds ,Combinatorics ,Riemann hypothesis ,symbols.namesake ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Several complex variables ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,symbols ,PSPACE ,Mathematics - Abstract
We show that if the Generalized Riemann Hypothesis is true, the problem of deciding whether a system of polynomial equations in several complex variables has a solution is in the second level of the polynomial hierarchy. In fact, this problem is in AM, the ``Arthur-Merlin'''' class (recall that $\np \subseteq \am \subseteq \rp^{\tiny \np} \subseteq \Pi_2$). The best previous bound was PSPACE. An earlier version of this paper was distributed as NeuroCOLT Technical Report~96-44. The present paper includes in particular a new lower bound for unsatisfiable systems, and remarks on the Arthur-Merlin class.
- Published
- 1996
- Full Text
- View/download PDF
46. Semi-algebraic Complexity of Quotients and Sign Determination of Remainders
- Author
-
Marie-Françoise Roy and Thomas Lickteig
- Subjects
Discrete mathematics ,Statistics and Probability ,Sequence ,Numerical Analysis ,Algebra and Number Theory ,Control and Optimization ,Degree (graph theory) ,Euclidean division ,General Mathematics ,Polynomial ring ,Applied Mathematics ,Upper and lower bounds ,Prime (order theory) ,Combinatorics ,Strassen algorithm ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Sign (mathematics) ,Mathematics - Abstract
For two nonzero polynomialsformula]the successive signed Euclidean division yields algorithms, that is, semialgebraic computation trees, for tasks such as computing the sequence of successive quotients, deciding the signs of the sequence of remainders in a pointa?R, deciding the number of remainders, or deciding the degree pattern of the sequence of remainders. In this paper we show lower bounds of ordermlog2(m) for these tasks, within the computational framework of semi-algebraic computation trees. The inevitably long paths in semi-algebraic computation trees can be specified as those followed by certain prime cones in the real spectrum of a polynomial ring. We give in the paper a positive answer to the question posed in T. Lickteig (J. Pure Appl. Algebra110(2), 131?184 (1996)) whether the degree of the zero-set of the support of a prime cone provides a lower bound on the complexity of isolating the prime cone. The applications are based on the degree inequalities given by Strassen and Schuster and extend their work to the real situation in various directions.
- Published
- 1996
- Full Text
- View/download PDF
47. The Complexity of Two-Point Boundary-Value Problems with Piecewise Analytic Data
- Author
-
Arthur G. Werschulz
- Subjects
Statistics and Probability ,Unit sphere ,Numerical Analysis ,Class (set theory) ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Computer science ,Finite element method ,Sobolev space ,Combinatorics ,Bounded function ,Piecewise ,A priori and a posteriori ,Mathematics ,Analytic function - Abstract
Previous work on the ϵ-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the "-complexity is proportional to ln(ϵ-1), and there is a finite element p-method (in the sense of Babuska) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ϵ less than sqroot(2). If we know only that there are b equal or greater than 2 breakpoints, but we don't know their location, then the ϵ-complexity is proportional to bϵ-1, and a finite element h-method is nearly optimal. . In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L2 sense.
- Published
- 1994
48. Variational Principles in Curve Design
- Author
-
Hans Strauss
- Subjects
Statistics and Probability ,Numerical Analysis ,Pure mathematics ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Value (computer science) ,Function (mathematics) ,Combinatorics ,Integer ,Curve design ,Hermite interpolation ,Interpolation ,Mathematics - Abstract
The paper considers Hermite interpolation for vector-valued functions. Corresponding to the interpolating functions f we define functionals I which contain function values of f ( r ) and integrals of f ( r ) where 0 ≤ r ≤ m for some integer m . The main purpose of the paper is to characterize those functions which satisfy the interpolation problem and have a minimal value of I . These characterizations contain several results of the literature including splines in tension and geometric splines.
- Published
- 1993
49. On the numerical computation of orbits of dynamical systems: The higher dimensional case
- Author
-
Kenneth J. Palmer and Shui-Nee Chow
- Subjects
Statistics and Probability ,Discrete mathematics ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Dynamical systems theory ,Applied Mathematics ,General Mathematics ,Computation ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Iterated function ,Orbit (dynamics) ,Applied mathematics ,0101 mathematics ,Finite time ,Computer Science::Databases ,Mathematics - Abstract
Chaotic dynamical systems exhibit sensitive dependence to initial conditions. So, because of round-off error, a computed orbit diverges at an exponential rate from the true orbit with the same initial condition. Nevertheless, we are able to exploit the hyperbolicity of the dynamical system to prove a “finite time” shadowing lemma, from which we deduce that a true orbit shadows the computed orbit for a large number of iterates. An algorithm for the computation of the shadowing error is given and, furthermore, the effect of round-off error on these computations is analyzed in detail. The algorithm is applied to the Hénon map. This paper is a continuation of an earlier paper on one-dimensional maps.
- Published
- 1992
50. On a posteriori upper bounds for approximating linear functionals in a probabilistic setting
- Author
-
G. W. Wasilkowski
- Subjects
Statistics and Probability ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Operator (physics) ,Linear space ,Probabilistic logic ,Space (mathematics) ,Combinatorics ,A priori and a posteriori ,Probability measure ,Mathematics ,Normed vector space - Abstract
The probabilistic setting for approximately solved problems has been studied in a number of papers; see, e.g., (Lee and Wasilkowski, 1986; Traub et al., 1988) and papers cited therein. Roughly speaking, it can be described in the following way. Suppose that we want to approximate the solutions SY-, for f E F, where S: F + G is an operator, F is a linear space, and G is a normed linear space. The elements S(j) are approximated by Ucf) E G, where Ucf) = 4(Ncf)) with information Ncf) consisting of n values of linear functionals Liv), and with an algorithm 4: N(F) + G being an arbitrary mapping. Assuming that the space F is endowed with a given probability measure /,L, the quality of U = 4 0 N is measured by the p-probability that the error [IS(j) U(‘j)ll is small. That is, for a given parameter 6 E (0, l), we seek an “optimal” algorithm U that, with probability at least 1 6, approximates Scf) to within E for as small E as possible. Equivalently: for a given 6 E (0, l), we want to find a pair (U, E) such that E is the smallest number for which p(CfE F: [IS(~) U(j)II 5 E}) 2 1 6. Since the bound E is independent off, it is an a priori bound. Since we seek the smallest E, in the probabilistic setting we actually search for U = $J 0 N that admits the sharpest a priori error bounds. In this paper, we propose a more general approach by permitting a posteriori bounds. That is, in addition to algorithms $, we let bounds Bcf
- Published
- 1992
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.