首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
We continue the study of generalized tractability initiated in our previous paper “Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information”, J. Complex. 23:262–295, 2007. We study linear tensor product problems for which we can compute linear information which is given by arbitrary continuous linear functionals. We want to approximate an operator S d given as the d-fold tensor product of a compact linear operator S 1 for d=1,2,…, with ‖S 1‖=1 and S 1 having at least two positive singular values. Let n(ε,S d ) be the minimal number of information evaluations needed to approximate S d to within ε∈[0,1]. We study generalized tractability by verifying when n(ε,S d ) can be bounded by a multiple of a power of T(ε −1,d) for all (ε −1,d)∈Ω⊆[1,∞)×ℕ. Here, T is a tractability function which is non-decreasing in both variables and grows slower than exponentially to infinity. We study the exponent of tractability which is the smallest power of T(ε −1,d) whose multiple bounds n(ε,S d ). We also study weak tractability, i.e., when . In our previous paper, we studied generalized tractability for proper subsets Ω of [1,∞)×ℕ, whereas in this paper we take the unrestricted domain Ω unr=[1,∞)×ℕ. We consider the three cases for which we have only finitely many positive singular values of S 1, or they decay exponentially or polynomially fast. Weak tractability holds for these three cases, and for all linear tensor product problems for which the singular values of S 1 decay slightly faster than logarithmically. We provide necessary and sufficient conditions on the function T such that generalized tractability holds. These conditions are obtained in terms of the singular values of S 1 and mostly asymptotic properties of T. The tractability conditions tell us how fast T must go to infinity. It is known that T must go to infinity faster than polynomially. We show that generalized tractability is obtained for T(x,y)=x 1+ln y . We also study tractability functions T of product form, T(x,y)=f 1(x)f 2(x). Assume that a i =lim inf  x→∞(ln ln f i (x))/(ln ln x) is finite for i=1,2. Then generalized tractability takes place iff
and if (a 1−1)(a 2−1)=1 then we need to assume one more condition given in the paper. If (a 1−1)(a 2−1)>1 then the exponent of tractability is zero, and if (a 1−1)(a 2−1)=1 then the exponent of tractability is finite. It is interesting to add that for T being of the product form, the tractability conditions as well as the exponent of tractability depend only on the second singular eigenvalue of S 1 and they do not depend on the rate of their decay. Finally, we compare the results obtained in this paper for the unrestricted domain Ω unr with the results from our previous paper obtained for the restricted domain Ω res=[1,∞)×{1,2,…,d *}∪[1,ε 0−1)×ℕ with d *≥1 and ε 0∈(0,1). In general, the tractability results are quite different. We may have generalized tractability for the restricted domain and no generalized tractability for the unrestricted domain which is the case, for instance, for polynomial tractability T(x,y)=xy. We may also have generalized tractability for both domains with different or with the same exponents of tractability.   相似文献   

2.
Let P be a set of n points in ℝ d . A subset of P is called a (k,ε)-kernel if for every direction, the directional width of ε-approximates that of P, when k “outliers” can be ignored in that direction. We show that a (k,ε)-kernel of P of size O(k/ε (d−1)/2) can be computed in time O(n+k 2/ε d−1). The new algorithm works by repeatedly “peeling” away (0,ε)-kernels from the point set. We also present a simple ε-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and works by repeatedly “grating” critical points into a working set, till the working set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear ε-approximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems. A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P. is supported by a NSF CAREER award CCR-0132901.  相似文献   

3.
We obtain, for T ε U=U(T)≤T 1/2−ε , asymptotic formulas for
where Δ(x) is the error term in the classical divisor problem, and E(T) is the error term in the mean square formula for . Upper bounds of the form O ε (T 1+ε U 2) for the above integrals with biquadrates instead of square are shown to hold for T 3/8U=U(T) T 1/2. The connection between the moments of E(t+U)−E(t) and is also given. Generalizations to some other number-theoretic error terms are discussed.   相似文献   

4.
We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A  -fault tolerant t-spanner is a geometric graph  on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+ε)-spanner of size for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to  , and for several special cases, we show how to obtain region-fault tolerant spanners of size without using Steiner points. We also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk D, the distance in between any two points u,vPD is at most t times the geodesic distance between u and v in ℝ2D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size  . M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation. M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.  相似文献   

5.
In this paper we study the point spectrum of the operator
where d ≥ 1, 1 ≤ p ≤ ∞([0, 1] d ) and τ is an irrational rotation on [0, 1] d . For a particular class of weights w, the point spectrum of T w is shown to be empty, generalizing Davie’s result [3], who considered the case p = 2, d = 1. Received: 1 June 2007, Revised: 16 October 2007  相似文献   

6.
In this paper we consider, in dimension d≥ 2, the standard finite elements approximation of the second order linear elliptic equation in divergence form with coefficients in L (Ω) which generalizes Laplace’s equation. We assume that the family of triangulations is regular and that it satisfies an hypothesis close to the classical hypothesis which implies the discrete maximum principle. When the right-hand side belongs to L 1(Ω), we prove that the unique solution of the discrete problem converges in (for every q with ) to the unique renormalized solution of the problem. We obtain a weaker result when the right-hand side is a bounded Radon measure. In the case where the dimension is d = 2 or d = 3 and where the coefficients are smooth, we give an error estimate in when the right-hand side belongs to L r (Ω) for some r > 1.  相似文献   

7.
We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c j (d)>0 and at most as n grows. We show that c 1(d)≥1−(d−1)−1 and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.  相似文献   

8.
We consider the solution x ε of the equation
where W is a Wiener sheet on . In the case where φε 2 converges to pδ(⋅ −a 1) + qδ(⋅ −a 2), i.e., the limit function describing the influence of a random medium is singular at more than one point, we establish the weak convergence of (x ε (u 1,⋅), …, x ε (u d , ⋅)) as ε → 0+ to (X(u 1,⋅), …, X(u d , ⋅)), where X is the Arratia flow. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 11, pp. 1529–1538, November, 2008.  相似文献   

9.
We consider the operator in L 2(B, ν) and in L 1(B, ν) with Neumann boundary condition, where U is an unbounded function belonging to for some q ∈(1, ∞), B is the possibly unbounded convex open set in where U is finite and ν(dx) = C exp (−2U (x))dx is a probability measure, infinitesimally invariant for N 0. We prove that the closure of N 0 is a m-dissipative operator both in L 2(B, ν) and in L 1(B, ν). Moreover we study the properties of ergodicity and strong mixing of the measure ν in the L 2 case.   相似文献   

10.
If 0 < p < ∞ and α > − 1, the space consists of those functions f which are analytic in the unit disc and have the property that f ′ belongs to the weighted Bergman space Aαp. In 1999, Z. Wu obtained a characterization of the Carleson measures for the spaces for certain values of p and α. In particular, he proved that, for 0 < p ≤ 2, the Carleson measures for the space are precisely the classical Carleson measures. Wu also conjectured that this result remains true for 2 < p < ∞. In this paper we prove that this conjecture is false. Indeed, we prove that if 2 < p < ∞, then there exists g analytic in such that the measure μg,p on defined by dμg,p (z) = (1 − |z|2)p - 1| g ′ (z)|p dx dy is not a Carleson measure for but is a classical Carleson measure. We obtain also some sufficient conditions for multipliers of the spaces   相似文献   

11.
In this paper we study some optimization problems for nonlinear elastic membranes. More precisely, we consider the problem of optimizing the cost functional over some admissible class of loads f where u is the (unique) solution to the problem −Δ p u+|u| p−2 u=0 in Ω with | u| p−2 u ν =f on Ω. Supported by Universidad de Buenos Aires under grant X078, by ANPCyT PICT No. 2006-290 and CONICET (Argentina) PIP 5478/1438. J. Fernández Bonder is a member of CONICET. Leandro M. Del Pezzo is a fellow of CONICET.  相似文献   

12.
We prove real Paley-Wiener type theorems for the Dunkl transform ℱ D on the space of tempered distributions. Let TS′(ℝ d ) and Δ κ the Dunkl Laplacian operator. First, we establish that the support of ℱ D (T) is included in the Euclidean ball , M>0, if and only if for all R>M we have lim  n→+∞ R −2n Δ κ n T=0 in S′(ℝ d ). Second, we prove that the support of ℱ D (T) is included in ℝ d ∖B(0,M), M>0, if and only if for all R<M, we have lim  n→+∞ R 2n  ℱ D −1(‖y−2n D (T))=0 in S′(ℝ d ). Finally, we study real Paley-Wiener theorems associated with -slowly increasing function.   相似文献   

13.
For any >0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P 1≤0,…,P s ≤0, where each P i R[X 1,…,X k ] has degree≤2, and computes the top Betti numbers of S, b k−1(S),…,b k (S), in polynomial time. The complexity of the algorithm, stated more precisely, is . For fixed , the complexity of the algorithm can be expressed as , which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing nontrivial topological invariants of semialgebraic sets in R k defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed s, we obtain, by letting =k, an algorithm for computing all the Betti numbers of S whose complexity is . An erratum to this article can be found at  相似文献   

14.
Summary  We consider the numerical treatment of second kind integral equations on the real line of the form
(abbreviatedφ =ψ +K z φ) in whichκ εL 1(ℝ),z εL (ℝ), andψ εBC(ℝ), the space of bounded continuous functions on ℝ, are assumed known andφ εBC(ℝ) is to be determined. We first derive sharp error estimates for the finite section approximation (reducing the range of integration to [−A, A]) via bounds on (I − K z )−1 as an operator on spaces of weighted continuous functions. Numerical solution by a simple discrete collocation method on a uniform grid on ℝ is then analysed: in the case whenz is compactly supported this leads to a coefficient matrix which allows a rapid matrix-vector multiply via the FFT. To utilise this possibility we propose a modified two-grid iteration, a feature of which is that the coarse grid matrix is approximated by a banded matrix, and analyse convergence and computational cost. In cases wherez is not compactly supported a combined finite section and two-grid algorithm can be applied and we extend the analysis to this case. As an application we consider acoustic scattering in the half-plane with a Robin or impedance boundary condition which we formulate as a boundary integral equation of the class studied. Our final result is that ifz (related to the boundary impedance in the application) takes values in an appropriate compact subsetQ of the complex plane, then the difference betweenφ(s) and its finite section approximation computed numerically using the iterative scheme proposed is ≤C 1[khlog(1/kh)+(1−θ)−1/2(kA)−1/2] in the interval [−θA, θA] (θ<1), forkh sufficiently small, wherek is the wavenumber andh the grid spacing. Moreover this numerical approximation can be computed in ≤C 2 N logN operations, whereN = 2A/h is the number of degrees of freedom. The values of the constantsC 1 andC 2 depend only on the setQ and not on the wavenumberk or the support ofz. This work was supported by the UK Engineering and Physical Sciences Research Council and by the Radio Communications Research Unit, Rutherford Appleton Laboratory.  相似文献   

15.
In this paper, we have analyzed a one parameter family of hp-discontinuous Galerkin methods for strongly nonlinear elliptic boundary value problems with Dirichlet boundary conditions. These methods depend on the values of the parameter , where θ = + 1 corresponds to the nonsymmetric and θ = −1 corresponds to the symmetric interior penalty methods when and f(u,∇u) = −f, that is, for the Poisson problem. The error estimate in the broken H 1 norm, which is optimal in h (mesh size) and suboptimal in p (degree of approximation) is derived using piecewise polynomials of degree p ≥ 2, when the solution . In the case of linear elliptic problems also, this estimate is optimal in h and suboptimal in p. Further, optimal error estimate in the L 2 norm when θ = −1 is derived. Numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.  相似文献   

16.
We consider the Poisson equation −Δu=f with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain Ω with cracks. Multigrid methods for the computation of singular solutions and stress intensity factors using piecewise linear functions are analyzed. The convergence rate for the stress intensity factors is whenfεL 2(Ω) and whenfεH 1(Ω). The convergence rate in the energy norm is in the first case and in the second case. The costs of these multigrid methods are proportional to the number of elements in the triangulation. The general case wherefεH m (Ω) is also discussed. The work of the first author was partially supported by NSF under grant DMS-96-00133  相似文献   

17.
We prove that the ground-state eigenfunction for symmetric stable processes of order α∈(0,2) killed upon leaving the interval (?1,1) is concave on $(-\frac{1}{2},\frac{1}{2})We prove that the ground-state eigenfunction for symmetric stable processes of order α∈(0,2) killed upon leaving the interval (−1,1) is concave on . We call this property “mid-concavity”. A similar statement holds for rectangles in ℝd, d>1. These result follow from similar results for finite-dimensional distributions of Brownian motion and subordination. Mathematics Subject Classification (2000) 30C45. Rodrigo Ba?uelos: R. Ba?uelos was supported in part by NSF grant # 9700585-DMS. Tadeusz Kulczycki: T. Kulczycki was supported by KBN grant 2 P03A 041 22 and RTN Harmonic Analysis and Related Problems, contract HPRN-CT-2001-00273-HARP.  相似文献   

18.
Optimal upper bounds are given for the norm of the semigroup (e tV ) t≥0, where V is the classical Volterra operator acting on L p [0,1], 1≤p≤∞. In particular, for every p∈[1,∞] we prove that
$\mathop{\overline{\lim}}_{t\to+\infty}\,\left(t^{-|1/4-1/(2p)|}\|e^{-tV}\|_{L_p}\right)>0.$\mathop{\overline{\lim}}_{t\to+\infty}\,\left(t^{-|1/4-1/(2p)|}\|e^{-tV}\|_{L_p}\right)>0.  相似文献   

19.
We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C 0 and ℋ is C d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.   相似文献   

20.
It has been known for a long time that the Deligne–Lusztig curves associated to the algebraic groups of type and defined over the finite field all have the maximum number of -rational points allowed by the Weil “explicit formulas”, and that these curves are -maximal curves over infinitely many algebraic extensions of . Serre showed that an -rational curve which is -covered by an -maximal curve is also -maximal. This has posed the problem of the existence of -maximal curves other than the Deligne–Lusztig curves and their -subcovers, see for instance Garcia (On curves with many rational points over finite fields. In: Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, pp. 152–163. Springer, Berlin, 2002) and Garcia and Stichtenoth (A maximal curve which is not a Galois subcover of the Hermitan curve. Bull. Braz. Math. Soc. (N.S.) 37, 139–152, 2006). In this paper, a positive answer to this problem is obtained. For every q = n 3 with n = p r  > 2, p ≥ 2 prime, we give a simple, explicit construction of an -maximal curve that is not -covered by any -maximal Deligne–Lusztig curve. Furthermore, the -automorphism group Aut has size n 3(n 3 + 1)(n 2 − 1)(n 2 − n + 1). Interestingly, has a very large -automorphism group with respect to its genus . Research supported by the Italian Ministry MURST, Strutture geometriche, combinatoria e loro applicazioni, PRIN 2006–2007.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号