Search

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).

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.

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.

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.

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.

Regression problems with multiple functional predictors have been studied previously. In this paper, we investigate functional quantile linear regression with multiple functional predictors within the framework of reproducing kernel Hilbert spaces. The estimation procedure is based on an l 1 -mixed-norm penalty. The learning rate of the estimator in prediction loss is established and a lower bound on the learning rate is also presented that matches the upper bound up to a logarithmic term.

An optimal convergence condition for Newton iteration is presented which is at least as weak as the one obtained by Traub and Woźniakowski leading also to an at least as precise complexity. The novelty of the paper is the introduction of a restricted convergence domain. That is we find a more precise location where the Newton iterates lie than in earlier studies. Consequently the Lipschitz constants are at least as small as the ones used before. This way and under the same computational cost, we extend the local convergence as well as the complexity of Newton iteration. Numerical examples further justify the theoretical results.

Siedlecki and Weimar (2015) defined the notion of ( s , t ) -weak tractability for linear multivariate problems, which holds if the information complexity of the multivariate problem is not exponential in d t and e − s , where d is the number of variables and e is the error threshold with positive s and t . For Hilbert spaces, they were able to characterize ( s , t ) -weak tractability in terms of how quickly the corresponding ordered singular values decay. Using this result, they studied the embedding of H r ( T d ) into L 2 ( T d ) , where T d is the d -dimensional torus, determining precisely when this problem is ( s , t ) -tractable for a given d and r . Their proof is based on deep results of Kuhn et al. (2014), which are complicated by the difficulty of ordering the singular values. In this paper, we provide a new characterization of ( s , t ) -weak tractability of multivariate problems over Hilbert spaces, which does not require us to order the singular values. This allows us to obtain a new, and somewhat simpler, proof of the Siedlecki and Weimar (2015) result that does not need to use the results of Kuhn et al. (2014).

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 ( e ) 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 e ? ( 0 , 1 ) . The growth of n X d ( e ) as a function of e - 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.

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over $\mathbb{Z}_{b}$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such \emph{folded digital nets} as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with "infinite digit expansions," which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good \emph{folded higher order polynomial lattice rules} that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.

The paper is concerned with recovery problems of linear multiplier-type operators from noisy information on weighted classes of functions. Optimal methods of recovery are constructed. The dual extremal problem is closely connected with Carlson type inequalities.

We study approximation properties of sequences of centered random elements $X_d$, $d\in\mathbb N$, with values in separable Hilbert spaces. We focus on sequences of tensor product-type and, in particular, degree-type random elements, which have covariance operators of corresponding tensor form. The average case approximation complexity $n^{X_d}(\varepsilon)$ is defined as the minimal number of continuous linear functionals that is needed to approximate $X_d$ with relative $2$-average error not exceeding a given threshold $\varepsilon\in(0,1)$. In the paper we investigate $n^{X_d}(\varepsilon)$ for arbitrary fixed $\varepsilon\in(0,1)$ and $d\to\infty$. Namely, we find criteria of (un)boundedness for $n^{X_d}(\varepsilon)$ on $d$ and of tending $n^{X_d}(\varepsilon)\to\infty$, $d\to\infty$, for any fixed $\varepsilon\in(0,1)$. In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics \begin{eqnarray*} \ln n^{X_d}(\varepsilon)= a_d+q(\varepsilon)b_d+o(b_d),\quad d\to\infty, \end{eqnarray*} at continuity points of a non-decreasing function $q\colon (0,1)\to\mathbb R$. Here $(a_d)_{d\in\mathbb N}$ is a sequence and $(b_d)_{d\in\mathbb N}$ is a positive sequence such that $b_d\to\infty$, $d\to\infty$. Under rather weak assumptions, we show that for tensor product-type random elements only special quantiles of self-decomposable or, in particular, stable (for tensor degrees) probability distributions appear as functions $q$ in the asymptotics. We apply our results to the tensor products of the Euler integrated processes with a given variation of smoothness parameters and to the tensor degrees of random elements with regularly varying eigenvalues of covariance operator., Comment: 39 pages, 0 figures

In this paper, by using the optimization idea, a new ultimate bound for the complex Lorenz system is derived. It is shown that a hyperelliptic estimate of the ultimate bound set can be analytically calculated based on the optimization method and the Lagrange multiplier method. And based on the ellipsoidal bound set and set operations, one further obtains a more conservative boundary for each variable in the complex system, which only relies on the system parameters. Afterwards, the estimated results are applied to the exponential finite-time synchronization of the complex Lorenz system. Especially, the designed control depends on the parameters of the exponential convergence rate, the finite-time convergence rate, the bound of the initial states of the master system, and the system parameter. Finally, numerical simulations are given to verify the effectiveness and correctness of the obtained results.

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. Kammerer et?al. (2013), Kammerer (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 .

The paper deals with linear problems defined on γ -weighted Hilbert spaces of functions with infinitely many variables. The spaces are endowed with zero-mean Gaussian measures which allows to define and study e -truncation and e -superposition dimensions in the average case and probabilistic settings. Roughly speaking, these e -dimensions quantify the smallest number k = k ( e ) of variables that allow to approximate the ∞ -variate functions by special ones that depend on at most k -variables with the average error bounded by e . In the probabilistic setting, given δ ∈ ( 0 , 1 ) , we want the error ≤ e with probability ≥ 1 − δ . We show that the e -dimensions are surprisingly small which, for anchored spaces, leads to very efficient algorithms, including the Multivariate Decomposition Methods.

We study EC- ( s , t ) -weak tractability of multivariate linear problems in the average case setting. This paper extends earlier work in the worst case setting. The parameters s ≥ 0 and t ≥ 0 allow us to study the information complexity n ( e , d ) of a d -variate problem with respect to different powers of ln e − 1 , corresponding to the bits of accuracy, and d . We consider the absolute and normalized error criteria. In particular, a multivariate problem is EC- ( s , t ) -weakly tractable iff lim d + e − 1 → ∞ ln n ( e , d ) ∕ [ d t + ln s e − 1 ] = 0 . We deal with general linear problems and linear tensor product problems. We show necessary and sufficient conditions for EC- ( s , t ) -weak tractability. In the case of general linear problem these conditions are matching. For linear tensor product problems, we also show matching conditions with the exception of some cases where s > 1 , in general.

It is well-known that classical integration schemes designed for regular systems of IVPs become inefficient for piecewise regular problems. To avoid a significant increase of the cost of obtaining an e -approximation for piecewise regular problems, special adaptive algorithms are usually designed. Constructing such algorithms is often based on the knowledge of a 'switching function' whose zeros define the singularity hypersurface, or it relies on certain heuristic arguments. In this paper we analyze the worst-case e -complexity of globally continuous and piecewise regular problems with unknown smooth switching function. We consider problems with right-hand side functions from the class F r , ? which consists of piecewise r -smooth functions with Holder r -th partial derivatives with the exponent ? ? ( 0 , 1 . In contrast to our previous work, we restrict ourselves to information defined only by values of the right-hand side function (computation of partial derivatives is not allowed). We design an algorithm that is based on the computation of Lagrange interpolation polynomials to locate singularity points and to approximate a function of a single variable at intermediate stages. A rigorous analysis (independent of heuristic arguments) of its error and cost is given. It turns out that both the error and the cost of the algorithm are of the same order as for regular problems. That is, no reduction of the order is observed when passing through singularities, and the cost of the algorithm remains at the same level as for regular problems. In the class F r , ? the algorithm has the worst-case error O ( m - ( r + ? ) ) (in the Chebyshev norm) and the total cost O ( m ) , where m is the number of discretization points. This leads to the conclusion that the worst-case e -complexity of the considered problem in F r , ? is ? ( e - 1 / ( r + ? ) ) , and the minimal cost is achieved by the defined algorithm that only needs function evaluations. The auxiliary algorithm that locates singularities and approximates a piecewise regular function of a single variable is also original, and it may be of interest per se.

The Dick weight is a generalization of the Hamming weight and the Niederreiter–Rosenbloom–Tsfasman (NRT) weight, defined on F p s × n . A point set with large value of minimum Dick weight gives a quadrature rule with small error in quasi-Monte Carlo integration. In this paper we explicitly construct point sets P ⊂ F p s × n with large minimum Dick weight using Niederreiter–Xing sequences and Dick’s interleaving construction. These point sets are also examples of low-WAFOM point sets.

In this paper we study the convergence of the famous Weierstrass method for simultaneous approximation of polynomial zeros over a complete normed field. We present a new semilocal convergence theorem for the Weierstrass method under a new type of initial conditions. Our result is obtained by combining ideas of Weierstrass (1891) and Proinov (2010). A priori and a posteriori error estimates are also provided under the new initial conditions.

Given a graph G=(V,E) with a cost function c:E->R^+ and a vertex subset [email protected]?V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost @?"("u","v")"@?"E"("T")c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a ([email protected]+1)-approximation algorithm for solving the problem on complete graphs, where @r is an approximation ratio for the Steiner tree problem. Currently, the best-known @r is [email protected]

Hinrichs (2009) [3] recently studied multivariate integration defined over reproducing kernel Hilbert spaces in the randomized setting and for the normalized error criterion. In particular, he showed that such problems are strongly polynomially tractable if the reproducing kernels are pointwise nonnegative and integrable. More specifically, let n^r^a^n(@e,INT"d) be the minimal number of randomized function samples that is needed to compute [email protected] for the d-variate case of multivariate integration. Hinrichs proved that n^r^a^n(@e,INT"d)@[email protected][email protected]([email protected])^[email protected]?for [email protected]@?(0,1) and [email protected]?N. In this paper we prove that the exponent 2 of @e^-^1 is sharp for tensor product Hilbert spaces whose univariate reproducing kernel is decomposable and univariate integration is not trivial for the two parts of the decomposition. More specifically we have n^r^a^n(@e,INT"d)>[email protected]?18([email protected])^[email protected]?for [email protected]@?(0,1) and d>[email protected]^-^[email protected]^-^1, where @[email protected]?[1/2,1) depends on the particular space. We stress that these estimates hold independently of the smoothness of functions in a Hilbert space. Hence, even for spaces of very smooth functions the exponent of strong polynomial tractability must be 2. Our lower bounds hold not only for multivariate integration but for all linear tensor product functionals defined over a Hilbert space with a decomposable reproducing kernel and with a non-trivial univariate functional for the two spaces corresponding to decomposable parts. We also present lower bounds for reproducing kernels that are not decomposable but have a decomposable part. However, in this case it is not clear if the lower bounds are sharp.

This paper investigates some properties of multi-scale kernels, mainly those which are related to their native spaces and make the corresponding integral operators well defined in the Lp context. In the case p=2, we derive results related to the range of the operators, alternative representations, computation of their norms, basic spectral analysis and isolated properties involving the native spaces of the kernels. Even being not compact, the integral operators possess interesting properties which are peculiar to compact operators.

A crucial point in the implementation of meshless methods such as the meshless local Petrov–Galerkin (MLPG) method is the evaluation of the domain integrals arising over circles in the discrete local weak form of the governing partial differential equation. In this paper we make a comparison between the product Gauss numerical quadrature rules, which are very popular in the MLPG literature, with cubature formulas specifically constructed for the approximation of an integral over the unit disk, but not yet applied in the MLPG method, namely the spherical, the circularly symmetrical and the symmetric cubature formulas. The same accuracy obtained with 64×64 points in the product Gauss rules may be obtained with symmetric quadrature formulas with very few points.

We want to compute a worst case @e-approximation to the solution of the Helmholtz equation [email protected]+qu=f over the unit d-cube I^d, subject to Neumann boundary conditions @?"@nu=g on @?I^d. We measure error in the H^1(I^d)-norm. Let card(@e,d) denote the minimal number of evaluations of f, g, and q needed to compute an absolute or normalized @e-approximation, assuming that f, g, and q vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if card(@e,d) grows subexponentially in @e^-^1 and d. It is said to be polynomially tractable if card(@e,d) is polynomial in @e^-^1 and d, and strongly polynomially tractable if this polynomial is independent of d. We have previously studied tractability for the homogeneous version g=0 of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general g. Using new perturbation estimates having explicit constants, we are able to relate the tractability of this problem to that of the L"2(I^d)-approximation problem. First, suppose that we use product weights, in which the role of any variable is moderated by its particular weight. We then find that if the sum of the weights is sublinearly bounded, then the problem is weakly tractable; moreover, this condition is more or less necessary. We then show that the problem is polynomially tractable if the sum of the weights is logarithmically or uniformly bounded, and we estimate the exponents of tractability for these two cases. Next, we turn to finite-order weights of fixed order @w, in which a d-variate function can be decomposed as a sum, each term depending on at most @w variables. We show that the problem is always polynomially tractable for finite-order weights, and we give estimates for the exponents of tractability. Since our results so far have established nothing stronger than polynomial tractability, we look more closely at whether strong polynomial tractability is possible. We show that our problem is never strongly polynomially tractable for the absolute error criterion. Moreover, we believe that the same is true for the normalized error criterion, but we have been able to prove this lack of strong tractability only when certain conditions hold on the weights. Finally, we use the Korobov and min kernels, along with product weights, to illustrate our results.

In this paper, we present a new technique for bounding local Rademacher averages of function classes induced by a loss function and a reproducing kernel Hilbert space (RKHS). At the heart of this technique lies the observation that certain expectations of random entropy numbers can be bounded by the eigenvalues of the integral operator associated with the RKHS. We then work out the details of the new technique by establishing two new oracle inequalities for support vector machines, which complement and generalize previous results.

It is a well-known fact that the Halton sequence exhibits poor uniformity in high dimensions. Starting with Braaten and Weller in 1979, several researchers introduced permutations to scramble the digits of the van der Corput sequences that make up the Halton sequence, in order to improve the uniformity of the Halton sequence. These sequences are called scrambled Halton, or generalized Halton sequences. Another significant result on the Halton sequence was the fact that it could be represented as the orbit of the von Neumann–Kakutani transformation, as observed by Lambert in 1982. In this paper, I will show that a scrambled Halton sequence can be represented as the orbit of an appropriately generalized von Neumann–Kakutani transformation. A practical implication of this result is that it gives a new family of randomized quasi-Monte Carlo sequences: random-start scrambled Halton sequences. This work generalizes random-start Halton sequences of Wang and Hickernell. Numerical results show that random-start scrambled Halton sequences can improve on the sample variance of random-start Halton sequences by factors as high as 7000.

Recently, a new iterative method, called Newton–Lavrentiev regularization (NLR) method, was considered by George (2006) for regularizing a nonlinear ill-posed Hammerstein-type operator equation in Hilbert spaces. In this paper we introduce a modified form of the NLR method and derive order optimal error bounds by choosing the regularization parameter according to the adaptive scheme considered by Pereverzev and Schock (2005).

In the present paper, we investigate the estimates for the covering number of a ball in a Mercer kernel Hilbert space on [0,1]. Let P"l(x) be the Legendre orthogonal polynomial of order l, a"l>0 be real numbers satisfying @?"l"="0^+^~la"l

Discretisation methods to simulate stochastic differential equations belong to the main tools in mathematical finance. For Itô processes, there exist several Euler- or Runge–Kutta-like methods which are analogues of well-known approximation schemes in the nonstochastic case. In the multidimensional case, there appear several difficulties, caused by the mixed second order derivatives. These mixed terms (or more precisely their differences) correspond to special random variables called Lévy stochastic area terms. In the present paper, we compare three approximation methods for such random variables with respect to computational complexity and the so-called effective dimension.

We study the complexity of Fredholm problems (I − Tk)u = f of the second kind on the I d = [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(I d ) with r > d/p and that k ∈ Ws,∞(I 2d ) 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 2(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/µ.

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L2-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities.

In this paper we study the convergence properties of Newton's sequence for analytic systems of equations with constant rank derivatives. Our main result is an alpha-theorem which ensures the convergence of Newton's sequence to a least-square solution of this system.

In this paper we describe an adaptive algorithm for approximating the global minimum of a continuous function on the unit interval, motivated by viewing the function as a sample path of a Wiener process. It operates by choosing the next observation point to maximize the probability that the objective function has a value at that point lower than an adaptively chosen threshold. The error converges to zero for any continuous function. Under the Wiener measure, the error converges to zero at rate e−nδn, where {δn} (a parameter of the algorithm) is a positive sequence converging to zero at an arbitrarily slow rate.

We mainly study multivariate (uniform or Gaussian) integration defined for integrand spaces Fd such as weighted Sobolev spaces of functions of d variables with smooth mixed derivatives. The weight γj moderates the behavior of functions with respect to the jth variable. For γj≡1, we obtain the classical Sobolev spaces whereas for decreasing γj's the weighted Sobolev spaces consist of functions with diminishing dependence on the jth variables. We study the minimal errors of quadratures that use n function values for the unit ball of the space Fd. It is known that if the smoothness parameter of the Sobolev space is one, then the minimal error is the same as the discrepancy. Let n(ε, Fd) be the smallest n for which we reduce the initial error, i.e., the error with n=0, by a factor ε. The main problem studied in this paper is to determine whether the problem is intractable, i.e., whether n(ε, Fd) grows faster than polynomially in ε−1 or d. In particular, we prove intractability of integration (and discrepancy) if limsupd∑dj=1γj/lnd=∞. Previously, such results were known only for restricted classes of quadratures. For γj≡1, the, following bounds hold for discrepancy •with boundary conditions1.0628d(1+o(1))⩽n(ε, Fd)⩽1.5dε−2,asd→∞,•without boundary conditions1.0463d(1+o(1))⩽n(ε, Fd)⩽1.125dε−2,asd→∞. These results are obtained by analyzing arbitrary linear tensor product functionals Id defined over weighted tensor product reproducing kernel Hilbert spaces Fd of functions of d variables. We introduce the notion of a decomposable kernel. For reproducing kernels that have a decomposable part we prove intractability of all Id with non-zero subproblems with respect to the decomposable part of the kernel, as long as the weights satisfy the condition mentioned above.

In this paper we describe a fast algorithm for counting the number of roots of complex polynomials in the open unit disk, classically called the Schur–Cohn problem. For degree d polynomials our bound is of order d log 2 d in terms of field operations and comparisons, but our approach nicely allow us to integrate the bit size as a further complexity parameter as well. For bit size σ of input polynomials of Z [ X ] our running time is of order d 2 σ ·log( dσ )·log log( dσ )·log( d ) in the multi-tape Turing machine model, thus improving all previously proposed approaches.

Secant type methods are useful for finding zeros of analytic equations that include polynomial systems. This paper proves new results concerning contraction and robustness theorems for secant maps. It is also shown that numerical path-following using secant maps has the same order of complexity that numerical path-following using Newton's map to approximate a zero. Such an algorithm was implemented and some numerical experiments are displayed.

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m , s )-nets in base b produce unbiased estimates of the integral, have a variance that tends to zero faster than 1/ n for any square integrable integrand and have a variance that for finite n is never more than e ≐2.718 times as large as the Monte Carlo variance. Lower bounds than e are known for special cases. Some very important ( t , m , s )-nets have t >0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially in s >1 dimensions. This paper shows that scrambled ( t , m , s )-nets enjoy the same properties as scrambled (0, m , s )-nets, except the sampling variance is guaranteed only to be below b t [( b +1)/( b −1)] s times the Monte Carlo variance for a least-favorable integrand and finite n .

This paper deals with the worst case setting for approximating multivariate tensor product linear operators defined over Hilbert spaces. Approximations are obtained by using a number of linear functionals from a given class of information. We consider the three classes of information: the class of all linear functionals, the Fourier class of inner products with respect to given orthonormal elements, and the standard class of function values. We wish to determine which problems are tractable and which are strongly tractable. The complete analysis is provided for approximating operators of rank two or more. The problem of approximating linear functionals is fully analyzed in the first two classes of information. For the third class of standard information we show that the possibilities are very rich. We prove that tractability of linear functionals depends on the given space of functions. For some spaces all nontrivial normed linear functionals are intractable, whereas for other spaces all linear functionals are tractable. In “typical” function spaces, some linear functionals are tractable and some others are not.

In this paper, the complexity of full solution of Fredholm integral equations of the second kind with data from the Sobolev classWr2is studied. The exact order of information complexity is derived. The lower bound is proved using a Gelfand number technique. The upper bound is shown by providing a concrete algorithm of optimal order, based on a specific hyperbolic cross approximation of the kernel function. Numerical experiments are included, comparing the optimal algorithm with the standard Galerkin method.

Let F be a class of functions defined on a d-dimensional domain. Our task is to compute Hm-norm ϵ-approximations to solutions of 2mth-order elliptic boundary-value problems Lu = f for a fixed L and for f ∈ F. We assume that the only information we can compute about f ∈ F is the value of a finite number of continuous linear functionals of f, each evaluation having cost c(d). Previous work has assumed that F was the unit ball of a Sobolev space Hr of fixed smoothness r, and it was found that the complexity of computing an ϵ-approximation was comp(ϵ, d) = Θ(c(d)(1/ϵ)d/(r+m)). Since the exponent of 1/ϵ depends on d, we see that the problem is intractable in 1/ϵ for any such F of fixed smoothness r. In this paper, we ask whether we can break intractability by letting F be the unit ball of a space of infinite smoothness. To be specific, we let F be the unit ball of a Hardy space of analytic functions defined over a complex d-dimensional ball of radius greater than one. We then show that the problem is tractable in 1/ϵ. More precisely, we prove that comp(ϵ, d) = Θ(c(d)(ln 1/ϵ)d), where the Θ-constant depends on d. Since for any p > 0, there is a function K (·) such that comp(ϵ, d) ≤ c(d) K (d)(1/ϵ)p for sufficiently small ϵ, we see that the problem is tractable, with (minimal) exponent 0. Furthermore, we show how to construct a finite element p-method (in the sense of Babuška) that can compute an ϵ-approximation with cost Θ(c(d)(ln 1/ϵ)d). Hence this finite element method is a nearly optimal complexity algorithm for d-dimensional elliptic problems with analytic data.

Classical upper bounds on global numerical errors are much too large for most ordinary differential systems of practical interest. The explanation is that perturbation bounds are generally poorly represented in estimates based on the Lipschitz constant. Consequently, complexity studies that are based on classical Lipschitz estimates are either exceedingly pessimistic or need be restricted to a small subset of problems of marginal relevance. In this paper we review the shortcomings of the classical bounds, explaining the reasons for their inadequacy. We present two modern alternative techniques, that produce much more realistic error bounds: the Alekseev-Gröbner lemma and Lipschitz algebra bounds using the Dahlquist functional. The exposition of both techniques is illustrated with examples of their implementation, and compared with the classical approach. In the concluding section we review a new and speculative approach to approximate ordinary differential systems. This method abandons all standard concepts of time-stepping, matching of terms in a Taylor expansion, etc. Instead, the solution is derived by truncating a Dirichlet expansion. It is accompanied by a useful global error bound and yields itself to easy complexity analysis.

Let O be an order of any quadratic number field. In this paper we show that under the assumption of the generalized Riemann hypothesis the following decision problems are in NP ⊃ co-NP: 1. 1. Is a given ideal A of O principal? 2. 2. Given ideals A 1 , … , Aκ of O , do their equivalence classes generate the class group of O ? 3. 3. Given ideals A 1 , … , Aκ of O , is the class group of O the direct product of the cyclic subgroups generated by the equivalence classes of the A 1 ?

n random matrix with independent Gaussian entries gij (real or complex), defined on some probability space (a, P’) and distributed according to the N(0, 1) law. In the theory of computational complexity it is of interest to consider the “random condition number” IIG;‘jl . \IGnll; in particular a question about the exact order of where 11.11 denotes the operator norm on the Euclidean space and [E the expected value, was asked in (Smale, 1985) (this quantity may be inter- preted as the average “loss of precision” when solving large systems of linear equations). It is very well known that n-“*IE((G,,(J + 2 as n -+ 03; moreover, lE/G,,ll pr~~‘~) 5 C exp(-cp*n), P((lG,(j < an”*) 5 (cay2 etc. Consequently, as far as the condition numbers are concerned, esskntially the only unknown is the behavior of G;‘. Above and in what follows, C, c, etc., denote uniuersa/ (effectively computable) numerical constants, most notably independent of n; however, identical symbols may represent different numbers in different places. In this paper we deal with a more general setup, which covers, e.g., the case when 5P is endowed with the 1; - norm ~~~~~, (for some p E [ 1, ~1); we denote the corresponding operator norm by ll’llp+P (in fact our methods allow us to handle arbitrary norms, on both the domain and the range of G; see Remark 4.1). We then have the following

Let Pd be the set of polynomials over the complex number of degree d with all its roots in the unit ball. For f ϵ Pd, let Γf be the set of points for which Newton's method converges to a root, and let Af ≡ |Γf ∩ B2(0)|/|B2(0)|, i.e., the density of Γf in the ball of radius 2 (where || denotes Lebesgue measure on C viewed as R2). For each d we consider Ad, the worst-case density (i.e., infimum) of Af for f ϵ Pd. S. Smale (1985) conjectured that Ad > 0 for all d ⪰ 3 (it was well known that A1 = A2 = 1) In this paper we prove that 1 d cd 2 log d ⩽ A d for some constant c. In particular, Ad > 0 for all d. Remark. Our definition of Ad differs slightly from that of Smale (1985) , but the conclusions hold for Ad as defined by Smale as well.