Systolic array implementation of some iterative algorithms for solving systems of linear algebraic equations

The paper elucidates the internal properties of some iterative linear algebra algorithms through transformation of their lattice graphs.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 145–158, September–October, 1992.     

Solving systems of sparse linear equations

We present in this work stable methods for solving sparse linear equations systems based on the LU factorizations and its updating when columns and rows of the system matrix are added, deleted or modified.     

Solving systems of large dense linear equations

Many mathematical models of physical phenomena lead to solving dense systems of linear equations. As the models are refined, the order of these problems increases, usually beyond the capacity of the computer to contain the problem in central memory. This paper reviews block Gaussian elimination, which can be used to solve these problems efficiently. An implementation that achieves the maximum sustainable computational rate on a wide range of computers is given. The question of how large of a problem is currently feasible is addressed.     

Solving algebraic equations on a microcomputer

Equation-solving programs for microcomputers make the numerical solution of algebraic equations an easy task. It is no longer necessary to learn or to program algorithms for the solution of many different types of equations. A single equation or a set of simultaneous equations may simply be entered into the computer and numerically solved for unknowns without concern as to whether the equations are linear or non-linear. Several examples of possible applications of equation-solving programs are discussed. Solution times for these examples are given for SEQS on the Apple II and Macintosh computers. The example sets of equations, which include chemical equilibrium and enzyme kinetics problems, have been chosen to demonstrate important aspects of the uses and limitations of equation solving. The four examples discussed are: a two-compartment pharmacokinetic model, citric acid ionization in aqueous solution, an enzyme inhibition model, and an example of the application of an equation-solving program in doing a simple non-linear regression problem.     

Solving systems of algebraic equations by a general elimination method

A method of factorisation of a U-resultant into linear factors is given. Using this method we can obtain solutions and their multiplicities of a system of algebraic equations, provided the system of algebraic equations has finitely many solutions. We directly calculate a matrix à which gives all solutions of the system by using a Gröbner basis of the ideal generated by the polynomials of the system of algebraic equations.     

Solving systems of linear equations with Boolean variables

The paper presents a method to solve systems of linear equations with Boolean variables, which implements an enumeration strategy. Necessary and sufficient conditions for the existence of feasible plans are formalized. A formal procedure to analyze subsets of alternatives is described. The structure of an algorithm that possesses the property of completeness is presented. Special cases of systems of equations are examined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 42–50, September–October 2006.     

Solution of systems of linear algebraic equations with preliminary flattening

A method of improving computing properties of matrices of systems of linear algebraic equations is considered. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 144–149, September–October, 1999.     

Quantitative criterion of conditioning for systems of linear algebraic equations

Conventional conditioning criteria are shown to be invalid for estimating the accuracy of a numerical calculation for systems of linear algebraic equations. A new conditioning criterion is proposed, quantitatively describing the actual loss of decimal digits in calculations. The adequacy of this criterion is confirmed by examples of numerical calculations. Conditioning criteria have been obtained for some types of linear systems arising in important applied problems, in particular, in the difference solution of differential or integral equations.     

Solving systems of algebraic and differential equations by second-order difference modulation

We consider algorithms that solve some systems of algebraic and differential equations using optimized modulation of functions by second difference quanta. These algorithms provide an integrated technique for tackling various issues of organization of special-purpose computations.Translated from Kibernetika, No. 2, pp. 65–72, March–April, 1989.     

Solving tridiagonal systems of linear equations on the IBM 3090 VF

Cyclic reduction, originally proposed by Hockney and Golub, is the most popular algorithm for solving tridiagonal linear systems on SIMD-type computers like CRAY-1 or CDC CYBER 205. That algorithm seems to be the adequate one for the IBM 3090 VF (uni-processor), too, although the overall expected speedup over Gaussian elimination, specialized for tridiagonal systems, is not as high as for the CRAY-1 or the CYBER 205. That is because the excellent scalar speed of the IBM 3090 makes its vector-to-scalar speed ratio relatively moderate.

The idea of the cyclic reduction algorithm can be generalized and modified in various directions. A polyalgorithm can be derived which takes into account much better the given architecture of the IBM 3090 VF than the ‘pure’ cyclic reduction algorithm as described for instance by Kershaw. This is mainly achieved by introducing more locality into the formulae. For large systems of equations the well-known cache problems are prevented.     

Methods for obtaining reliable solutions to systems of linear algebraic equations

The general case of incompatible systems of linear algebraic equations with matrices of arbitrary rank is considered. The estimates for total errors are obtained for all the considered cases under conditions of approximate data. In solving systems by iterative methods, the conditions of completion of iterative processes that provide solutions with a prescribed accuracy are considered in detail. A special attention is given to the solution of incompatible systems with symmetric positive semidefinite matrices by the method of three-stage regularization in which an algorithm for choosing the regularization parameter is proposed that allows finding solutions with the required accuracy.     

Solving large systems of linear ordinary differential equations on a vector computer

This paper is concerned with the development, analysis and implementation on a computer consisting of two vector processors of the arithmetic mean method for solving numerically large sparse sets of linear ordinary differential equations. This method has second-order accuracy in time and is stable.

The special class of differential equations that arise in solving the diffusion problem by the method of lines is considered. In this case, the proposed method has been tested on the CRAY X-MP/48 utilizing two CPUs. The numerical results are largely in keeping with the theory; a speedup factor of nearly two is obtained.     

Probabilistic properties of systems of random linear equations over finite algebraic structures

Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 100–105, May–June, 1993.     

Solving large linear algebraic systems in the context of integrable non-abelian Laurent ODEs

The paper reports on a computer algebra program LSSS (Linear Selective Systems Solver) for solving linear algebraic systems with rational coefficients. The program is especially efficient for very large sparse systems that have a solution in which many variables take the value zero. The program is applied to the symmetry investigation of a non-abelian Laurent ODE introduced recently by M. Kontsevich. The computed symmetries confirmed that a Lax pair found for this system earlier generates all first integrals of degree at least up to 14.     

Solving sparse linear systems of equations using the modified digraph approach

We propose two different algorithms which depend on the modified digraph approach for solving a sparse system of linear equations. The main feature of the algorithms is that the solution of a sparse system of linear equations can be expressed exactly if all the non-zero entries, including the right-hand side, are integers and if none of the products exceeds the size of the largest integer that can be represented in the arithmetic of the computer used. The implementation of the algorithms is tested on five problems. The results are compared with those obtained using an algorithm proposed earlier. It is shown that the efficiency with which a sparse system of linear equations can be analysed by a digital computer using the proposed modified digraph approach as a tool depends mainly on the efficiency with which semifactors and k-semifactors are generated. Finally, in our implementation of the proposed algorithms, the input sparse matrix is stored using a row-ordered list of a modified uncompressed storage scheme.