Concise row-pruning algorithm to invert a matrix

Presented here, in a vector formulation, is an O(mn2) direct concise algorithm that prunes/identifies the linearly dependent (ld) rows of an arbitrary m X n matrix A and computes its reflexive type minimum norm inverse A(mr)-, which will be the true inverse A-1 if A is nonsingular and the Moore-Penrose inverse A+ if A is full row-rank. The algorithm, without any additional computation, produces the projection operator P = (I - A(mr)- A) that provides a means to compute any of the solutions of the consistent linear equation Ax = b since the general solution may be expressed as x = A(mr)+b + Pz, where z is an arbitrary vector. The rank r of A will also be produced in the process. Some of the salient features of this algorithm are that (i) the algorithm is concise, (ii) the minimum norm least squares solution for consistent/inconsistent equations is readily computable when A is full row-rank (else, a minimum norm solution for consistent equations is obtainable), (iii) the algorithm identifies ld rows, if any, and reduces concerned computation and improves accuracy of the result, (iv) error-bounds for the inverse as well as the solution x for Ax = b are readily computable, (v) error-free computation of the inverse, solution vector, rank, and projection operator and its inherent parallel implementation are straightforward, (vi) it is suitable for vector (pipeline) machines, and (vii) the inverse produced by the algorithm can be used to solve under-/overdetermined linear systems.

Variable Elimination in Linear Constraints

Gauss and Fourier have together provided us with the essential techniques for symbolic computation with linear arithmetic constraints over the reals and the rationals. These variable elimination techniques for linear constraints have particular significance in the context of constraint logic programming languages that have been developed in recent years. Variable elimination in linear equations (Guassian Elimination) is a fundamental technique in computational linear algebra and is therefore quite familiar to most of us. Elimination in linear inequalities (Fourier Elimination), on the other hand, is intimately related to polyhedral theory and aspects of linear programming that are not quite as familiar. In addition, the high complexity of elimination in inequalities has forces the consideration of intricate specializations of Fourier's original method. The intent of this survey article is to acquaint the reader with these connections and developments. The latter part of the article dwells on the thesis that variable elimination in linear constraints over the reals extends quite naturally to constraints in certain discrete domains.

Matrix method for eigenstructure assignment - The multi-input case with application

The eigenvalue and eigenstructure assignment procedure has found application in a wide variety of control problems. In this paper a method for assigning eigenstructure to a linear time invariant multi-input system is proposed. The algorithm determines a matrix that has eigenvalues and eigenvectors at the desired locations. It is obtained from the knowledge of the open-loop system and the desired eigenstructure. Solution of the matrix equation, involving unknown controller gams, open-loop system matrices, and desired eigenvalues and eigenvectors, results hi the state feedback controller. The proposed algorithm requires the closed-loop eigenvalues to be different from those of the open-loop case. This apparent constraint can easily be overcome by a negligible shift in the values. Application of the procedure is illustrated through the offset control of a satellite supported, from an orbiting platform, by a flexible tether.

Matrix method for eigenvalue assignment: The single input case

The eigenvalue assignment/pole placement procedure has found application in a wide variety of control problems. The associated literature is rather extensive with a number of techniques discussed to that end. In this paper a method for assigning eigenvalues to a Linear Time Invariant (LTI) single input system is proposed. The algorithm determines a matrix, which has eigenvalues at the desired locations. It is obtained from the knowledge of the open-loop system and the desired eigenvalues. Solution of the matrix equation, involving unknown controller gains, open-loop system matrices and desired eigenvalues, results in the state feedback controller. The proposed algorithm requires the closed-loop eigenvalues to be different from those of the open-loop case. This apparent constraint is easily overcome by a negligible shift in the values. Two examples are considered to verify the proposed algorithm. The first one pertains to the in-plane libration of a Tethered Satellite System (TSS) while the second is concerned with control of the short period dynamics of a flexible airplane. Finally, the method is extended to determine the Controllability Grammian, corresponding to the specified closed-loop eigenvalues, without computing the controller gains.

Matrix method for eigenstructure assignment - The multi-input case with application

The eigenvalue and eigenstructure assignment procedure has found application in a wide variety of control problems. In this paper a method for assigning eigenstructure to a Linear time invariant multi-input system is proposed. The algorithm determines a matrix that has eigenvalues and eigenvectors at the desired locations. It is obtained from the knowledge of the open-loop system and the desired eigenstructure. solution of the matrix equation, involving unknown controller gains, open-loop system matrices, and desired eigenvalues and eigenvectors, results in the state feedback controller. The proposed algorithm requires the closed-loop eigenvalues to be different from those of the open-loop case. This apparent constraint can easily be overcome by a negligible shift in the values. Application of the procedure is illustrated through the offset control of a satellite supported, from an orbiting platform, by a flexible tether,

Matrix method for eigenvalue assignment: The single input case

The eigenvalue assignment/pole placement procedure has found application in a wide variety of control problems. The associated literature is rather extensive with a number of techniques discussed to that end. In this paper a method for assigning eigenvalues to a Linear Time Invariant (LTI) single input system is proposed. The algorithm determines a matrix, which has eigenvalues at the desired locations. It is obtained from the knowledge of the open-loop system and the desired eigenvalues. Solution of the matrix equation, involving unknown controller gains, open-loop system matrices and desired eigenvalues, results in the state feedback controller. The proposed algorithm requires the closed-loop eigenvalues to be different from those of the open-loop case. This apparent constraint is easily overcome by a negligible shift in the values. Two examples are considered to verify the proposed algorithm. The first one pertains to the in-plane libration of a Tethered Satellite System (TSS) while the second is concerned with control of the short period dynamics of a flexible airplane. Finally, the method is extended to determine the Controllability Grammian, corresponding to the specified closed-loop eigenvalues, without computing the controller gains.

Dynamic stiffness matrix of a general cable element

A computational scheme for determining the dynamic stiffness coefficients of a linear, inclined, translating and viscously/hysteretically damped cable element is outlined. Also taken into account is the coupling between inplane transverse and longitudinal forms of cable vibration. The scheme is based on conversion of the governing set of quasistatic boundary value problems into a larger equivalent set of initial value problems, which are subsequently numerically integrated in a spatial domain using marching algorithms. Numerical results which bring out the nature of the dynamic stiffness coefficients are presented. A specific example of random vibration analysis of a long span cable subjected to earthquake support motions modeled as vector gaussian random processes is also discussed. The approach presented is versatile and capable of handling many complicating effects in cable dynamics in a unified manner.

FIR system identification based on subspaces of a higher order cumulant matrix

A new linear algebraic approach for identification of a nonminimum phase FIR system of known order using only higher order (>2) cumulants of the output process is proposed. It is first shown that a matrix formed from a set of cumulants of arbitrary order can be expressed as a product of structured matrices. The subspaces of this matrix are then used to obtain the parameters of the FIR system using a set of linear equations. Theoretical analysis and numerical simulation studies are presented to characterize the performance of the proposed methods.

The Gaussian Toeplitz matrix

An analytical expression for the LL(T) decomposition for the Gaussian Toeplitz matrix with elements T(ij) = [1/(2-pi)1/2-sigma] exp[-(i - j)2/2-sigma-2] is derived. An exact expression for the determinant and bounds on the eigenvalues follows. An analytical expression for the inverse T-1 is also derived.

Graphics Processing Units for the Real-time Linear Elastostatic Simulation of Liver

Biomedical engineering solutions like surgical simulators need High Performance Computing (HPC) to achieve real-time performance. Graphics Processing Units (GPUs) offer HPC capabilities at low cost and low power consumption. In this work, it is demonstrated that a liver which is discretized by about 2500 finite element nodes, can be graphically simulated in realtime, by making use of a GPU. Present work takes into consideration the time needed for the data transfer from CPU to GPU and back from GPU to CPU. Although behaviour of liver is very complicated, present computer simulation assumes linear elastostatics. One needs to use the commercial software ANSYS to obtain the global stiffness matrix of the liver. Results show that GPUs are useful for the real-time graphical simulation of liver, which in turn is needed in simulators that are used for training surgeons in laparoscopic surgery. Although the computer simulation should involve rendering also, neither rendering, nor the time needed for rendering and displaying the liver on a screen, is considered in the present work. The present work is just a demonstration of a concept; the concept is not really implemented and validated. Future work is to develop software which can accomplish real-time and very realistic graphical simulation of liver, with rendered image of liver on the screen changing in real-time according to the position of the surgical tool tip approximated as the mouse cursor in 3D.

Solving linear programming problems exactly

A linear programming problem in an inequality form having a bounded solution is solved error-free using an algorithm that sorts the inequalities, removes the redundant ones, and uses the p-adic arithmetic. (C) Elsevier Science Inc., 1997

Density-matrix renormalization-group study of low-lying excitations of polyacene within a Pariser-Parr-Pople model

We have carried out symmetrized density-matrix renormalization-group calculations to study the nature of excited states of long polyacene oligomers within a Pariser-Parr-Pople Hamiltonian. We have used the C-2 symmetry, the electron-hole symmetry, and the spin parity of the system in our calculations. We find that there is a crossover in the lowest dipole forbidden two-photon state and the lowest dipole allowed excited state with size of the oligomer. In the long system limit, the two-photon state lies below the lowest dipole allowed excited state. The triplet state lies well below the two-photon state and energetically does not correspond to its description as being made up of two triplets. These results are in agreement with the general trends in linear conjugated polymers. However, unlike in linear polyenes wherein the two-photon state is a localized excitation, we find that in polyacenes, the two-photon excitation is spread out over the system. We have doped the systems with a hole and an electron and have calculated the charge excitation gap. Using the charge gap and the optical gap, we estimate the binding energy of the 1(1)B(-) exciton to be 2.09 eV. We have also studied doubly doped polyacenes and find that the bipolaron in these systems, to be composed of two separated polarons, as indicated by the calculated charge-density profile and charge-charge correlation function. We have studied bond orders in various states in order to get an idea of the excited state geometry of the system. We find that the ground state, the triplet state, the dipole allowed state, and the polaron excitations correspond to lengthening of the rung bonds in the interior of the oligomer while the two-photon excitation corresponds to the rung bond lengths having two maxima in the system.

Quadratic Lyapunov functions for linear systems Journal

The paper deals with the existence of a quadratic Lyapunov function V = x′P(t)x for an exponentially stable linear system with varying coefficients described by the vector differential equation S0305004100044777_inline1 The derivative dV/dt is allowed to be strictly semi-(F) and the locus dV/dt = 0 does not contain any arc of the system trajectory. It is then shown that the coefficient matrix A(t) of the exponentially stable sy

A Fast Linear Separability Test by Projection of Positive Points on Subspaces

A geometric and non parametric procedure for testing if two finite set of points are linearly separable is proposed. The Linear Separability Test is equivalent to a test that determines if a strictly positive point h > 0 exists in the range of a matrix A (related to the points in the two finite sets). The algorithm proposed in the paper iteratively checks if a strictly positive point exists in a subspace by projecting a strictly positive vector with equal co-ordinates (p), on the subspace. At the end of each iteration, the subspace is reduced to a lower dimensional subspace. The test is completed within r ≤ min(n, d + 1) steps, for both linearly separable and non separable problems (r is the rank of A, n is the number of points and d is the dimension of the space containing the points). The worst case time complexity of the algorithm is O(nr3) and space complexity of the algorithm is O(nd). A small review of some of the prominent algorithms and their time complexities is included. The worst case computational complexity of our algorithm is lower than the worst case computational complexity of Simplex, Perceptron, Support Vector Machine and Convex Hull Algorithms, if d

Topological analysis of general linear networks

A new method of network analysis, a generalization in several different senses of existing methods and applicable to all networks for which a branch-admittance (or impedance) matrix can be formed, is presented. The treatment of network determinants is very general and essentially four terminal rather than three terminal, and leads to simple expressions based on trees of a simple graph associated with the network and matrix, and involving products of low-order, usually(2 times 2)determinants of tree-branch admittances, in addition to tree-branch products as in existing methods. By comparison with existing methods, the total number of trees and of tree pairs is usually considerably reduced, and this fact, together with an easy method of tree-pair sign determination which is also presented, makes the new method simpler in general. The method can be very easily adapted, by the use of infinite parameters, to accommodate ideal transformers, operational amplifiers, and other forms of network constraint; in fact, is thought to be applicable to all linear networks.