Solution of systems of Boolean equations via the integer domain

This paper presents a new method for solving systems of Boolean equations. The method is based on converting the equations so that we operate in the integer domain. In the integer domain better and more efficient methodologies for solving equations are available. The conversion leads us to a system of polynomial equations obeying certain characteristics. A method is proposed for solving these equations. The most computationally demanding step is the repeated multiplication of polynomials. We develop a method for this problem that is significantly faster than the standard approach. We also introduce another variant of the method, the so-called hybrid approach, that leads to reduced memory requirements. Theoretical and experimental results indicate the superior performance of the proposed method and its variant compared to the competing methods. The proposed method is also validated by applying it to the problem of hardware verification.     

Elimination of Boolean variables for probabilistic coherence

 In this paper we deal with the computational complexity problem of checking the coherence of a partial probability assessment (called CPA). The CPA problem, like its analogous PSAT, is NP-complete so we look for an heuristic procedure to make tractable reasonable instances of the problem. Starting from the characteristic feature of de Finetti's approach (i.e. the explicit distinction between the probabilistic assessment and the logical relations among the sentences) we introduce several rules for a sequential “elimination” of Boolean variables from the domain of the assessment. The procedure resembles the well-known Davis-Putnam rules for the satisfiability, however we have, as a drawback, the introduction of constraints (among real variables) whose satisfiability must be checked. In simple examples we test the efficiency of the procedure respect to the “traditional” approach of solving a linear system with a huge coefficient matrix built from the atoms generated by the domain of the assessment.     

New Riccati equations for well-posed linear systems

We consider the classic problem of minimizing a quadratic cost functional for well-posed linear systems over the class of inputs that are square integrable and that produce a square integrable output. As is well-known, the minimum cost can be expressed in terms of a bounded nonnegative self-adjoint operator X that in the finite-dimensional case satisfies a Riccati equation. Unfortunately, the infinite-dimensional generalization of this Riccati equation is not always well-defined. We show that X always satisfies alternative Riccati equations, which are more suitable for algebraic and numerical computations.     

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.     

Direct methods of solving systems of linear algebraic ef ions with complex a-matrices

Algorithms of computer algebra are proposed for solving systems of linear algebraic equations with complex á- matrices. An analysis of roundoff errors for the computational schemes considered is given. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 144–156, March–April, 2000.     

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.     

Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing

This paper proposes a method for finding solutions of arbitrarily nonlinear systems of functional equations through stochastic global optimization. The original problem (equation solving) is transformed into a global optimization one by synthesizing objective functions whose global minima, if they exist, are also solutions to the original system. The global minimization task is carried out by the stochastic method known as fuzzy adaptive simulated annealing, triggered from different starting points, aiming at finding as many solutions as possible. To demonstrate the efficiency of the proposed method, solutions for several examples of nonlinear systems are presented and compared with results obtained by other approaches. We consider systems composed of n   equations on Euclidean spaces ?n${?}^n$ (n variables: x₁, x₂, x₃, ? , x_n).     

Methods of solution and criteria of consistency of systems of linear diophantine equations over the set of natural numbers1

Some methods and algorithms of solution of systems of linear Diophantine equations over the naturals are briefly reviewed. Criteria and an incremental algorithm of efficient solution of the problem of consistency for a system of linear Diophantine equations and inequalities over the naturals are given. This research was supported under grant INTAS-RFBR 95-0095. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 12–36, July–August, 1999.     

Algorithms for solving systems of linear diophantine equations in residue rings

Algorithms are proposed that construct the basis of the set of solutions to a system of homogeneous or inhomogeneous linear Diophantine equations in a residue ring modulo n when the prime factors of n are known. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 27–40, November–December 2007.     

Algorithms for solving systems of linear diophantine equations in integer domains

Algorithms are described that solve homogeneous systems of linear Diophantine equations over natural numbers and over the set {0, 1}. Properties of the algorithms and their time estimates are given. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 3–17, March–April 2006.     

Algorithms for solution of systems of linear diophantine equations in residue fields

Algorithms are proposed for computing the basis of the solution set of a system of linear Diophantine homogeneous or inhomogeneous equations in the residue field modulo a prime number. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 15–23, March–April 2007.     

Simulation based optimization of stochastic systems with integer design variables by sequential multipoint linear approximation

Optimization problems are considered for which objective function and constraints are defined as expected values of stochastic functions that can only be evaluated at integer design variable levels via a computationally expensive computer simulation. Design sensitivities are assumed not to be available. An optimization approach is proposed based on a sequence of linear approximate optimization subproblems. Within each search subregion a linear approximate optimization subproblem is built using response surface model building. To this end, N simulation experiments are carried out in the search subregion according to a D-optimal experimental design. The linear approximate optimization problem is solved by integer linear programming using corrected constraint bounds to account for any uncertainty due to the stochasticity. Each approximate optimum is evaluated on the basis of M simulation replications with respect to objective function change and feasibility of the design. The performance of the optimization approach and the influence of parameters N and M is illustrated via two analytical test problems. A third example shows the application to a production flow line simulation model. Received April 28, 2000     

Tableau methods for analysis and design of linear systems

Certain classes of elementary operations on the system matrix of a linear system are defined, and then their use is illustrated for the calculation of canonical forms, the largest (A,B)-invariant and controllability subspaces in ker(C), transmission zeros, and minimal inverses. Questions of numerical accuracy are discussed. The results are directly codable as efficient numerical algorithms, and may be extended to the use of orthogonal transformations.     

Numerical solution of a fuzzy system of linear equations with polynomial parametric form

A systems of linear equations are used in many fields of science and industry, such as control theory and image processing, and solving a fuzzy linear system of equations is now a necessity. In this work we try to solve a fuzzy system of linear equations having fuzzy coefficients and crisp variables using a polynomial parametric form of fuzzy numbers.     

A new iterative refinement of the solution of ill-conditioned linear system of equations

In this paper, a new iterative refinement of the solution of an ill-conditioned linear system of equations are given. The convergence properties of the method are studied. Some numerical experiments of the method are given and compared with that of two of the available methods.     

Taylor polynomial solutions of systems of linear differential equations with variable coefficients

A Taylor collocation method has been presented for numerically solving systems of high-order linear ordinary, differential equations with variable coefficients. Using the Taylor collocation points, this method transforms the ODE system and the given conditions to matrix equations with unknown Taylor coefficients. By means of the obtained matrix equation, a new system of equations corresponding to the system of linear algebraic equations is gained. Hence by finding the Taylor coefficients, the Taylor polynomial approach is obtained. Also, the method can be used for the linear systems in the normal form. To illustrate the pertinent features of the method, examples are presented and results are compared.     

Analysis of the properties of a linear system using the method of artificial basis matrices

Formulas relating elements of the method in adjacent basis matrices are used to solve a system of linear algebraic equations and to represent analytically the general solutions to the corresponding system of linear algebraic inequalities for a nondegenerate constraint matrix. Sponsored by the ICS NATO program of April 18 2006, in line with the Project “Optimal replacement of information technologies and stable development (in Kazakhstan, Ukraine, and the USA),” NATO Grant CLG 982209. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 119–127, July–August 2007.     

Analysis of systems of singular ordinary differential equations

Systems of ordinary differential equations with a small parameter at the derivative and specific features of the construction of their periodic solution are considered. Sufficient conditions of existence and uniqueness of the periodic solution are presented. An iterative procedure of construction of the steady-state solution of a system of differential equations with a small parameter at the derivative is proposed. This procedure is reduced to the solution of a system of nonlinear algebraic equations and does not involve the integration of the system of differential equations. Problems of numerical calculation of the solution are considered based on the procedure proposed. Some sources of its divergence are found, and the sufficient conditions of its convergence are obtained. The results of numerical experiments are presented and compared with theoretical ones. Translated from Kibemetika i Sistemnyi Analiz, No. 5, pp. 103–110, September–October, 1999.