Hermite interpolation with simple planar PH curves by speed reparametrization

We introduce a new method of solving C¹ Hermite interpolation problems, which makes it possible to use a wider range of PH curves with potentially better shapes. By characterizing PH curves by roots of their hodographs in the complex representation, we introduce PH curves of type K(t−c)²ⁿ⁺¹+d. Next, we introduce a speed reparametrization. Finally, we show that, for C¹ Hermite data, we can use PH curves of type K(t−c)²ⁿ⁺¹+d or strongly regular PH quintics satisfying the G¹ reduction of C¹ data, and use these curves to solve the original C¹ Hermite interpolation problem.     

Branching blend of natural quadrics based on surfaces with rational offsets

A new branching blend between two natural quadrics (circular cylinders/cones or spheres) in many positions is proposed. The blend is a ring shaped patch of a PN surface (surface with rational offset) parametrized by rational bivariant functions of degree (6,3). The general theory of PN surfaces is developed using Laguerre geometry and a universal rational parametrization of the Blaschke cylinder. The construction is extended via inversion to a PN branching blend of degree (8,4) between Dupin cyclide and a natural quadric.     

Multi-degree reduction of triangular Bézier surfaces with boundary constraints

Given a triangular Bézier surface of degree n, the problem of multi-degree reduction by a triangular Bézier surface of degree m with boundary constraints is investigated. This paper considers the continuity of triangular Bézier surfaces at the three corners, so that the boundary curves preserve endpoints continuity of any order . The l₂- and L₂-norm combined with the constrained least-squares method are used to get the matrix representations for the control points of the degree reduced surfaces. Both methods can be applied to piecewise continuous triangular patches or to only a triangular patch with the combination of surface subdivision. And the resulting piecewise approximating patches are globally C⁰ continuous. Finally, error estimation is given and numerical examples demonstrate the effectiveness of our methods.     

A novel lossless data compression scheme based on the error correcting Hamming codes

This paper introduces a novel lossless binary data compression scheme that is based on the error correcting Hamming codes, namely the HCDC scheme. In this scheme, the binary sequence to be compressed is divided into blocks of n bits length. To utilize the Hamming codes, the block is considered as a Hamming codeword that consists of p parity bits and d data bits (n=d+p). Then each block is tested to find if it is a valid or a non-valid Hamming codeword. For a valid block, only the d data bits preceded by 1 are written to the compressed file, while for a non-valid block all n bits preceded by 0 are written to the compressed file. These additional 1 and 0 bits are used to distinguish the valid and the non-valid blocks during the decompression process. An analytical formula is derived for computing the compression ratio as a function of block size, and fraction of valid data blocks in the sequence. The performance of the HCDC scheme is analyzed, and the results obtained are presented in tables and graphs. Finally, conclusions and recommendations for future works are pointed out.     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.     

A new algebra of Toeplitz-plus-Hankel matrices and applications

We introduce a new simultaneously diagonalizable real algebra of symmetrical centrosymmetrical matrices having a Toeplitz-plus-Hankel structure. We give the corresponding orthonormal basis of eigenvectors which are alternately symmetrical and skewsymmetrical vectors. An application is the construction of a symmetrical Toeplitz-plus-centrosymmetrical Hankel matrix of equal row sums having a prescribed real spectrum. This matrix can be used as the starting matrix for symmetrical centrosymmetrical isospectral flows. In particular, for the isospectral flow corresponding to the construction of a regular Toeplitz matrix having prescribed eigenvalues. Moreover, if A is a noise representation of an unknown matrix in of rank k then we give a procedure to approximate A by a matrix in of rank k.     

A minimal representation of Markov arrival processes and a moments matching method

The paper investigates the problem of minimal representation of Markov arrival processes of order n (MAP(n)). The minimal representation of MAPs is crucial for developing effective fitting methods. It seems that all existing MAP fitting methods are based on the , representation which is known to be redundant. We present the minimal number of parameters to define a MAP(n) and provide a numerical moments-matching method based on a minimal representation.

The discussion starts with a characterization of phase type (PH) distributions and then the analysis of MAPs follows a similar pattern. This characterization contains essential results on the identity of stationary behaviour of MAPs and on the number of parameters required to describe the stationary behaviour.

The proposed moments matching method is also applicable for PH distributions. In this case it is a unique method that fits a general PH distribution of order n based on 2n−1 parameters.     

Triple positive solutions for some second-order boundary value problem on a measure chain

In this paper, we study the existence of three positive solutions for the second-order two-point boundary value problem on a measure chain,

where f:[t₁,σ(t₂)]×[0,∞)×R→[0,∞) is continuous and p:[t₁,σ(t₂)]→[0,∞) a nonnegative function that is allowed to vanish on some subintervals of [t₁,σ(t₂)] of the measure chain. The method involves applications of a new fixed-point theorem due to Bai and Ge [Z.B. Bai, W.G. Ge, Existence of three positive solutions for some second order boundary-value problems, Comput. Math. Appl. 48 (2004) 699–707]. The emphasis is put on the nonlinear term f involved with the first order delta derivative x^Δ(t).     

Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations

An important problem that arises in different areas of science and engineering is that of computing the limits of sequences of vectors {x_n}, where with N very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and lim_n→∞x_n are simply the required solutions. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make the sequences {x_n} converge more quickly is to apply to them vector extrapolation methods. In this work, we review two polynomial-type vector extrapolation methods that have proved to be very efficient convergence accelerators; namely, the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE). We discuss the derivation of these methods, describe the most accurate and stable algorithms for their implementation along with the effective modes of usage in solving systems of equations, nonlinear as well as linear, and present their convergence and stability theory. We also discuss their close connection with the method of Arnoldi and with GMRES, two well-known Krylov subspace methods for linear systems. We show that they can be used very effectively to obtain the dominant eigenvectors of large sparse matrices when the corresponding eigenvalues are known, and provide the relevant theory as well. One such problem is that of computing the PageRank of the Google matrix, which we discuss in detail. In addition, we show that a recent extrapolation method of Kamvar et al. that was proposed for computing the PageRank is very closely related to MPE. We present a generalization of the method of Kamvar et al. along with a very economical algorithm for this generalization. We also provide the missing convergence theory for it.     

Fast algorithms for finding disjoint subsequences with extremal densities

We derive fast algorithms for the following problem: given a set of n points on the real line and two parameters s and p, find s disjoint intervals of maximum total length that contain at most p of the given points. Our main contribution consists of algorithms whose time bounds improve upon a straightforward dynamic programming algorithm, in the relevant case that input size n is much bigger than parameters s and p. These results are achieved by selecting a few candidate intervals that are provably sufficient for building an optimal solution via dynamic programming. As a byproduct of this idea we improve an algorithm for a similar subsequence problem of Chen et al. [Disjoint segments with maximum density, in: International Workshop on Bioinformatics Research and Applications IWBRA 2005, (within ICCS 2005), Lecture Notes in Computer Science, vol. 3515, Springer, Berlin, pp. 845–850]. The problems are motivated by the search for significant patterns in biological data. Finally, we propose several heuristics that further reduce the time complexity in typical instances. One of them leads to an apparently open subsequence sum problem of independent interest.