Search

We search for the Markov chain with the optimal mixing rate where transitions are restricted to happen along a cycle of the states. We show that homogeneous, reversible chains are locally optimal for perturbations that make them inhomogeneous and non-reversible. Moreover, we show the optimality holds globally if only a single type of perturbation (either inhomogeneous or non-reversible) is applied. However, we conjecture global optimality holds for mixed perturbations as well, which is backed by simulation results. This paper complements previous results on bounds for mixing times of general Markov chains on the cycle [1].

Subspace tracking methods are widespread in signal and image processing. To reduce the influence of perturbations or outliers on the measurements, some authors have used a stochastic piecewise constant velocity model on the Grassmann manifold. This paper presents an efficient way to simulate such a model using a particular representation of the Grassmann manifold. By doing so, we can reduce the spatial and time complexity of filtering techniques based on this model. We also propose an approximation of this system which can be computed in a finite number of operations and show similar results if the subspace variation is slow.

We consider the problem of comparing two directed graphs with nodes that have been subdivided into classes of different type. The matching process is based on a constrained projection of the nodes of the graphs in a lower dimensional space. This procedure is formulated as a non-convex optimization problem. The objective function uses the two adjacency matrices of the graphs where the nodes are adequately numbered. The constraints on the problem impose the isometry of the so-called projections. An iterative algorithm is proposed to solve the optimization problem. As illustration, we give an example of graph matching for graphs with two types of nodes. Finally, an extension for comparing both groups of nodes in a directed bipartite graph is presented.

We propose a Forward/Backward (F/B) decomposition of periodic discrete time descriptor systems and describe a numerically reliable method to compute it. We mention a couple of applications of this F/B canonical form; namely, the solution of two-point boundary value problems, and discrete time Floquet theory.

We study the l 2 -induced norm, or H ∞ -norm, of discrete-time periodically time varying (PTV) systems and propose a quadratically convergent algorithm to compute it. Our method involves numerically stable computations (periodic Schur decomposition) and works even for the descriptor case. This work has connections to stability radii problems. Among other things, we clarify the relationship between various TI representations of a PTV system.

We present a new method for eigenvalue assignment in linear periodic discrete-time systems through the use of linear periodic state feedback. The proposed method uses reliable numerical techniques based on unitary transformations. In essence, it computes the Schur form of the open-loop monodromy matrix via a recent implicit eigen-decomposition algorithm, and shifts its eigenvalues sequentially. Given complete reachability of the open-loop system, we show that we can assign an arbitrary set of eigenvalues to the closed-loop monodromy matrix in this manner. Under the weaker assumption of complete control-lability, this method can be used to place all eigenvalues at the origin, thus solving the so-called deadbeat control problem. The algorithm readily extends to more general situations, such as when the system equation is given in descriptor form.

In this paper we discuss the numerical properties of a new algorithm for computing the zeros of linear multivariable systems and compare it with some earlier techniques of computing zeros. The new approach can handle both nonsquare and/or degenerate systems without difficulties whereas earlier methods would either fail or would require special treatment for these cases. The method is very efficient and backward stable in a rigorous sense.

A uniformly balanced realization for time-varying systems is defined. Such a framework has many remarkable properties and leads to a natural setting for performing model reduction. It turns out that in many cases a reduced model preserves the properties of the original model. In this paper stability of the reduced systems is fully explored.

A factorization of a regular rational matrix R(?) = R1 (?)R2 (?) is said to be minimal if the degrees ?1 and ?2 of the two factors add up to the degree ? of R(?). This problem has been studied earlier and it is known that in general nontrivial (i.e. ?1?0 and ?2;?0) factorizations may not exist [1]. Recently [2-3] a geometric approach using state-space representations yielded simple existence conditions for general minimal factorizations. In this paper we follow a more practical approach and focus on numerical and algorithmic aspects. Since the two points of view complement each other we briefly recall the main results of [3] from a system theoretical perspective.

A new algorithm for the GCD extraction of a set of polynomial matrices is given. The approach is based on system theoretic notions of feedback.

The problem of balancing the state space system matrices of a linear time-invariant system prior to computation of its transmission zeros is considered. It is shown that in some cases balancing has a significant effect on the accuracy of the computed transmission zeros. An algorithm designed specifically for balancing the system matrices for the computation of transmission zeros is presented. The paper also presents a new numerically stable algorithm for computation of zeros and gains of transfer functions. Several examples are provided to illustrate the algorithms in the paper.

This paper presents a novel method of extracting the general structure of a pencil ?B-A using stable transformations. Special applications are treated such as the computation of minimal realizations, (invariant, transmission and decoupling) zeros, supremal (A,B)-invariant and controllability subspaces.

The generalized eigenvalue problem provides a suitable framework for reliable solutions of many system theoretic, control, and estimation problems. A general algorithm for solving the matrix algebraic Riccati equation (ARE) which utilizes a pencil structure is described here. This algorithm avoids unnecessary inversion of cost or transition matrices, making it a numerically sound way to solve for the gains and/or ARE with singular quadratic costs, for cases satisfying detectability and stabilizability conditions. Examples are solution with discrete dead-beat control, noiseless measurements in Kalman filters and time-delays in discrete-time systems, which cause difficulties in the Hamiltonian standard eigenvalue problem formulation. The ARE algorithm implementation and numerical examples are shown.