Vector-valued Lg-splines I. Interpolating splines

The theory of Lg-splines developed by Jerome and Schumaker is extended to the vector-valued (multivariate) case. The extension is described in the frame-work of a reproducing-kernel Hilbert space which among other things allows the establishment of a congruent least-squares estimation problem for a vectorvalued lumped random process. The results include a dynamic recursive algorithm for vector-valued Lg-splines with EHB data and a useful structural characterization theorem for such splines. Some results on computable approximation error bounds are also included.     

Complexity Analysis via Approach Spaces

Complexity of a recursive algorithm typically is related to the solution to a recurrence equation based on its recursive structure. For a broad class of recursive algorithms we model their complexity in what we call the complexity approach space, the space of all functions in X?=? ]0,?∞?] ^Y , where Y can be a more dimensional input space. The set X, which is a dcpo for the pointwise order, moreover carries the complexity approach structure. There is an associated selfmap Φ on the complexity approach space X such that the problem of solving the recurrence equation is reduced to finding a fixed point for Φ. We will prove a general fixed point theorem that relies on the presence of the limit operator of the complexity approach space X and on a given well founded relation on Y. Our fixed point theorem deals with monotone selfmaps Φ that need not be contractive. We formulate conditions describing a class of recursive algorithms that can be treated in this way.     

Nonconvex variational problem with recursive integral functionals in Sobolev spaces: Existence and representation

The purpose of this paper is twofold. First, we present the existence theorem of an optimal trajectory in a nonconvex variational problem with recursive integral functionals by employing the norm-topology of a weighted Sobolev space. We show the continuity of the integral functional and the compactness of the set of admissible trajectories. Second, we show that a recursive integrand is represented by a normal integrand under the conditions guaranteeing the existence of optimal trajectories. We also demonstrate that if the recursive integrand satisfies the convexity conditions, then the normal integrand is a convex function. These results are achieved by the application of the representation theorem in Lp-spaces.     

Depth in bucket recursive trees with variable capacities of buckets

We consider bucket recursive trees of sizen consisting of all buckets with variable capacities1,2,...,b and with a specifc stochastic growth rule.This model can be considered as a generalization of random recursive trees like bucket recursive trees introduced by Mahmoud and Smythe where all buckets have the same capacities.In this work,we provide a combinatorial analysis of these trees where the generating function of the total weights satisfes an autonomous frst order diferential equation.We study the depth of the largest label（i.e.,the number of edges from the root node to the node containing label n）and give a closed formula for the probability distribution.Also we prove a limit law for this quantity which is a direct application of quasi power theorem and compute its mean and variance.Our results for b=1 reduce to the previous results for random recursive trees.     

Recursive error correction for general Reed-Muller codes

Reed-Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight (dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability p, which yields a vanishing output error probability on long codes.     

Convergence and error estimates for (m,l,s)-splines

In some recent papers, Bouhamidi and Le Méhauté introduced L^m,l,s-splines as a natural extension of J. Duchon's (m,s)-splines. In the present work, some results on convergence and error estimates for smoothing and interpolating L^m,l,s-splines (called here (m,l,s)-splines) are given. These results extend those presented in several papers by Duchon, Arcangéli and López de Silances for (m,s)-splines and also for D^m-splines (i.e. (m,0)-splines).     

Parameter estimation using minimum norm differential approximation

We present mathematical results which can be used to compute the parameters of a system described by differential equations, using the method of minimum norm differential approximation. The algorithm is described and several examples are given in both the ordinary and partial differential equations cases. The approximating subspaces used in this algorithm are those spanned by certain B-splines of degree 3 in the O.D.E. case and by tensor products of B-splines in the P.D.E. case. Singular value decomposition is used in two distinct ways in the algorithm. The method described can be used on any type of differential operator with constant coefficients, i.e., elliptic, hyperbolic, parabolic, although only in the case of elliptic operators can error bounds between the data function and a generalized solution of the D.E. with the approximated parameters be estimated.     

About the generalized LM-inverse and the weighted Moore-Penrose inverse

The recursive method for computing the generalized LM-inverse of a constant rectangular matrix augmented by a column vector is proposed in Udwadia and Phohomsiri (2007) [16] and [17]. The corresponding algorithm for the sequential determination of the generalized LM-inverse is established in the present paper. We prove that the introduced algorithm for computing the generalized LM-inverse and the algorithm for the computation of the weighted Moore-Penrose inverse developed by Wang and Chen (1986) in [23] are equivalent algorithms. Both of the algorithms are implemented in the present paper using the package MATHEMATICA. Several rational test matrices and randomly generated constant matrices are tested and the CPU time is compared and discussed.     

Pairs of B-Splines with Small Support on the Four-Directional Mesh Generating a Partition of Unity

Let τ be the four-directional mesh of the plane and let Σ₁ (respectively Λ₁) be the unit square (respectively the lozenge) formed by four (respectively eight) triangles of τ. We study spaces of piecewise polynomial functions in C ^k (R ²) with supports Σ₁ or Λ₁ having sufficiently high degree n, which are invariant with respect to the group of symmetries of Σ₁ or Λ₁ and whose integer translates form a partition of unity. Such splines are called complete Σ₁ and Λ₁-splines. We first give a general study of spaces of linearly independent complete Σ₁ and Λ₁-splines of class C ^k and degree n. Then, for any fixed k≥0, we prove the existence of complete Σ₁ and Λ₁-splines of class C ^k and minimal degree, but they are not unique. Finally, we describe algorithms allowing to compute the Bernstein–Bézier coefficients of these splines.     

Read-Once Functions Revisited and the Readability Number of a Boolean Function

In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P₄-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2^k function and a read 2^k formula for F for f can be obtained in polynomial time.     

Normalized trigonometric splines of Lagrange type

B _?-splines, which are a nonpolynomial generalization of the well-known B-splines, are investigated. B _?-splines arise from approximation relations regarded as a system of linear algebraical equations, from which both polynomial and nonpolynomial splines are derived. Third-order normalized trigonometric splines of Lagrange type (zero height) determined by the generating vector function ?(t) = (1, sin t, cos t, sin2 t) ^T are constructed. These splines are twice continuously differentiable and have minimal compact support. A system of functionals biorthogonal to B _?-splines is defined. The solution of the interpolation problem generated by the resulting biorthogonal system in the space of B _?-splines is found.     

Construction of polynomials of a special kind and examples of their application in the theory of power series and in the wavelet theory

In this paper we construct polynomials of a special type. We consider examples of their application for studying the convergence of special power series, for determining the upper and lower Riesz bounds for a basis consisting of B-splines, and for studying the convergence of a sequence of Battle-Lemarié scaling functions.     

A survey on the local refinable splines

This paper provides a survey of local refinable splines, including hierarchical B-splines, T-splines, polynomial splines over T-meshes, etc., with a view to applications in geometric modeling and iso-geometric analysis. We will identify the strengths and weaknesses of these methods and also offer suggestions for their using in geometric modeling and iso-geometric analysis.     

Multivariate interpolating (m, l, s)-splines

The multivariate interpolating (m, l, s)-splines are a natural generalization of Duchon's thin plate splines (TPS). More precisely, we consider the problem of interpolation with respect to some finite number of linear continuous functionals defined on a semi-Hilbert space and minimizing its semi-norm. The (m, l, s)-splines are explicitly given as a linear combination of translates of radial basis functions. We prove the existence and uniqueness of the interpolating (m, l, s)-splines and investigate some of their properties. Finally, we present some practical examples of (m, l, s)-splines for Lagrange and Hermite interpolation.     

Shannon-type sampling for multivariate non-bandlimited signals

In this paper, starting from a function analytic in a neighborhood of the unit disk and based on Bessel functions, we construct a family of generalized multivariate sinc functions, which are radial and named radial Bessel-sinc (RBS) functions being time-frequency atoms with nonlinear phase. We obtain a recursive formula for the RBS functions in R d with d being odd. Based on the RBS function, a corresponding sampling theorem for a class of non-bandlimited signals is established. We investigate a class of radial functions and prove that each of these functions can be extended to become a monogenic function between two parallel planes, where the monogencity is taken to be of the Clifford analysis sense.     

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.     

Rectified approximations for the solution of nonlinear equations

In this paper we introduce the ‘rectification method’ for the construction of algorithms of pre-designed order r for the solution of nonlinear equations f(x) = 0. Our method is based upon the derivation of a rectified approximation g(x) to f(x), via Padé formulas, such that the application of the Newton-Raphson iterations to g generates the desired rth order algorithm. Various properties of g are explored as are recursive relations among rectified approximations associated with successive orders of convergence. It is demonstrated that the use of g in favor of f can relax standard sufficient conditions assuring convergence of the iterations.     

Algorithms for maximum independent sets

An algorithm is presented which finds (the size of) a maximum independent set of an n vertex graph in time O(2^0.276n) improving on a previous bound of $\text{O(2}{}^{\mathrm{<mtext>n</mtext><mtext>3</mtext>}}\text{)}$. The improvement comes principally from three sources: first, a modified recursive algorithm based on a more detailed study of the possible subgraphs around a chosen vertex; second, an improvement, not in the algorithm but in the time bound proved, by an argument about connected regular graphs; third, a time-space trade-off which can speed up recursive algorithms from a fairly wide class.     

On Schmerl's effective version of Brooks' theorem

A new proof is given of Schmerl's recent result that a highly recursive graph G with χ(G) ≤ k according to Brooks' theorem, has a recursive k-colouring.