Fixed zeros in the model matching problem for systems over semirings

This paper studies “fixed zeros” of solutions to the model matching problem for systems over semirings. Such systems have been used to model queueing systems, communication networks, and manufacturing systems. The main contribution of this paper is the discovery of two fixed zero structures, which possess a connection with the extended zero semimodules of solutions to the model matching problem. Intuitively, the fixed zeros provides an essential component that is obtained from the solutions to the model matching problem. For discrete event dynamic systems modeled in max-plus algebra, a common Petri net component constructed from the solutions to the model matching problem can be discovered from the fixed zero structure.     

Two concepts of singularity for matrices over semirings

The two common concepts of singularity for matrices over semirings are being studied since the 1970’s and arise from natural generalizations of the determinant and linear dependence. They were introduced in the context of schedule algebras by Gondran and Minoux, who proved later that the concepts discussed are equivalent over any selective invertible semiring. We present an approach that uses a generalization of power series arithmetic and, in particular, allows to derive a short proof for the theorem of Gondran and Minoux. Our main result is a complete concise characterization of semirings over which the two concepts of singularity are equivalent.     

Bases in semilinear spaces over zerosumfree semirings

This paper investigates the cardinality of a basis and the characterizations of a basis in semilinear space of n-dimensional vectors over zerosumfree semirings. First, it discusses the cardinality of a basis and gives some necessary and sufficient conditions that each basis has the same number of elements. Then it presents some conditions that a set of vectors is a basis and that a set of linearly independent vectors can be extended to a basis. In the end, it shows a necessary and sufficient condition that two semilinear spaces are isomorphic.     

Factor and term ranks for matrix union over semirings

We consider the arithmetic properties of the factor-rank and term-rank functions for matrices over semirings. In particular, we investigate the sets of matrices that satisfy the extremes of inequalities for these rank functions of matrix union. The classification of the linear transformations that keep these sets invariant is obtained. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 3, pp. 175–197, 2003.     

Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem

Applications such as the modal analysis of structures and acoustic cavities require a number of eigenvalues and eigenvectors of large‐scale Hermitian eigenvalue problems. The most popular method is probably the spectral transformation Lanczos method. An important disadvantage of this method is that a change of pole requires a complete restart. In this paper, we investigate the use of the rational Krylov method for this application. This method does not require a complete restart after a change of pole. It is shown that the change of pole can be considered as a change of Lanczos basis. The major conclusion of this paper is that the method is numerically stable when the poles are chosen in between clusters of the approximate eigenvalues. Copyright © 2001 John Wiley & Sons, Ltd.     

Projective semimodules over semirings with valuations in nonnegative integers

We introduce semirings with valuations in nonnegative integers and prove that all projective semimodules over them are free.     

Fixed points of endomorphisms over special confluent rewriting systems

Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization for the case of infinite fixed points.     

Fixed points of endomorphisms over special confluent rewriting systems

Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization for the case of infinite fixed points.     

A graph-theoretic model to solve the approximate string matching problem allowing for translocations

In this paper, we study the approximate string matching problem under a string distance whose edit operations are translocations of equal length factors. We extend a graph-theoretic approach proposed by Rahman and Illiopoulos (2008) to model our problem. In the sequel, we devise efficient algorithms based on this model to solve a number of variants of the string matching problem with translocations.     

On dominant poles and model reduction of second order time-delay systems

The method known as the dominant pole algorithm (DPA) has previously been successfully used in combination with model order reduction techniques to approximate standard linear time-invariant dynamical systems and second order dynamical systems. In this paper, we show how this approach can be adapted to a class of second order delay systems, which are large scale nonlinear problems whose transfer functions have an infinite number of simple poles. Deflation is a very important ingredient for this type of methods. Because of the nonlinearity, many deflation approaches for linear systems are not applicable. We therefore propose an alternative technique that essentially removes computed poles from the system?s input and output vectors. In general, this technique changes the residues, and hence, modifies the order of dominance of the poles, but we prove that, under certain conditions, the residues stay near the original residues. The new algorithm is illustrated by numerical examples.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

Exact model matching of generalized state space systems

The problem of exact model matching for generalized state space (GSS) systems via pure proportional state and output feedback is studied. The following two major issues are resolved here for the first time: The necessary and sufficient conditions for the problem to have a solution and the general analytical expressions for the exact modelmatching controller matrices. The important case of left invertible systems is treated separately wherein simple solutions are established for the above two major issues and results on structural properties of the closed-loop system are reported. Known results on model matching of regular systems are derived as a special case of the GSS systems results, thus unifying the solution of the exact model-matching problem of regular and singular systems.The work described in this paper has been partially funded by the General Secretariat for Research and Technology of the Greek Ministry of Industry, Research, and Technology and by the Heracles General Cement Company of Greece.     

Fixed points and matching points in partitions

The Ramanujan Journal - We study fixed points in integer partitions viewed, respectively, as weakly increasing or weakly decreasing structures. A fixed point is a point with value i in position i....     

Generalized model matching and (F,G)-invariant submodules for linear systems over rings

A generalized version of the exact model matching problem (GEMMP) is considered for linear multivariable systems over an arbitrary commutative ring K with identity. Reduced forms of this problem are introduced, and a characterization of all solutions and minimal order solutions is given, both with and without the properness constraint on the solutions, in terms of linear equations over K and K-modules. An approach to the characterization of all stable solutions is presented which, under a certain Bezout condition and a freeness condition, provides a parametrization of all stable solutions. The results provide an explicit parametrization of all solutions and all stable solutions in case K is a field, without the Bezout condition. This is achieved through a very simple characterization and a generalization to an arbitrary field K of the “fixed poles” of the model matching problem in terms of invariant factors of a certain polynomial matrix. The results also show that whenever the GEMMP has a solution, there exist solutions whose poles can be chosen arbitrarily as far as they contain the “fixed poles” with the right multiplicities (in the algebraic closure of K). Implications of these results in regard to inverse systems are shown. Equivalent simpler forms (in state space form) of the problem are shown to be obtainable. A theory of finitely generated (F,G)-invariant submodules for linear systems over rings is developed, and the geometric equivalent of the model matching problem—the dynamic cover problem—is formulated, to which the results of the previous sections provide a solution in the reduced case.     

A maximum stable matching for the roommates problem

The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n ²) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n ²) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04.     

An efficient algorithm for the bipartite matching problem

The minimum cost bipartite matching problem is considered. An approach based on the solution of a sequence of shortest path sub-problems is proposed. The particular structure of the problem and the use of reduced costs make it possible to devise an efficient “threshold” algorithm to solve these sub-problems. The computational behaviour of the proposed procedure is analyzed.     

Note on cardinality of bases in semilinear spaces over zerosumfree semirings

A necessary and sufficient condition under which all bases in a semilinear space of n-dimensional vectors over zerosumfree semirings have exactly n elements is established.     

Model recovery for Hammerstein systems using the auxiliary model based orthogonal matching pursuit method

This article investigates parameter and order identification of a block-oriented Hammerstein system by using the orthogonal matching pursuit method in the compressive sensing theory which deals with how to recover a sparse signal in a known basis with a linear measurement model and a small set of linear measurements. The idea is to parameterize the Hammerstein system into the linear measurement model containing a measurement matrix with some unknown variables and a sparse parameter vector by using the key variable separation principle, then an auxiliary model based orthogonal matching pursuit algorithm is presented to recover the sparse vector.The standard orthogonal matching pursuit algorithm with a known measurement matrix is a popular recovery strategy by picking the supporting basis and the corresponding non-zero element of a sparse signal in a greedy fashion. In contrast to this, the auxiliary model based orthogonal matching pursuit algorithm has unknown variables in the measurement matrix. For a K-sparse signal, the standard orthogonal matching pursuit algorithm takes a fixed number of K stages to pick K columns (atoms) in the measurement matrix, while the auxiliary model based orthogonal matching pursuit algorithm takes steps larger than K to pick K atoms in the measurement matrix with the process of picking and deleting atoms, due to the gradually accurate estimates of the unknown variables step by step.The auxiliary model based orthogonal matching pursuit algorithm can simultaneously identify parameters and orders of the Hammerstein system, and has a high efficient identification performance.