共查询到20条相似文献,搜索用时 46 毫秒
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.
Aleksandar Ivić 《The Ramanujan Journal》2009,19(2):207-224
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/8≤U=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.
M. A. Abam M. de Berg M. Farshi J. Gudmundsson 《Discrete and Computational Geometry》2009,41(4):556-582
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,v∈P∖D is at most t times the geodesic distance between u and v in ℝ2∖D. 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.
Isabelle Chalendar Antoine Flattot Nadine Guillotin-Plantard 《Archiv der Mathematik》2008,90(4):353-359
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.
J. Casado-Díaz T. Chacón Rebollo V. Girault M. Gómez Mármol F. Murat 《Numerische Mathematik》2007,105(3):337-374
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.
T. V. Malovichko 《Ukrainian Mathematical Journal》2008,60(11):1789-1802
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.
Roberta Tognari 《Potential Analysis》2007,26(2):163-188
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 T∈S′(ℝ
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.
Saugata Basu 《Foundations of Computational Mathematics》2008,8(1):45-80
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.
Oleksandr Gomilko 《Semigroup Forum》2011,83(2):343-350
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. 相似文献
|