On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

A new algorithm for parallel solution of linear equations

Abstract is not available.

Iterative solution of a class of linear equations with application to reconstruction of three-dimensional object arrays

An iterative algorithm baaed on probabilistic estimation is described for obtaining the minimum-norm solution of a very large, consistent, linear system of equations AX = g where A is an (m times n) matrix with non-negative elements, x and g are respectively (n times 1) and (m times 1) vectors with positive components.

Finite field computation technique for exact solution of systems of linear equations and interval linear programming problems

An error-free computational approach is employed for finding the integer solution to a system of linear equations, using finite-field arithmetic. This approach is also extended to find the optimum solution for linear inequalities such as those arising in interval linear programming probloms.

An integer arithmetic method to compute generalized matrix inverse and solve linear equations exactly

An algorithm that uses integer arithmetic is suggested. It transforms anm ×n matrix to a diagonal form (of the structure of Smith Normal Form). Then it computes a reflexive generalized inverse of the matrix exactly and hence solves a system of linear equations error-free.

Nonnegative integral solution of linear equations

A method to obtain a nonnegative integral solution of a system of linear equations, if such a solution exists is given. The method writes linear equations as an integer programming problem and then solves the problem using a combination of artificial basis technique and a method of integer forms.

Points-to Analysis as a System of Linear Equations

We propose a novel formulation of the points-to analysis as a system of linear equations. With this, the efficiency of the points-to analysis can be significantly improved by leveraging the advances in solution procedures for solving the systems of linear equations. However, such a formulation is non-trivial and becomes challenging due to various facts, namely, multiple pointer indirections, address-of operators and multiple assignments to the same variable. Further, the problem is exacerbated by the need to keep the transformed equations linear. Despite this, we successfully model all the pointer operations. We propose a novel inclusion-based context-sensitive points-to analysis algorithm based on prime factorization, which can model all the pointer operations. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that our approach is competitive to the state-of-the-art algorithms. With an average memory requirement of mere 21MB, our context-sensitive points-to analysis algorithm analyzes each benchmark in 55 seconds on an average.

Non-linear flapping vibrations of rotating blades

The non-linear equations of motion of a rotating blade undergoing extensional and flapwise bending vibration are derived, including non-linearities up to O (ε3). The strain-displacement relationship derived is compared with expressions derived by earlier investigators and the errors and the approximations made in some of those are brought out. The equations of motion are solved under the inextensionality condition to obtain the influence of the amplitude on the fundamental flapwise natural frequency of the rotating blade. It is found that large finite amplitudes have a softening effect on the flapwise frequency and that this influence becomes stronger at higher speeds of rotation.

Non-linear flapping vibrations of rotating blades

The non-linear equations of motion of a rotating blade undergoing extensional and flapwise bending vibration are derived, including non-linearities up to O (ε3). The strain-displacement relationship derived is compared with expressions derived by earlier investigators and the errors and the approximations made in some of those are brought out. The equations of motion are solved under the inextensionality condition to obtain the influence of the amplitude on the fundamental flapwise natural frequency of the rotating blade. It is found that large finite amplitudes have a softening effect on the flapwise frequency and that this influence becomes stronger at higher speeds of rotation.

Theory of Non-linear Waves in Multi-dimensions: with Special Reference to Surface Water Waves

The surface water waves are "modal" waves in which the "physical space" (t, x, y, z) is the product of a propagation space (t, x, y) and a cross space, the z-axis in the vertical direction. We have derived a new set of equations for the long waves in shallow water in the propagation space. When the ratio of the amplitude of the disturbance to the depth of the water is small, these equations reduce to the equations derived by Whitham (1967) by the variational principle. Then we have derived a single equation in (t, x, y)-space which is a generalization of the fourth order Boussinesq equation for one-dimensional waves. In the neighbourhood of a wave froat, this equation reduces to the multidimensional generalization of the KdV equation derived by Shen & Keller (1973). We have also included a systematic discussion of the orders of the various non-dimensional parameters. This is followed by a presentation of a general theory of approximating a system of quasi-linear equations following one of the modes. When we apply this general method to the surface water wave equations in the propagation space, we get the Shen-Keller equation.

A generalised cole-hopf transformation for nonlinear parabolic and hyperbolic equations

The Cole-Hopf transformation has been generalized to generate a large class of nonlinear parabolic and hyperbolic equations which are exactly linearizable. These include model equations of exchange processes and turbulence. The methods to solve the corresponding linear equations have also been indicated.La transformation de Cole et de Hopf a été généralisée en vue d'engendrer une classe d'équations nonlinéaires paraboliques et hyperboliques qui peuvent être rendues linéaires de façon exacte. Elles comprennent des équations modèles de procédés d'échange et de turbulence. Les méthodes pour résoudre les équations linéaires correspondantes ont également été indiquées.

Non-linear Dynamic Analysis of a Piezoelectrically Actuated Flapping Wing

An energy method is used in order to derive the non-linear equations of motion of a smart flapping wing. Flapping wing is actuated from the root by a PZT unimorph in the piezofan configuration. Dynamic characteristics of the wing, having the same size as dragonfly Aeshna Multicolor, are analyzed using numerical simulations. It is shown that flapping angle variations of the smart flapping wing are similar to the actual dragonfly wing for a specific feasible voltage. An unsteady aerodynamic model based on modified strip theory is used to obtain the aerodynamic forces. It is found that the smart wing generates sufficient lift to support its own weight and carry a small payload. It is therefore a potential candidate for flapping wing of micro air vehicles.

A bicharacteristic formulation of the ideal MHD equations

On a characteristic surface Omega of a hyperbolic system of first-order equations in multi-dimensions (x, t), there exits a compatibility condition which is in the form of a transport equation along a bicharacteristic on Omega. This result can be interpreted also as a transport equation along rays of the wavefront Omega(t) in x-space associated with Omega. For a system of quasi-linear equations, the ray equations (which has two distinct parts) and the transport equation form a coupled system of underdetermined equations. As an example of this bicharacteristic formulation, we consider two-dimensional unsteady flow of an ideal magnetohydrodynamics gas with a plane aligned magnetic field. For any mode of propagation in this two-dimensional flow, there are three ray equations: two for the spatial coordinates x and y and one for the ray diffraction. In spite of little longer calculations, the final four equations (three ray equations and one transport equation) for the fast magneto-acoustic wave are simple and elegant and cannot be derived in these simple forms by use of a computer program like REDUCE.

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.