The parametric solution of underdetermined linear ODEs

The purpose of this paper is twofold. An immediate practical use of the presented algorithm is its applicability to the parametric solution of underdetermined linear ordinary differential equations (ODEs) with coefficients that are arbitrary analytic functions in the independent variable. A second conceptual aim is to present an algorithm that is in some sense dual to the fundamental Euclids algorithm, and thus an alternative to the special case of a Gröbner basis algorithm as it is used for solving linear ODE-systems. In the paper Euclids algorithm and the new “dual version” are compared and their complementary strengths are analysed on the task of solving underdetermined ODEs. An implementation of the described algorithm is interactively accessible under [7].     

Time response bounds for linear parametric uncertain systems

Parametric uncertainties in linear time-invariant state-space models introduce perturbations in the eigenvalues and eigenvectors (eigenstructure), which modify the properties of a nominal system. Besides stability by the perturbed eigenvalues, controllability, observability, transient and steady-state values, etc., are some basic properties of a linear system significantly influenced by the perturbed eigenvectors. In this paper, time response analysis of parametric uncertain systems is considered. First the bounds on eigenvectors and parametric uncertainties are established for the perturbed eigenvalues to reside in a set of distinct circular regions. Secondly, analysis of such parametric uncertain systems is discussed by presenting bounds on the perturbed state variables in time coordinate. These bounds are then investigated for norm-bounded and structured uncertainty classifications. Input-output analysis of uncertain systems is illustrated using the initial conditions and input functions.     

A logarithmic-time solution to the point location problem for parametric linear programming

The optimiser of a (multi) parametric linear program (pLP) is a piecewise affine function defined over a polyhedral subdivision of the set of feasible states. Once this affine function has been pre-calculated, the optimal solution can be computed for a particular parameter by determining the region that contains it. This is the so-called point location problem. In this paper, we show that this problem can be written as an additively weighted nearest neighbour search that can be solved in time linear in the dimension of the state space and logarithmic in the number of regions.

It is well-known that linear model predictive control (MPC) problems based on linear control objectives (e.g., 1- or ∞-norm) can be posed as pLPs, and on-line calculation of the control law involves the solution to the point location problem. Several orders of magnitude sampling speed improvement are demonstrated over traditional MPC and closed-form MPC schemes using the proposed scheme.     

On input-output parametric invariance in linear systems

The problem of the invariance of the input-output behavior of time-invariant linear systems under perturbations in the system matrices and initial conditions is examined. Previous results are unified and expanded upon, and new results for invariance in the presence of perturbations in the output matrix are given. Conditions for input-output invariance are related to the subspace of reachable states and its orthogonal complement, and to the subspace of unobservable states.     

Fast algorithm for the solution of banded linear systems

Linear systems can be solved by converting the coefficient matrix into a triangular matrix. If it is known, apriori, that the coefficient matrix is a banded matrix having only few non zero diagonals, then a substantial saving in both the time and the storage on the computer can be achieved. In this paper a new algorithm has been developed for triangularisation of the banded matrix. The algorithm is computationally economical and advantageous as compared to the existing known algorithms. The advantage decreases with the increase in bandwidth and the break even point being approximately N/√3 where N is the size of the square matrix.     

Two parametric approaches for eigenstructure assignment in second-order linear systems

This paper considers eigenstructure assignment in second-order linear systems via proportional plus derivative feedback . It is shown that the problem is closely related to a type of so-called second-order Sylvester matrix equations. Through establishing two general parametric solutions to this type of matrix equations, two complete parametric methods for the proposed eigenstructure assignment problem are presented. Both methods give simple complete parametric expressions for the feedback gains and the closed-loop eigenvector matrices. The first one mainly depends on a series of singular value decompositions, and is thus numerically simple and reliable; the second one utilizes the right factorization of the system, and allows the closed-loop eigenvalues to be set undetermined and sought via certain optimization procedures. An example shows the effectiveness of the proposed approaches.     

Robustness analysis for linear dynamical systems with linearlycorrelated parametric uncertainties

The authors propose an approach for robust pole location analysis of linear dynamical systems with parametric uncertainties. Linear control systems with characteristic polynomials whose coefficients are affine in a vector of uncertain physical parameters are considered. A design region in complex plane for system pole placement and a nominal parameter vector generating a characteristic polynomial with roots in that region are given. The proposed method allows the computation of maximal domains bounded by linear inequalities and centered at the nominal point in system parameter space, preserving system poles in the given region. The solution of this problem is shown to also solve the problem of testing robot location of a given polytope of polynomials in parameter space. It is proved that for stability problems for continuous-time systems with independent perturbations on polynomial coefficients, this method generates the four extreme Kharitonov polynomials     

Moment stability for linear systems with a random parametric excitation

Moment stability for linear systems with a nonwhite parametric noise is considered. A method of reduction of the study of this stability to the study of stability for large-scale matrices is proposed. Mean square stability diagrams for random harmonic oscillator are presented.     

On efficient parametric identification methods for linear discrete stochastic systems

We construct a numerically stable algorithm (with respect to machine rounding errors) of adaptive Kalman filtering in order to solve the parametric identification problem for linear stationary stochastic discrete systems. We solve the problem in the state space. The proposed algorithm is formulated in terms of an orthogonal square-root covariance filter which lets us avoid a standard implementation of the Kalman filter.     

Transputer data-flow solution for systems of linear equations

The authors present data-flow solutions on a pipeline of transputers for banded and dense systems of linear equations using Gauss elimination and the Gauss-Jordan method, respectively. These implementations, written in occam, are especially effective when there is a continuous supply of right-hand sides to be solved with the same coefficient matrix. Attention is paid to both load balancing and resource handling within the processor elements of the pipeline. When solving multiple right-hand sides, floating-point efficiency levels on 32-processor implementations range from 110% (for dense systems) down to 90% (for banded systems), where 100% represents the peak performance attainable from a single transputer applied to the same problem (effectively back-to-back floating-point operations on data in external memory). Some conclusions are drawn on efficiency issues arising from state-of-the-art massively parallel supercomputers.     

On the solution of interval linear systems

In the literature efficient algorithms have been described for calculating guaranteed inclusions for the solution of a number of standard numerical problems [3,4,8,11,12,13]. The inclusions are given by means of a set containing the solution. In [12,13] this set is calculated using an affine iteration which is stopped when a nonempty and compact set is mapped into itself. For exactly given input data (point data) it has been shown that this iteration stops if and only if the iteration matrix is convergent (cf. [13]). In this paper we give a necessary and sufficient stopping criterion for the above mentioned iteration for interval input data and interval operations. Stopping is equivalent to the fact that the algorithm presented in [12] for solving interval linear systems computes an inclusion of the solution. An algorithm given by Neumaier is discussed and an algorithm is proposed combining the advantages of our algorithm and a modification of Neumaier's. The combined algorithm yields tight bounds for input intervals of small and large diameter. Using a paper by Jansson [6,7] we give a quite different geometrical interpretation of inclusion methods. It can be shown that our inclusion methods are optimal in a specified geometrical sense. For another class of sets, for standard simplices, we give some interesting examples.     

Computing the frequency response of linear systems with parametric perturbation

The problem of computing the frequency response of linear systems with parametric perturbation is addressed. Under the assumption that the coefficients of the system transfer function depend on the perturbation parameters in a linear manner, we provide results for plotting the frequency response of the perturbed transfer function. These results are useful in determining the H∞ norm, gain margin and phase margin and in improving the diagonal dominance of multi-input multi-out-put uncertain systems. An illustrative example is provided to demonstrate the results.     

Sequential monte carlo techniques for the solution of linear systems

Given alinear system Ax=b, wherex is anm-vector,direct numerical methods, such as Gaussian elimination, take timeO(m ³) to findx. Iterative numerical methods, such as the Gauss-Seidel method or SOR, reduce the system to the formx=a+Hx, whence and then apply the iterationsx ₀=a,x _s+1=a+Hx _s , until sufficient accuracy is achieved; this takes timeO(m ²) per iteration. They generate the truncated sums The usualplain Monte Carlo approach uses independent random walks, to give an approximation to the truncated sumx _s , taking timeO(m) per random step. Unfortunately, millions of random steps are typically needed to achieve reasonable accuracy (say, 1% r.m.s. error). Nevertheless, this is what has had to be done, ifm is itself of the order of a million or more.The alternative presented here, is to apply a sequential Monte Carlo method, in which the sampling scheme is iteratively improved. Simply put, ifx=y+z, wherey is a current estimate ofx, then its correction,z, satisfiesz=d+Hz, whered=a+Hy–y. At each stage, one uses plain Monte Carlo to estimatez, and so, the new estimatey. If the sequential computation ofd is itself approximated, numerically or stochastically, then the expected time for this process to reach a given accuracy is againO(m) per random step; but the number of steps is dramatically reduced [improvement factors of about 5,000, 26,000, 550, and 1,500 have been obtained in preliminary tests].     

Robust stability analysis of linear systems with parametric uncertainty

This article is concerned with the problem of robust stability analysis of linear systems with uncertain parameters. By constructing an equivalent system with positive uncertain parameters and using the properties of these parameters, a new stability analysis condition is derived. Due to making use of the properties of uncertain parameters, the new proposed method has potential to give less conservative results than the existing approaches. A numerical example is given to illustrate the effectiveness of the proposed method.     

Parallel algorithms for the solution of certain large sparse linear systems

A couple of approximate inversion techniques are presented which provide a parallel enhancement to several iterative methods for solving linear systems arising from the discretization of boundary value problems. In particular, the Jacobi, Gauss‐Seidel, and successive overrelaxation methods can be improved substantially in a parallel environment by the extensions considered. A special case convergence proof is presented. The use of our approximate inverses with the preconditioned conjugate gradient method is examined and comparisons are made with some recently proposed algorithms in this area that also employ approximate inverses. The methods considered are compared under sequential and parallel hardware assumptions.     

Unified parametric approaches for high-order integral observer design for matrix second-order linear systems

A type of high-order integral observers for matrix second-order linear systems is proposed on the basis of generalized eigenstructure assignment via unified parametric approaches. Through establishing two general parametric solutions to this type of generalized matrix second-order Sylvester matrix equations, two unified complete parametric methods for the proposed observer design problem are presented. Both methods give simple complete parametric expressions for the observer gain matrices. The first one mainly depends on a series of singular value decompositions, and is thus numerically simple and reliable; the second one utilizes the right factorization of the system, and allows eigenvalues of the error system to be set undetermined and sought via certain optimization procedures. A spring-mass-dashpot system is utilized to illustrate the design procedure and show the effect of the proposed approach.     

Robust iterative learning control for linear systems with multiple time-invariant parametric uncertainties

This article presents a novel robust iterative learning control algorithm (ILC) for linear systems in the presence of multiple time-invariant parametric uncertainties.The robust design problem is formulated as a min–max problem with a quadratic performance criterion subject to constraints of the iterative control input update. Then, we propose a new methodology to find a sub-optimal solution of the min–max problem. By finding an upper bound of the worst-case performance, the min–max problem is relaxed to be a minimisation problem. Applying Lagrangian duality to this minimisation problem leads to a dual problem which can be reformulated as a convex optimisation problem over linear matrix inequalities (LMIs). An LMI-based ILC algorithm is given afterward and the convergence of the control input as well as the system error are proved. Finally, we apply the proposed ILC to a generic example and a distillation column. The numerical results reveal the effectiveness of the LMI-based algorithm.     

Parallel solution of arbitrarily sparse linear systems

A parallel algorithm for the iterative solution of sparse linear systems is presented. This algorithm is shown to be efficient for arbitrarily sparse matrices. Analysis of this algorithm suggests that a network of Processing Elements [PE's] equal in number to the number R of non-zero matrix entries is particularly useful. If this collection of PE's is interconnected by a message-passing, or a synchronous, communication network which is fast enough, the iteration time grows as the logarithm of the number of PE's. A comparison with earlier work, which suggested that only √R PE's are useful for this task, is also presented. The performance of three proposed networks of PE's on this algorithm is analyzed. The networks investigated all have the topology of the Cube Connected Cycles [CCC] graph, and all employ the same silicon technology, and the same number of chips and wires, and hence all should cost the same. One, the Boolean Vector Machine [BVM], employs 2²⁰ bit-serial PE's implemented in 4096 VLSI chips; the other two networks use different 32-bit parallel microprocessors, and a 32-bit parallel CCC to interconnect 2048 2-chip processors. One of the microprocessors is assumed to deliver about 1 Mflop, while the other is assumed to deliver 32 Mflops per PE. The comparison indicates that the BVM network would have superior performance to both of these parallel networks.     

Analysis of a parallel solution method for tridiagonal linear systems

We analyse an alternative decomposition for a tridiagonal matrix which has the property that the decomposition as well as the subsequent solution process can be done in two parallel parts. This decomposition is equivalent to the two-sided Gaussian elimination algorithm that has been discussed by Babuska. In the context of parallel computing a similar approach has been suggested by Joubert and Cloete. The computational complexity of this alternative decomposition is the same as for the standard decomposition and a remarkable aspect is that it often leads to slightly more accurate solutions than the standard process does. The algorithm can be combined with recursive doubling or cyclic reduction in order to increase the degree of parallelism and vectorizability.