Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Behavior of the beta-splines with values of the parameters beta2 negative

In this paper we study the behavior of the beta-spline functions in the case the parameter β₂(i) is negative. We prove that a negative value exists so that if , the beta-spline functionsN_i(u) are positive. Moreover, if the control vertices are such that x₀ x_m−1, we have proved that the design curve keeps the properties already proved in the case β₂(i) 0.     

A complete algebraic solvability test for the nonstrict Lyapunov inequality

For arbitrary equally sized square complex matrices A and Q (Q Hermitian), the paper provides a complete algebraic test for verifying the existence of a Hermitian solution X of the nonstrict Lyapunov inequality A^*X + XA + Q 0. If existing, we exhibit how to construct a solution. Our approach involves the validation problem for the linear matrix inequality Σ_j=1^k (A_j^*X_jB_j + B_j^*X_j^*A_j) + Q> 0 in X_j, for which we provide an algebraic solvability test and a construct solutions if the kernels of A_j or, dually, those of B_j form an isotonic sequence.     

An element for static, vibration and buckling analysis of thick laminated plates

A conforming finite element formulation of the equations governing composite multilayered plates using Reddy's higher-order theory is presented. The element has eight degrees of freedom, u₀, v₀, w, ∂w/∂x, ∂w/∂y, ∂²w/∂x∂y, γ_x, γ_y, per node. The transverse displacement of the present element is described by a modified bicubic displacement function while the in-plane displacements and shear-rotations are interpolated quadraticly. The element is evaluated for its accuracy in the analysis of static, vibration, and buckling of anisotropic rectangular plates with different lamination schemes and boundary conditions. The conforming finite element described here for the higher-order theory gives fairly accurate results for displacements, stresses, buckling loads, and natural frequencies.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

Nonnegative solutions of singular boundary value problems with sign changing nonlinearities

The paper presents sufficient conditions for the existence of positive solutions of the equation x″(t) + q(t)f(t,x(t),x′(t)) = 0 with the Dirichlet conditions x(0) = 0, x(1) = 0 and of the equation (p(t)x′(t))′ + p(t)q(t)f(t,x(t),p(t)x′(t)) = 0 with the boundary conditions lim_t→o⁺ p(t)x′(t) = 0, x(1) = 0. Our nonlinearity f is allowed to change sign and f may be singular at x = 0. The proofs are based on a combination of the regularity and sequential techniques and the method of lower and upper functions.     

Lyapunov exponents of the logistic map with periodic forcing

The iterative map x_n+1 = r_nx_n (1 - x_n) is investigated with r_n changing periodically between two values A and B. Different periodicities are assumed, e.g., {r_n} = {BABA …} or {r_n} = {BBABA BBABA …}. The Lyapunov exponent (a measure of average stability) is displayed with high resolution on the A-B-plane. The resulting images have aesthetically appealing self-similar structures. Furthermore, these images allow with one glimpse the identification of a number of system properties: coexistence of attractors, superstable curves, order by alternation of chaotic processes, and chaos by periodic resetting from a stable into an unstable fixed point.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

3-D silicon vector sensor based on a novel parallel-field Hall microdevice

A single-chip 3-D silicon vector sensor for magnetic-field measurement is presented. This triaxial device functionally integrates in a common transducer region two novel five-contacts parallel-field Hall elements for in-plane components B_x and B_y and four cross-coupled orthogonal triple Hall elements for the B_z component, perpendicular to the chip surface. The effective sensor volume is 150 μm×150 μm×100 μm. The main advantage of this 3-D vector magnetometer is the strongly reduced (with about 45%) channel cross-sensitivities. This is achieved by amperometric output mode of operation using an original read-out circuitry, keeping equal voltage conditions on the top of the chip with and without magnetic field. The sensitivities per channel reaches S_A(B_x)=S_A(B_y)=356 μA/T and S_A(B_z)=260 μA/T at a supply current 10 mA, the measured equivalent offsets of the three channel outputs are 25/35 mT and the low frequency noise is mainly a 1/f. The lowest detected magnetic induction of the three output channels is about 15/20 μT in the range 1≤f≤ 10² Hz and the frequency response of the 3-D device together with the read-out electronics is at least 30 kHz.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Blossoms are polar forms

Consider the functions H(t):=t² and h(u,v):=uv. The identity H(t)=h(t,t) shows that h is the restriction of h to the diagonal u=v in the uv-plane. Yet, in many ways, a bilinear function like h is simpler than a homogeneous quadratic function like H. More generally, if F(t) is some n-ic polynomial function, it is often helpful to study the polar form of F, which is the unique symmetric, multiaffine function ƒ(u_1,…u_n) satisfying the identity F(t)=f(t,…,t). The mathematical theory underlying splines is one area where polar forms can be particularly helpful, because two pieces F and G of an n-ic spline meet at a point r with C^k parametric continuity if and only if their polar forms ƒ and g agree on all sequences of n arguments that contain at least n-k copies of r.

The polar approach to the theory of splines emerged in rather different guises in three independent research efforts: Paul de Faget Casteljau called it ‘shapes through poles’; Carl de Boor called it ‘B-splines without divided differences’; and Lyle Ramshaw called it ‘blossoming’. This paper reviews the work of de Casteljau, de Boor, and Ramshaw in an attempt to clarify the basic principles that underly the polar approach. It also proposes a consistent system of nomenclature as a possible standard.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

On canonical number systems

Let be such that d1,p_d=1,p₀2 and . We are proving in this note a new criterion for the pair to be a canonical number system. This enables us to prove that if p₂,…,p_d−1,∑_i=1^dp_i0 and p₀>2∑_i=1^d|p_i|, then is a canonical number system.     

Uniform and optimal schemes for stiff initial-value problems

We formulate a class of difference schemes for stiff initial-value problems, with a small parameter ε multiplying the first derivative. We derive necessary conditions for uniform convergence with respect to the small parameter ε, that is the solution of the difference scheme u_i^h satisfies |u_i^h−u(x_i)| Ch, where C is independent of h and ε. We also derive sufficient conditions for uniform convergence and show that a subclass of schemes is also optimal in the sense that |u_i^h−u(x_i)| C min (h, ε). Finally, we show that this class contains higher-order schemes.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.