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.     

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     

求解非线性方程组的社会认知算法

将非线性方程组的求解问题转化为函数优化问题,应用一种新的智能优化算法——社会认知算法求解此优化问题,实验结果表明了社会认知算法在求解非线性方程组时的可行性和有效性。     

具有轮盘反转算子的多Agent算法用于线性系统逼近

针对John Holland的反转算子在数值优化中的不合理性, 提出了一种轮盘反转算子来克服这种不合理性,并结合该算子提出了一种多Agent进化算(RAER), 证明了算法的全局收敛性. 无约束优化仿真实验表明, 该算法性能好于其他算法. 在求解线性系统逼近工程优化问题时, 无论在固定区域还是动态扩展区域搜索, 算法都能得到更好的模型, 较其他算法能够对搜索区域进行更为充分的探索和求精. RAER算法是实际有效的.     

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.     

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.     

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.     

Robust stability analysis of linear systems with parametric uncertainty

This article is concerned with the problem of robust stability analysis of linear systems with uncertain parameters. By constructing an equivalent system with positive uncertain parameters and using the properties of these parameters, a new stability analysis condition is derived. Due to making use of the properties of uncertain parameters, the new proposed method has potential to give less conservative results than the existing approaches. A numerical example is given to illustrate the effectiveness of the proposed method.