主理想整环上的线性方程组的通解

将文[1]中整数环上的线性方程组问题推广到主理想整环上,利用主理想整环上的矩阵的初等变换及等价标准形导出了主理想整环上的线性方程组有解的一个充分必要条件和求解方法.最后,通过实例说明了算法.     

On a Matrix Equation AX＋XB=C over a Skew Field

In this paper we study a matrix equation AX BX=C （Ⅰ）over an arbitrary skew field,and give a consistency criterion of （Ⅰ） and an explicit expression of general solutions of （Ⅰ）.A convenient,simple and practical method of solving （Ⅰ） is also given.As a particular case,we also give a simple method of finding a system of fundamental solutions of a homogeneous system of right linear equations over a skew field.     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

On the critical exponents of random k‐SAT

There has been much recent interest in the satisfiability of random Boolean formulas. A random k‐SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2‐SAT this happens when m/n → 1, for 3‐SAT the critical ratio is thought to be m/n ≈ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called ν = ν_k (the smaller the value of ν the sharper the transition). Experiments have suggested that ν₃ = 1.5 ± 0.1. ν₄ = 1.25 ± 0.05, ν₅ = 1.1 ± 0.05, ν₆ = 1.05 ± 0.05, and heuristics have suggested that ν_k → 1 as k → ∞. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well defined). This result holds for each of the three standard ensembles of random k‐SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q‐colorability and the appearance of a q‐core in a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002     

A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas

We compute the probability of satisfiability of a class of random Horn‐SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum clause length is three, this model displays a curve in its parameter space, along which the probability of satisfiability is discontinuous, ending in a second‐order phase transition where it is continuous but its derivative diverges. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Monte-Carlo estimation of time-dependent statistical characteristics of random dynamical systems

The problem of estimating the time-dependent statistical characteristics of a random dynamical system is studied under two different settings. In the first, the system dynamics is governed by a differential equation parameterized by a random parameter, while in the second, this is governed by a differential equation with an underlying parameter sequence characterized by a continuous time Markov chain. We propose, for the first time in the literature, stochastic approximation algorithms for estimating various time-dependent process characteristics of the system. In particular, we provide efficient estimators for quantities such as the mean, variance and distribution of the process at any given time as well as the joint distribution and the autocorrelation coefficient at different times.     

黄金分割法在求解线性方程组中的应用

把线性方程组转化成为其等价的变分问题 ,借助黄金分割法的思想对该变分问题进行求解 ,给出的算例结果表明 ,本文方法不仅对良态线性方程组的求解有效 ,而且对于病态线性方程组的求解同样是有效实用的 .     

On the Rate of Convergence for Modified Baskakov Operators

We consider some linear operators in certain weighted spaces of functions of one variable and study approximation properties of these operators. The method was inspired by Kirov [4].     

On the expected optimal value of random assignment problems: Experimental results and open questions

In the paper, we study the expected optimal value of random linear assignment problems, whose data are random variables with the uniform and the exponential distributions. An interior point approach is used to solve large-scale dense assignment problems with size up to 10,000 nodes and 100 million edges. Our computational results indicate the validity of a long-standing conjecture about the limiting value of the expected optimal assignment. Some interesting open problems and extensions are discussed.     

On the algebraic structure of functional matrices of special form

Algebraic properties of functional matrices arising in the constuction of graded Padé approximations are established. This construction plays an important role in the theory of transcendental numbers. Translated fromMatematicheskie Zametki, Vol. 60, No. 6, pp. 851–860, December, 1996. This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-00739.     

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 − κ(p))p, where κ(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.     

An average case analysis of the minimum spanning tree heuristic for the power assignment problem

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]^d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d.     

On a System of Martix Equations over an Arbitrary Skew Field

ＯｎａＳｙｓｔｅｍｏｆＭａｒｔｉｘＥｑｕａｔｉｏｎｓｏｖｅｒａｎＡｒｂｉｔｒａｒｙＳｋｅｗＦｉｅｌｄ￥ＷａｎｇＱｉｎｇｗｅｎ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＣｈａｎｇｗｅｉＴｅａｃｈｅｒｓＣｏｌｌｅｙｅ，Ｗｅｉｆａｎｇ，Ｗｅｉｆａｎｇ，２６１０４３）Ａｂ...     

A Strong Approximation Theorem for Stochastic Recursive Algorithms

The constant stepsize analog of Gelfand–Mitter type discrete-time stochastic recursive algorithms is shown to track an associated stochastic differential equation in the strong sense, i.e., with respect to an appropriate divergence measure.     

The Lagrange principle in the problem of optimal inversion of linear operators in finite-dimensional spaces with a priori information about its solution

The problem of solving a system of linear algebraic equations is examined. An application of the Lagrange principle to the optimal recovery in this problem is described. New optimal methods that use available information about the errors in the data and a priori information about the solution are proposed for solving such systems.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

有限维中心代数上矩阵方程组的广对称解与斜广对称解

设Ω是一个具有对合反自同构的有限维中心代数且charΩ≠2.本文在Ω上定义了广对称矩阵和斜广对称矩阵,在Ω[λ]上考虑了三个矩阵方程组,分别给出了其有广对称解和斜广对称的充要条件.作为特例,得到了某些矩阵方程相应的结果.     

On hypothesis testing with a partitioned random alternative

It is common in statistical practice that one needs to make a choice among m + 1 mutually exclusive claims on distributions.When m=1,it is done by the (traditional) hypothesis test.In this paper,a generalization to the case m > 1 is proposed.The fundamental difference with the case m=1 is that the new alternative hypothesis is a partition of m multiple claims and is data-dependent.Data is used to decide which claim in the partition is to be tested as the alternative.Thus,a random alternative is involved.The...