Complexity of Weighted Approximation over

We study approximation of multivariate functions defined over ^d. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms (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 L_q 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 was studied.     

Hadamard foliations of

We introduce the notion of an Hadamard foliation as a foliation of Hadamard manifold which all leaves are Hadamard.We prove that a foliation of an Hadamard manifold M of curvature −a² with a norm of the second fundamental form is Hadamard. For we construct a canonical embedding of the union of leaf boundaries into the boundary of . This embedding is continuous and it is homeomorphism on any fixed leaf boundary.Some methods of hyperbolic geometry are developed. It is shown that a ray in with the bounded by κ<1 curvature has a limit on the boundary.     

-Modules on Smooth Toric Varieties

Let X be a smooth toric variety. Cox introduced the homogeneous coordinate ring S of X and its irrelevant ideal . Let A denote the ring of differential operators on Spec(S). We show that the category of -modules on X is equivalent to a subcategory of graded A-modules modulo -torsion. Additionally, we prove that the characteristic variety of a -module is a geometric quotient of an open subset of the characteristic variety of the associated A-module and that holonomic -modules correspond to holonomic A-modules.     

On a Polynomial Inequality of Paul Erd s

Let f be a real polynomial having no zeros in the open unit disk. We prove a sharp evaluation from above for the quantity f′_∞/f_p, 0p<∞. The extremal polynomials and the exact constants are given. This extends an inequality of Paul Erd s [7].     

Shadow Codes over 4

The notion of a shadow of a self-dual binary code is generalized to self-dual codes over ₄. A Gleason formula for the symmetrized weight enumerator of the shadow of a Type I code is derived. Congruence properties of the weights follow; this yields constructions of self-dual codes of larger lengths. Weight enumerators and the highest minimum Lee, Hamming, and Euclidean weights of Type I codes of length up to 24 are studied.     

Finite Interpolation with Minimum Uniform Norm in

Given a finite sequence a{a₁, …, a_N} in a domain Ω ⁿ, and complex scalars v{v₁, …, v_N}, consider the classical extremal problem of finding the smallest uniform norm of a holomorphic function verifying f(a_j)=v_j for all j. We show that the modulus of the solutions to this problem must approach its least upper bound along a subset of the boundary of the domain large enough so that its A(Ω)-hull contains a subset of the original a large enough to force the same minimum norm. Furthermore, all the solutions must agree on a variety which contains the hull (in an appropriate, weaker, sense) of a measure supported on the maximum modulus set. An example is given to show that the inclusions can be strict.     

Polynomial Interpolation to Data on Flats in

Stimulated by recent work of Hakopian and Sahakian, polynomial interpolation to data at all the s-dimensional intersections of an arbitrary sequence of hyperplanes in ^d is considered, and reduced, by the adjunction of an additional s hyperplanes in general position with respect to the given sequence, to the case s=0 solved much earlier by two of the present authors. In particular, interpolation is from the very same polynomial spaces already used earlier. The difficult question of multiplicity and corresponding matching of derivative information is completely solved, with the number of independent derivative conditions at an intersection exactly equal to that intersection's multiplicity. Also, the consistency requirements placed on the data are minimal in the sense that they need to be checked only at the finitely many 0-dimensional intersections of the hyperplanes involved. The arguments used provide, incidentally, further insights into the two polynomial spaces, (Ξ) and (Ξ), of basic interest in box spline theory.     

The structure of -tensorial cochains of differential operators

Let M be a manifold. Let F = C^∞(M, R). Then the associative algebra of differential operators on is a two-sided -module. We prove that there is a natural isomorphism between the -tensorial Hochschild p-cochains of and the jets, taken on the diagonal, of smooth functions on the Cartesian product of p + 1 copies of M. There is an induced isomorphism of the corresponding associative differential graded algebras. The normalised -tensorial p-cochains correspond isomorphically to jets of those above functions which vanish on all the contiguous subdiagonals x_{j + 1} = X_j, j = 0,…, p − 1 of M^{(p + 1)}. This isomorphism may offer a useful alternative view of infinite-order jets of functions of several variables, taken on the diagonal as cochains of .     

Curves with Many Points and Multiplication Complexity in Any Extension of q

From the existence of algebraic function fields having some good properties, we obtain some new upper bounds on the bilinear complexity of multiplication in all extensions of the finite field _q, where q is an arbitrary prime power. So we prove that the bilinear complexity of multiplication in the finite fields _qⁿ is linear uniformly in q with respect to the degree n.     

Smoothness Theorems for Erds Weights, II

We obtain new characterizations of smoothness, saturation results, and existence theorems of derivatives for weighted polynomials associated with Erds weights on the real line. Our methods rely heavily on realization functionals.     

The set of solutions for abstract Volterra equations in

This paper studies the topological structure of the set of solutions for the equation y = Fy, where F is an abstract Volterra operator on , with an application to a nonlinear integral equation.     

An Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size

This paper shows an important exception to the common perception that three-dimensional meshes are more powerful than two-dimensional ones. Let N be the total number of processors. Then permutation routing over three-dimensional mesh computers needs Θ(N^2/3) steps while it takes Θ(N^1/2) steps over two-dimensional ones under the following conditions: (1) The path of each packet must be determined solely by its initial position and destination, i.e., the algorithm must be oblivious. (2) Each path must be “elementary,” i.e., it must be shortest and as straight as possible. Thus the conditions, under which, somewhat surprisingly, three-dimensional meshes are significantly less powerful than two-dimensional ones for the fundamental network operation, are quite reasonable in practice.     

Dense Subsets of -Solutions to Linear Elliptic Partial Differential Equations

Let Ω ^N (N2) be an unbounded domain, and L_m be a homogeneous linear elliptic partial differential operator with constant coefficients. In this paper we show, among other things, that rapidly decreasing ¹-solutions to L_m (in Ω) approximate all ¹-solutions to L_m (in Ω), provided there exist real numbers R_j→∞, 0, and a sequence {y^j} such that B(y^j, )∩Ω= and where |·| means the volume and

Full-size image

for z ^N, R>0 and D ^N. For m=2, we can replace the volume density by the capacity-density. It appears that the problem is related to the characterization of largest sets on which a nonzero polynomial solution to L_m may vanish, along with its (m−1)-derivatives. We also study a similar approximation problem for polyanalytic functions in .     

Nash's surface and the space of quantum scale

We draw some connections between Nash's theorem on imbedding of Riemannian manifolds and space and speculate on further connections to fractal spacetime and high energy physics. It is conjectured that 26 dimensions are required for imbedding a Menger sponge of arbitrary large size into an arbitrary small portion of the 26 dimensional space. We further conjecture that the 26 dimensions on their own already imply the fracticality of the surfaces imbedded into such a space and allow for a non-intuitive results similar to the Banach–Tarski decomposition theorem.     

σ-core and -core of bounded sequences

In this paper we characterize matrices that map every bounded sequence into one whose σ-core is a subset of the -core of the original sequence.     

Bounds for the Quality Parameter of Digital Shift Nets over 2

Until now, the concept of digital (t,m,s)-nets is the most powerful concept for the construction of low-discrepancy point sets in the s-dimensional unit cube. In this paper we consider a special class of digital nets over ₂, the so-called shift nets introduced by W. Ch. Schmid, and give bounds for the quality parameter t of such nets.     

Erd s–Turán Type Theorems on Quasiconformal Curves and Arcs

The theorems of Erd s and Turán mentioned in the title are concerned with the distribution of zeros of a monic polynomial with known uniform norm along the unit interval or the unit disk. Recently, Blatt and Grothmann (Const. Approx.7(1991), 19–47), Grothmann (“Interpolation Points and Zeros of Polynomials in Approximation Theory,” Habilitationsschrift, Katholische Universität Eichstätt, 1992), and Andrievskii and Blatt (J. Approx. Theory88(1977), 109–134) established corresponding results for polynomials, considered on a system of sufficiently smooth Jordan curves and arcs or piecewise smooth curves and arcs. We extend some of these results to polynomials with known uniform norm along an arbitrary quasiconformal curve or arc. As applications, estimates for the distribution of the zeros of best uniform approximants, values of orthogonal polynomials, and zeros of Bieberbach polynomials and their derivatives are obtained. We also give a negative answer to one conjecture of Eiermann and Stahl (“Zeros of orthogonal polynomials on regularN-gons,” in Lecture Notes in Math.1574(1994), 187–189).     

Boundary penalty finite element methods for blending surfaces, . Superconvergence and stability and examples

This paper is Part III of the study on blending surfaces by partial differential equations (PDEs). The blending surfaces in three dimensions (3D) are taken into account by three parametric functions, x(r,t),y(r,t) and z(r,t). The boundary penalty techniques are well suited to the complicated tangent (i.e., normal derivative) boundary conditions in engineering blending. By following the previous papers, Parts I and II in Li (J. Comput. Math. 16 (1998) 457–480; J. Comput. Appl. Math. 110 (1999) 155–176) the corresponding theoretical analysis is made to discover that when the penalty power σ=2, σ=3 (or 3.5) and 0<σ1.5 in the boundary penalty finite element methods (BP-FEMs), optimal convergence rates, superconvergence and optimal numerical stability can be achieved, respectively. Several interesting samples of 3D blending surfaces are provided, to display the remarkable advantages of the proposed approaches in this paper: unique solutions of blending surfaces, optimal blending surfaces in minimum energy, ease in handling the complicated boundary constraint conditions, and less CPU time and computer storage needed. This paper and Li (J. Comput. Math. 16 (1998) 457–480; J. Comput. Appl. Math.) provide a foundation of blending surfaces by PDE solutions, a new trend of computer geometric design.     

Approximation in Lp( ) from Spaces Spanned by the Perturbed Integer Translates of a Radial Function

The problem of approximating smooth L_p-functions from spaces spanned by the integer translates of a radially symmetric function φ is very well understood. In case the points of translation, Ξ, are scattered throughout ^d, the approximation problem is only well understood in the “stationary” setting. In this work, we provide lower bounds on the obtainable approximation orders in the “non-stationary” setting under the assumption that Ξ is a small perturbation of ^d. The functions which we can approximate belong to certain Besov spaces. Our results, which are similar in many respects to the known results for the case Ξ= ^d, apply specifically to the examples of the Gauss kernel and the generalized multiquadric.