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.     

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 systems of linear algebraic equations on array processors

Conclusion We have proposed a modification of the orthogonal Faddeev method [6] for solving various SLAE and also for inversion and pseudoinversion of matrices. The proposed version of the method relies on Householder and Jordan-Gauss methods and its computational complexity is approximately half that of [6]. This method, combined with the matrix-graph method [9] of formalized SPPC structure design, has been applied to synthesize a number of AP architectures that efficiently implement the proposed method. Goal-directed isomorphic and homeomorphic transformations of the LFG of the original algorithm (5) lead to a one-dimensional (linear) AP of fixed size, with minimum hardware and time costs and with minimized input-output channel width. The proposed algorithm (5) has been implemented using a 4-processor AP, with Motorola DSP96002 processors as PEs (Fig. 7). Application of the algorithm (5) to solve an SLAE with a coefficient matrixA withM=N=100 and one righthand side on this AP produced a load factor η=0.82; for inversion of the matrixA of the same size we achieved η=0.77. The sequence of transformations and the partitioning of a trapezoidal planaer LFG described in this article have been generalized to the case of other LA algorithms decribed by triangular planar LFGs and executed on linear APs. It is shown that the AP structures synthesized in this study execute all the above-listed algorithms no less efficiently than the modified Faddeev algorithm, provided their PEs are initially tuned to the execution of the corresponding operators. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 47–66, March–April, 1996.     

Solving equations via the trust region and its application to a class of stochastic linear complementarity problems

Equations with box constraints are applied in many fields, for example the complementarity problem. After studying the existing methods, we find that quadratic convergence of majority algorithms is based on the solvability of the equations. But whether the equations are solvable is previously unknown. So, it is necessary to design an algorithm which has fast quadratic convergence. The quadratic convergence does not depend on the solvability of the equations. In this paper, we propose a new method for solving equations. The global and local quadratic convergence of the proposed algorithm are established under some suitable assumptions. We apply the proposed algorithm to a class of stochastic linear complementarity problems. Numerical results show that our method is valid.     

LS-SVM approximate solution to linear time varying descriptor systems

This paper discusses a numerical method based on Least Squares Support Vector Machines (LS-SVMs) for solving linear time varying initial and boundary value problems in Differential Algebraic Equations (DAEs). The method generates a closed form (model-based) approximate solution. The results of numerical experiments on different systems with index from $0$ to $3$, are presented and compared with analytic solutions to confirm the validity and applicability of the proposed method.     

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.     

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.     

Stabilisation of time-varying linear systems via Lyapunov differential equations

This article studies stabilisation problem for time-varying linear systems via state feedback. Two types of controllers are designed by utilising solutions to Lyapunov differential equations. The first type of feedback controllers involves the unique positive-definite solution to a parametric Lyapunov differential equation, which can be solved when either the state transition matrix of the open-loop system is exactly known, or the future information of the system matrices are accessible in advance. Different from the first class of controllers which may be difficult to implement in practice, the second type of controllers can be easily implemented by solving a state-dependent Lyapunov differential equation with a given positive-definite initial condition. In both cases, explicit conditions are obtained to guarantee the exponentially asymptotic stability of the associated closed-loop systems. Numerical examples show the effectiveness of the proposed approaches.     

Condition numbers for linear systems and Kronecker product linear systems with multiple right-hand sides

In this paper we investigate linear systems with multiple right-handed sides in the form of AX=B and (A ? B)X=C. We derive normwise, mixed and componentwise condition numbers for these linear systems. Examples are given to evaluate the tightness of the first-order perturbation bounds.     

Solving parametric fuzzy systems of linear equations by a nonlinear programming method

Linear systems of equations, with uncertainty on the parameters, play a major role in various problems in economics and finance. In this paper parametric fuzzy linear systems of the general form A ₁ x + b ₁ = A ₂ x + b ₂, with A ₁, A ₂, b ₁ and b ₂ matrices with fuzzy elements, are solved by means of a nonlinear programming method. The relation between this methodology and the algorithm proposed in Muzzioli and Reynaerts [(2006) Fuzzy Sets and Systems, in press] is highlighted. The methodology is finally applied to an economic and a financial problem.     

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.     

Conjugate gradient solution of linear equations

The conjugate gradient method is an ingenious method for iterative solution of sparse linear equations. It is now a standard benchmark for parallel scientific computing. In the author's opinion, the apparent mystery of this method is largely due to the inadequate way in which it is presented in textbooks. This tutorial explains conjugate gradients by deriving the computational steps from elementary mathematical concepts. The computation is illustrated by a numerical example and an algorithmic outline. © 1998 John Wiley & Sons, Ltd.     

Solving systems of polynomial equations

Geometric and solid modelling deal with the representation and manipulation of physical objects. Currently most geometric objects are formulated in terms of polynomial equations, thereby reducing many application problems to manipulating polynomial systems. Solving systems of polynomial equations is a fundamental problem in these geometric computations. The author presents an algorithm for solving polynomial equations. The combination of multipolynomial resultants and matrix computations underlies this efficient, robust and accurate algorithm     

Solving a system of linear equations: From centralized to distributed algorithms

For a wide range of control engineering applications, the problem of solving a system of linear equations is often encountered and has been well studied. Traditionally, this problem has been mainly solved in a centralized manner. However, for applications related to large-scale complex networked systems, centralized algorithms are often subjected to some practical issues due to limited computational power and communication bandwidth. As a promising and viable alternative, distributed algorithms can effectively address the issues associated with centralized algorithms by solving the problem efficiently in a multi-agent setting that accords with the distributed nature of networked systems. Distributed algorithms decompose the entire problem into many sub-problems that are solved by individual agents in a cooperative manner. In this survey paper, we provide a detailed overview of the state of the art relevant to distributed algorithms for solving a system of linear equations. We will first review basic distributed algorithms including both discrete-time and continuous-time algorithms. Then we will discuss the extended algorithms to achieve communication efficiency. Furthermore, we will also introduce distributed algorithms to obtain the minimum-norm solution for a system of linear equations with multiple solutions, as well as the least-squares solution when there is no solution. Finally, the relationship of distributed algorithms for solving a system of linear equations to the existing distributed optimization algorithms is discussed.     

Semiglobal stabilization of saturated linear systems via multiple parametric Lyapunov equations

This paper investigates the problem of semiglobal stabilization with guaranteed flexible pole placement for saturated linear systems. To retain the advantages of the parametric Lyapunov equation, matrix‐partitioning idea is used to derive a new pole shift lemma. Starting from system matrix transformations, a recursive algorithm is proposed to shift every eigenvalue of a linear system separately without mode decomposition in each step. A new method introducing various parameters to every Lyapunov equation in each step is presented. As an application, the semiglobal stabilization with guaranteed flexible pole placement for saturated linear systems can be achieved by this method. Finally, its effectiveness and advantages are demonstrated via a simulation example. Copyright © 2013 John Wiley & Sons, Ltd.     

Solving systems of equations with multi-stage Monte Carlo optimization

Dantzig (1963), Orchard-Hays (1968) and other pioneers have helped to develop linear programming theory and applications. Additionally an elegant solution technique is available for linear systems of equations. However there is a need to be able to solve the general non-linear model and non-linear systems of equations. Multi-stage Monte Carlo optimization along with the absolute value transformations presented here show some promise in solving difficult non-linear problems. They also perform well on many linear problems and tend to streamline the solution process and give the practitioner more freedom to develop accurate non-linear models and systems. The fundamental theorem of linear programming tells us that the optimal solution is at a ‘corner point’ of the n-dimensional constrained solution space. The simplex technique goes along the edges of the constrained region from corner point to corner point until it finds the optimal solution. However, with multistage Monte Carlo for non-linear problems, the solution could be anywhere in the constrained or unconstrained solution space. Preliminary Bayesian discovery samples are thus taken to help to locate the optimal solution region or regions and n-dimensional geometric shapes will then go straight across the region in pursuit of the solution area. These geometric shapes slowly close in and find the solution, making considerable use of the law of large numbers and the relatively compact nature of n-dimensional space. An example is presented here.