A multiresolution method for fitting scattered data on the sphere

In this work, we propose an efficient multiresolution method for fitting scattered data functions on a sphere S, using a tensor product method of periodic algebraic trigonometric splines of order 3 and quadratic polynomial splines defined on a rectangular map of S. We describe the decomposition and reconstruction algorithms corresponding to the polynomial and periodic algebraic trigonometric wavelets. As application of this method, we give an algorithm which allows to compress scattered data on spherelike surfaces. In order to illustrate our results, some numerical examples are presented.     

Multiplicative orders on terms

Let R be a commutative ring with identity. Any order on terms of the polynomial algebra R[x ₁, …, x _k] induces in a natural way the notion of a leading term. An order on terms is called multiplicative if and only if the leading term of a product equals the product of leading terms. In this paper, we present a procedure for the construction of multiplicative orders. We obtain some characterizations of rings for which such orders exist. We give conditions sufficient for the existence of such orders. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 1, pp. 101–107, 2007.     

Sur le choix du paramètre d'ajustement dans le lissage par fonctions spline

Summary We consider the problem of approximating an unknown functionf, known with error atn equally spaced points of the real interval [a, b].To solve this problem, we use the natural polynomial smoothing splines. We show that the eigenvalues associated to these splines converge to the eigenvalues of a differential operator and we use this fact to obtain an algorithm, based on the Generalized Cross Validation method, to calculate the smoothing parameter.With this algorithm, we divide byn the time used by classical methods.

     

Solving two-point boundary value problems with spline functions

We consider a collocation method for the approximation of thesolution of the nonlinear two-point boundary value problem y'(x)=f(x,y(x)), y(a)=A, y(b)=B, using splines of degree m3. The methodwhich we shall use leads to a system of recurrence relationswhich can be solved by Newton's method. By obtaining asymptotic error bounds we verify a conjectureof Khalifa & Eilbeck, i.e. splines of even degree can giveeven better solutions than splines of odd degree in certaincases.     

Computing the bump number with techniques from two-processor scheduling

Let (X, <) be a partially ordered set. A linear extension x ₁, x ₂, ... has a bump whenever x _i<x _i+1, and it has a jump whenever x _iand x _i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem.Part of this work was done while the first author was a Research Student Associate at IBM Almaden Research Center. During the academic year his work is primarily supported by a Fannie and John Hertz Foundation Fellowship and is supported in part by ONR contract N00014-85-C-0731.     

Global convergence for Newton methods in mathematical programming

In constrained optimization problems in mathematical programming, one wants to minimize a functionalf(x) over a given setC. If, at an approximate solutionx _n , one replacesf(x) by its Taylor series expansion through quadratic terms atx _n and denotes byx _n+1 the minimizing point for this overC, one has a direct analogue of Newton's method. The local convergence of this has been previously analyzed; here, we give global convergence results for this and the similar algorithm in which the constraint setC is also linearized at each step.This research was supported in part by the Office of Naval Research, Contract No. N00014-67-0126-0015, and was presented by invitation at the Fifth Gatlinburg Symposium on Numerical Algebra, Los Alamos, New Mexico, 1972.     

Construction of multiwavelets with high approximation order and symmetry

In this paper, based on existing symmetric multiwavelets, we give an explicit algorithm for constructing multiwavelets with high approximation order and symmetry. Concretely, suppose Φ(x) := (φ1(x), . . . , φr(x))T is a symmetric refinable function vectors with approximation order m. For an arbitrary nonnegative integer n, a new symmetric refinable function vector Φnew(x) := (φn1 ew(x), . . . , φrn ew(x))T with approximation order m + n can be constructed through the algorithm mentioned above. Additionally,...     

Lagrange Interpolation by Bivariate C 1-Splines with Optimal Approximation Order

We develop the first local Lagrange interpolation scheme for C ¹-splines of degree q≥3 on arbitrary triangulations. For doing this, we use a fast coloring algorithm to subdivide about half of the triangles by a Clough–Tocher split in an appropriate way. Based on this coloring, we choose interpolation points such that the corresponding fundamental splines have local support. The interpolating splines yield optimal approximation order and can be computed with linear complexity. Numerical examples with a large number of interpolation points show that our method works efficiently.     

A univariate global search working with a set of Lipschitz constants for the first derivative

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f ′(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. Algorithms working with a number of Lipschitz constants for f ′(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm. This research was supported by the RFBR grant 07-01-00467-a and the grant 4694.2008.9 for supporting the leading research groups awarded by the President of the Russian Federation.     

Stable Determination of X-Ray Transforms of Time Dependent Potentials from Partial Boundary Data

We consider compact smooth Riemmanian manifolds with boundary of dimension greater than or equal to two. For the initial-boundary value problem for the wave equation with a lower order term q(t, x), we can recover the X-ray transform of time dependent potentials q(t, x) from the dynamical Dirichlet-to-Neumann map in a stable way. We derive conditional Hölder stability estimates for the X-ray transform of q(t, x). The essential technique involved is the Gaussian beam Ansatz, and the proofs are done with the minimal assumptions on the geometry for the Ansatz to be well-defined.     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001     

Estimation of the Location of the Maximum of a Regression Function Using Extreme Order Statistics

In this paper, we consider the problem of approximating the location,x₀∈C, of a maximum of a regresion function,θ(x), under certain weak assumptions onθ. HereCis a bounded interval inR. A specific algorithm considered in this paper is as follows. Taking a random sampleX₁, …, X_nfrom a distribution overC, we have (X_i, Y_i), whereY_iis the outcome of noisy measurement ofθ(X_i). Arrange theY_i's in nondecreasing order and take the average of ther X_i's which are associated with therlargest order statistics ofY_i. This average,x₀, will then be used as an estimate ofx₀. The utility of such an algorithm with fixed r is evaluated in this paper. To be specific, the convergence rates ofx₀tox₀are derived. Those rates will depend on the right tail of the noise distribution and the shape ofθ(·) nearx₀.     

Nonlocal higher order evolution equations

In this article, we study the asymptotic behaviour of solutions to the nonlocal operator u _t (x, t) = (?1) ^n?1 (J * Id ? 1) ⁿ (u(x, t)), x ∈ ? ^N , which is the nonlocal analogous to the higher order local evolution equation v _t = (?1) ^n?1(Δ) ⁿ v. We prove that the solutions of the nonlocal problem converge to the solution of the higher order problem with the right-hand side given by powers of the Laplacian when the kernel J is rescaled in an appropriate way. Moreover, we prove that solutions to both equations have the same asymptotic decay rate as t goes to infinity.     

Best Approximation and Cyclic Variation Diminishing Kernels

We study best uniform approximation of periodic functions from

Full-size image

where the kernelK(x, y) is strictly cyclic variation diminishing, and related problems including periodic generalized perfect splines. For various approximation problems of this type, we show the uniqueness of the best approximation and characterize the best approximation by extremal properties of the error function. The results are proved by using a characterization of best approximants from quasi-Chebyshev spaces and certain perturbation results.     

Characterization of H?lder spaces corresponding to Ditzian-Totik modulus of smoothness

For the step-weight function j( x ) = ?{1 - x² }\varphi \left( x \right) = \sqrt {1 - x^2 } , we prove that the H?lder spaces \gL{ina, p} on the interval [−1, 1], defined in terms of moduli of smoothness with the step-weight function ϕ, are linearly isomorphic to some sequence spaces, and the isomorphism is given by the coefficients of function with respect to a system of orthonormal splines with knots uniformly distributed according to the measure with density 1/ϕ. In case \gL{ina, p} is contained in the space of continuous functions, we give a discrete characterization of this space, using only values of function at the appropriate knots. Application of these results to characterize the order of polynomial approximation is presented.     

Non-uniform exponential tension splines

We describe explicitly each stage of a numerically stable algorithm for calculating with exponential tension B-splines with non-uniform choice of tension parameters. These splines are piecewisely in the kernel of D ²(D ²–p ²), where D stands for ordinary derivative, defined on arbitrary meshes, with a different choice of the tension parameter p on each interval. The algorithm provides values of the associated B-splines and their generalized and ordinary derivatives by performing positive linear combinations of positive quantities, described as lower-order exponential tension splines. We show that nothing else but the knot insertion algorithm and good approximation of a few elementary functions is needed to achieve machine accuracy. The underlying theory is that of splines based on Chebyshev canonical systems which are not smooth enough to be ECC-systems. First, by de Boor algorithm we construct exponential tension spline of class C ¹, and then we use quasi-Oslo type algorithms to evaluate classical non-uniform C ² tension exponential splines.      

Boundedness and Stability for Higher Order Difference Equations*

Sufficient conditions are given under which the higher order difference equation x _n+1= f(x _n,x _n-1,...,x_n-k ), n=0,1,2,... generates an order preserving discrete dynamical system with respect to the discrete exponential ordering. It is shown that under the above monotonicity assumption the boundedness of all solutions as well as the local and global stability of an equilibrium hold if and only if they hold for the much simpler first order equation x _n+1=h(x _n ), where h(x)=f(x,x,…,x). As an application, a second order nonlinear difference equation from macroeconomics and a discrete analogue of a model of haematopoiesis are discussed.     

Kernels of derivations of polynomial rings and Casimir elements

We propose an algorithm for the evaluation of elements of the kernel of an arbitrary derivation of a polynomial ring. The algorithm is based on an analog of the well-known Casimir element of a finite-dimensional Lie algebra. By using this algorithm, we compute the kernels of Weitzenb?ck derivation d(x _i ) = x _i−1, d(x ₀) = 0, i = 0,…, n, for the cases where n ≤ 6.     

Optimale hermite-interpolation differenzierbarer periodischer Funktionen

For the Favard class F_r in the space C_2π of continuous 2π-periodic functions we solve the following problem. Given x and knots x₀< x₁ < ··· < x_v−1., x_u− 2π we determine weights x_ki(0 k · n, 0 j < r) such that is minimal. The optimal weights are unique (except for a trivial case) and we obtain them from a system of periodic polynomial splines u_kj(0 k < n, 0 j< r): α_kj = u_kj(x). These splines induce an interpolation operator whose degree of approximation with respect to the class F_r is minimal if the knots are equidistant. Finally, we describe an efficient numerical procedure which shows how to compute the interpolation spline in the equidistant case.