Extremal Systems of Points and Numerical Integration on the Sphere

This paper considers extremal systems of points on the unit sphere S ^r⊂R ^r+1, related problems of numerical integration and geometrical properties of extremal systems. Extremal systems are systems of d _n =dim P _n points, where P _n is the space of spherical polynomials of degree at most n, which maximize the determinant of an interpolation matrix. Extremal systems for S ² of degrees up to 191 (36,864 points) provide well distributed points, and are found to yield interpolatory cubature rules with positive weights. We consider the worst case cubature error in a certain Hilbert space and its relation to a generalized discrepancy. We also consider geometrical properties such as the minimal geodesic distance between points and the mesh norm. The known theoretical properties fall well short of those suggested by the numerical experiments.

     

Lagrange interpolation on extended generalized Jacobi nodes

We consider theL ^p -convergence of interpolatory processes for nonsmooth functions. Therefore we use generalizations of the well-known Marcinkiewicz-Zygmund inequality for trigonometric polynomials to the case of algebraic polynomials, extending a result of Y. Xu. Particularly, we obtain the order of convergence for certain Lagrange and quasi-Lagrange interpolatory processes on generalized Jacobi nodes. Our approach enables us also to discuss the influence of additional nodes near the endpoints ±1.     

Best m-ter m approxi mation of the classes$$ B_{\infty, \theta }^r $$ of functions of many variables by polyno mials in the haar syste m

We obtain an exact-order estimate for the best m-term approximation of the classes B_{￥, q}^r B_{\infty, \theta }^r of periodic functions of many variables by polynomials in the Haar system in the metric of the space L _q , 1 < q < ∞.     

On Some Extremal Properties of Lagrange Interpolatory Polynomials

In this paper, we will show that Lagrange interpolatory polynomials are optimal for solving some approximation theory problems concerning the finding of linear widths.In particular, we will show that

Full-size image

, where _n is a set of the linear operators with finite rank n+1 defined on −1,1], and where _n+1 denotes the set of polynomials p=∑_i=0ⁿ⁺¹a_ixⁱ of degreen+1 such that a_n+11. The infimum is achieved for Lagrange interpolatory polynomial for nodes .     

Sobolev estimates for constructive uniform-grid FFT interpolatory approximations of spherical functions

The fast Fourier transform (FFT) based matrix-free ansatz interpolatory approximations of periodic functions are fundamental for efficient realization in several applications. In this work we design, analyze, and implement similar constructive interpolatory approximations of spherical functions, using samples of the unknown functions at the poles and at the uniform spherical-polar grid locations \(\left (\frac {j\pi }{N}, \frac {k \pi }{N}\right )\), for j=1,…,N?1, k=0,…,2N?1. The spherical matrix-free interpolation operator range space consists of a selective subspace of two dimensional trigonometric polynomials which are rich enough to contain all spherical polynomials of degree less than N. Using the \({\mathcal {O}}(N^{2})\) data, the spherical interpolatory approximation is efficiently constructed by applying the FFT techniques (in both azimuthal and latitudinal variables) with only \({\mathcal {O}}(N^{2} \log N)\) complexity. We describe the construction details using the FFT operators and provide complete convergence analysis of the interpolatory approximation in the Sobolev space framework that are well suited for quantification of various computer models. We prove that the rate of spectrally accurate convergence of the interpolatory approximations in Sobolev norms (of order zero and one) are similar (up to a log term) to that of the best approximation in the finite dimensional ansatz space. Efficient interpolatory quadratures on the sphere are important for several applications including radiation transport and wave propagation computer models. We use our matrix-free interpolatory approximations to construct robust FFT-based quadrature rules for a wide class of non-, mildly-, and strongly-oscillatory integrands on the sphere. We provide numerical experiments to demonstrate fast evaluation of the algorithm and various theoretical results presented in the article.     

Convergence of Derivatives of Optimal Nodal Splines

Optimal nodal spline interpolantsWfof ordermwhich have local support can be used to interpolate a continuous functionfat a set of mesh points. These splines belong to a spline space with simple knots at the mesh points as well as atm−2 arbitrary points between any two mesh points and they reproduce polynomials of orderm. It has been shown that, for a sequence of locally uniform meshes, these splines converge uniformly for anyfCas the mesh norm tends to zero. In this paper, we derive a set of sufficient conditions on the sequence of meshes for the uniform convergence ofD^jWftoD^jfforfC^sandj=1, …, s<m. In addition we give a bound forD^rWfwiths<r<m. Finally, we use optimal nodal spline interpolants for the numerical evaluation of Cauchy principal value integrals.     

On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

THE DIMENSION OF A CLASS OF BIVARIATE SPLINE SPACES

ＴＨＥＤＩＭＥＮＳＩＯＮＯＦＡＣＬＡＳＳＯＦＢＩＶＡＲＩＡＴＥＳＰＬＩＮＥＳＰＡＣＥＳ￥ＧＡＯＪＵＮＢＩＮＡｂｓｔｒａｃｔ：ＷｅｅｓｔａｂｌｉｓｈｔｈｅｄｉｍｅｎｓｉｏｎｆｏｒｍｕｌａｏｆｔｈｅｓｐａｃｅｏｆＣｒｂｉｖａｒｉａｔｅｐｉｅｃｅｗｉｓｅｐ...     

Exponentials Reproducing Subdivision Schemes

This paper is concerned with a family of nonstationary, interpolatory subdivision schemes that have the capability of reproducing functions in a finite-dimensional subspace of exponential polynomials. We give conditions for the existence and uniqueness of such schemes, and analyze their convergence and smoothness. It is shown that the refinement rules of an even-order exponentials reproducing scheme converge to the Dubuc—Deslauriers interpolatory scheme of the same order, and that both schemes have the same smoothness. Unlike the stationary case, the application of a nonstationary scheme requires the computation of a different rule for each refinement level. We show that the rules of an exponentials reproducing scheme can be efficiently derived by means of an auxiliary orthogonal scheme , using only linear operations. The orthogonal schemes are also very useful tools in fitting an appropriate space of exponential polynomials to a given data sequence.     

The algebraic theory approach for ordinary differential equations: Highly accurate finite differences

This article reports further developments of Herrera's algebraic theory approach to the numerical treatment of differential equations. A new solution procedure for ordinary differential equations is presented. Finite difference algorithms of 0(h^r), for arbitrary “r” are developed. The method consists in constructing local approximate solutions and using them to extract information about the sought solution. Only nodal information is derived. The local approximate solutions are constructed by collocation, using polynomials of degree G. When “n” collocation points are used at each subinterval, G = n + 1and the order of accuracy is 0(h^2n?1). The procedure here presented is very easy to implement. A program in which n can be chosen arbitrarily, was constructed and applied to selected examples.     

How good can polynomial interpolation on the sphere be?

This paper explores the quality of polynomial interpolation approximations over the sphere S ^r−1⊂R ^r in the uniform norm, principally for r=3. Reimer [17] has shown there exist fundamental systems for which the norm ‖Λ _n ‖ of the interpolation operator Λ _n , considered as a map from C(S ^r−1) to C(S ^r−1), is bounded by d _n , where d _n is the dimension of the space of all spherical polynomials of degree at most n. Another bound is d _n ^1/2(λ_avg/λ_min)^1/2, where λ_avg and λ_min are the average and minimum eigenvalues of a matrix G determined by the fundamental system of interpolation points. For r=3 these bounds are (n+1)² and (n+1)(λ_avg/λ_min)^1/2, respectively. In a different direction, recent work by Sloan and Womersley [24] has shown that for r=3 and under a mild regularity assumption, the norm of the hyperinterpolation operator (which needs more point values than interpolation) is bounded by O(n ^1/2), which is optimal among all linear projections. How much can the gap between interpolation and hyperinterpolation be closed?

For interpolation the quality of the polynomial interpolant is critically dependent on the choice of interpolation points. Empirical evidence in this paper suggests that for points obtained by maximizing λ_min, the growth in ‖Λ _n ‖ is approximately n+1 for n<30. This choice of points also has the effect of reducing the condition number of the linear system to be solved for the interpolation weights. Choosing the points to minimize the norm directly produces fundamental systems for which the norm grows approximately as 0.7n+1.8 for n<30. On the other hand, ‘minimum energy points’, obtained by minimizing the potential energy of a set of (n+1)² points on S ², turn out empirically to be very bad as interpolation points.

This paper also presents numerical results on uniform errors for approximating a set of test functions, by both interpolation and hyperinterpolation, as well as by non-polynomial interpolation with certain global basis functions.

     

The uniform norm of hyperinterpolation on the unit sphere in an arbitrary number of dimensions

In this paper we study the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere S ^r−1 ⊂ R^r. The hyperinterpolation approximation L _n ƒ, where ƒ ∈ C(S ^r −1), is derived from the exact L ² orthogonal projection Π ƒ onto the space P _n ^r (S ^r −1) of spherical polynomials of degree n or less, with the Fourier coefficients approximated by a positive weight quadrature rule that integrates exactly all polynomials of degree ≤ 2n. We extend to arbitrary r the recent r = 3 result of Sloan and Womersley [9], by proving that under an additional “quadrature regularity” assumption on the quadrature rule, the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere is O(n ^r /2−1), which is the same as that of the orthogonal projection Π_n, and best possible among all linear projections onto P _n ^r (S ^r −1).     

Polynomial wavelets on the unit circle

In this paper, we have considered polynomial wavelets on unit circle. The scaling functions are considered to be the fundamental polynomials of the Lagrange interpolants on the equally spaced nodes different from the n roots of unity, which satisfy certain interpolatory conditions.     

Relativistic Lamé functions: Completeness vs. polynomial asymptotics

In earlier work we introduced and studied two commuting generalized Lamé operators, obtaining in particular joint eigenfunctions for a dense set in the natural parameter space. Here we consider these difference operators and their eigenfunctions in relation to the Hilbert space L²((0, π/r), w(x)dx), with r > 0 and the weight function w(x) a ratio of elliptic gamma functions. In particular, we show that the previously known pairwise orthogonal joint eigenfunctions need only be supplemented by finitely many new ones to obtain an orthogonal base. This completeness property is derived by exploiting recent results on the large-degree Hilbert space asymptotics of a class of orthonormal polynomials. The polynomials p_n(cos(rx)), n ε , that are relevant in the Lamé setting are orthonormal in L²((0, π/r), w_P(x)dx), with w_p(x) closely related to w(x).     

On a problem of (0,2)-interpolation

The object in this paper is to consider the problem of existence, uniqueness, explicit representation of (0,2)-interpolation on the zeros of (1−x²)P_n−1(x)/x when n is odd, where P_n−1 denotes Legendre polynomial of degreen−1, and the problem of convergence of interpolatory polynomials.     

On Divergence of Hermite—Fejér Interpolation to f(z)=z in the Complex Plane

We show that for a broad class of interpolatory matrices on [-1,1] the sequence of polynomials induced by Hermite—Fejér interpolation to f(z)=z diverges everywhere in the complex plane outside the interval of interpolation [-1,1] . This result is in striking contrast to the behavior of the Lagrange interpolating polynomials. June 15, 1998. Date accepted: January 26, 1999.     

E -Theoretic Duality for Higher Rank Graph Algebras

We prove that there is a Poincaré type duality in E-theory between higher rank graph algebras associated with a higher rank graph and its opposite correspondent. We obtain an r-duality, that is the fundamental classes are in E^r. The basic tools are a higher rank Fock space and higher rank Toeplitz algebra which has a more interesting ideal structure than in the rank 1 case. The K-homology fundamental class is given by an r-fold exact sequence whereas the K-theory fundamental class is given by a homomorphism. The E-theoretic products are essentially pull-backs so that the computation is done at the level of exact sequences. Mathematics Subject Classification (2000): 46L80.     

On polynomial symbols for subdivision schemes

Given a dilation matrix A :ℤ^d→ℤ^d, and G a complete set of coset representatives of 2π(A ^−Tℤ^d/ℤ^d), we consider polynomial solutions M to the equation ∑ _g∈G M(ξ+g)=1 with the constraints that M≥0 and M(0)=1. We prove that the full class of such functions can be generated using polynomial convolution kernels. Trigonometric polynomials of this type play an important role as symbols for interpolatory subdivision schemes. For isotropic dilation matrices, we use the method introduced to construct symbols for interpolatory subdivision schemes satisfying Strang–Fix conditions of arbitrary order. Research partially supported by the Danish Technical Science Foundation, Grant No. 9701481, and by the Danish SNF-PDE network.     

Integral formulae on hypersurfaces in Riemannian manifolds

The coefficients of the complete set of n fundamental forms of a hypersuface V_n−1 imbedded in an n-dimensional Riemannian space V_n, as recently introduced[(5)], are used to construct certain tensor fields over V_n−1 which display some remarkable features. In particular, the divergences of these tensor fields can be expressed very simply in terms of polynomials involving the curvature tensor of V_n, the coefficients of the n fundamental forms, and the r^th curvatures of V_n−1. As the result of an application of the generalized divergence theorem of Gauss to these relations a set of integral formulae on V_n−1 is obtained. The integrands of these integral formulae can be expressed very simply in terms of the n fundamental forms of V_n−1. By successive specialization it is indicated how known integral theorems([2], [3], [6], [7], [8]) can be derived as particular cases, which is possible partly as a result of the fact that the polynomial referred to above vanishes identically whenever V_n is a space of constant curvature. This research was supported by the National Research Council of Canada. Entrata in Redazione il 21 agosto 1970.     

Optimal points for numerical differentiation

Newn-pointr ^th derivative Lagrangian numerical differentiation formulas employ the best irregular locations of points, A. From the standpoint of highest degree accuracy for derivatives at a singlefixed point (n ^th degree accuracy proven to be the highestexactly attainable for anyr). B. From the Tschebyscheff standpoint of minimal largest |remainder| over an argument range. In B the dominant term in the remainder is minimal for arguments at the zeros ofr ^th order integrals of Tschebyscheff polynomials specialized by addition of suitable (r–1)^th degree polynomials chosen to produce real, distinct locations of points within or fairly close to the range of optimization. First and second derivative formulas up to nine-point, are obtained with remainder estimates.Presented at the Eleventh International Congress of Mathematicians Edinburgh, Scotland, August 14–21, 1958.