The smallest point of a polytope

This note suggests new ways for calculating the point of smallest Euclidean norm in the convex hull of a given set of points inR ⁿ . It is shown that the problem can be formulated as a linear least-square problem with nonnegative variables or as a least-distance problem. Numerical experiments illustrate that the least-square problem is solved efficiently by the active set method. The advantage of the new approach lies in the solution of large sparse problems. In this case, the new formulation permits the use of row relaxation methods. In particular, the least-distance problem can be solved by Hildreth's method.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

非负矩阵Perron根的上下界

1.引言 本文主要讨论非负矩阵,我们将用B≥0和B>0分别表示矩阵B是非负的和正的,也就是B的每一个元素是非负的和B的每一个元素是正的.用p(B)表示方阵B的谱半径,当B≥0时,p(B)也就是B的perron根. 设(n)={1,2,…,n},A=(ai,j)是n×n非负矩阵,我们称     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

Global error bounds for the extended vertical LCP

A new necessary and sufficient condition for the row -property is given. By using this new condition and a special row rearrangement, we provide two global error bounds for the extended vertical linear complementarity problem under the row -property, which extend the error bounds given in Chen and Xiang (Math. Program. 106:513–525, 2006) and Mathias and Pang (Linear Algebra Appl. 132:123–136, 1990) for the P-matrix linear complementarity problem, respectively. We show that one of the new error bounds is sharper than the other, and it can be computed easily for some special class of the row -property block matrix. Numerical examples are given to illustrate the error bounds. The work was in part supported by a Grant-in-Aid from Japan Society for the Promotion of Science, and the National Natural Science Foundation of China (10671010).     

多项式的最大公因式的一种新求法

本文介绍了一种利用数域上矩阵的初等行变换求一组一元ｎ次多项式的最大公因式的方法．     

Degenerate Boundary Conditions for a Third-Order Differential Equation

We consider the spectral problem y'''(x) = λy(x) with general two-point boundary conditions that do not contain the spectral parameter λ. We prove that the boundary conditions in this problem are degenerate if and only if their 3 × 6 coefficient matrix can be reduced by a linear row transformation to a matrix consisting of two diagonal 3 × 3 matrices one of which is the identity matrix and the diagonal entries of the other are all cubic roots of some number. Further, the characteristic determinant of the problem is identically zero if and only if that number is ?1. We also show that the problem in question cannot have finite spectrum.     

The Homotopy Perturbation Renormalization Group Method to Solve the WKB Problem with Turn Points

In this paper, we give the homotopy perturbation renormalization group method, this is a new method for turning point problem. Using this method, the independent variables are introduced by transformation without introducing new related variables and no matching is needed. The WKB approximation method problem can be solved.     

Algebra over estimation algorithms: Normalization with respect to the interval

Algebra over estimation algorithms with addition, multiplication by a constant, and normalization operations is investigated. Normalization is interpreted as a linear (with respect to each row) transformation of the matrix of estimates that takes the maximum entry of the row to unity and the minimum entry to zero. The algebraic closure is described, a formula for its dimension is obtained, and correctness criteria are formulated.     

Break minimization

A break in a {0, 1}-matrix is defined as a 0 with at least one 1 to its left and at least one 1 to its right in the same row. This paper is concerned with {0, 1}-matrices with given column sums and an upper limit for the row sums. In addition, there are limits on the distance from the first to the last 1 in a row. The problem that is considered is to find a {0, 1}-matrix satisfying the conditions such that the total number of breaks is minimum. An algorithm for solving this problem is presented. Computational results illustrate the effectiveness of the algorithm. The investigation originated in a problem of crew rostering.     

A shortest path-based approach to the multileaf collimator sequencing problem

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.     

Row Stochastic Matrices Similar to Doubly Stochastic Matrices

The problem of determining which row stochastic n-by-n matrices are similar to doubly stochastic matrices is considered. That not all are is indicated by example, and an abstract characterization as well as various explicit sufficient conditions are given. For example, if a row stochastic matrix has no entry smaller than (n+1)^-1 it is similar to a doubly stochastic matrix.

Relaxing the nonnegativity requirement, the real matrices which are similar to real matrices with row and column sums one are then characterized, and it is observed that all row stochastic matrices have this property. Some remarks are then made on the nonnegative eigenvalue problem with respect to i) a necessary trace inequality and ii) removing zeroes from the spectrum.     

Block rearranging elements within matrix columns to minimize the variability of the row sums

Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic—based on an idea of variance equalization—to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar–Karp differencing algorithm.     

用矩阵的初等变换解矩阵方程A_(m×n)X_(n×s)=B_(m×s)

本文通过对一般的矩阵方程Ａｍ×ｎＸｎ×ｓ＝Ｂｍ×ｓ的矩阵Ａ和Ｂ作初等行变换及初等列变换，给出了一般矩阵方程的求解方法．     

Matrix pencils completion problems

In this paper we give a partial solution to the challenge problem posed by Loiseau et al. in [J. Loiseau, S. Mondié, I. Zaballa, P. Zagalak, Assigning the Kronecker invariants of a matrix pencil by row or column completion, Linear Algebra Appl. 278 (1998) 327-336], i.e. we assign the Kronecker invariants of a matrix pencil obtained by row or column completion. We have solved this problem over arbitrary fields.     

A variational iteration method for solving Troesch’s problem

Troesch’s problem is an inherently unstable two-point boundary value problem. A new and efficient algorithm based on the variational iteration method and variable transformation is proposed to solve Troesch’s problem. The underlying idea of the method is to convert the hyperbolic-type nonlinearity in the problem into polynomial-type nonlinearities by variable transformation, and the variational iteration method is then directly used to solve this transformed problem. Only the second-order iterative solution is required to provide a highly accurate analytical solution as compared with those obtained by other analytical and numerical methods.     

Some Birkhoff interpolation problems on the roots of unity

The object of this note is to study three row almost Hermitian incidence matrices and to give sufficient conditions when the corresponding interpolation problem is regular on the roots of unity. In particular, a three row almost Hermitian matrix with only two nonzero entries in one row is regular on the cube roots of unity. Other situations are also examined in detail.     

Integer matrices with constraints on leading partial row and column sums

Consider the problem of finding an integer matrix that satisfies given constraints on its leading partial row and column sums. For the case in which the specified constraints are merely bounds on each such sum, an integer linear programming formulation is shown to have a totally unimodular constraint matrix. This proves the polynomial-time solvability of this case. In another version of the problem, one seeks a zero-one matrix with prescribed row and column sums, subject to certain near-equality constraints, namely, that all leading partial row (respectively, column) sums up through a given column (respectively, row) are within unity of each other. This case admits a polynomial reduction to the preceding case, and an equivalent reformulation as a maximum-flow problem. The results are developed in a context that relates these two problems to consistent matrix rounding.     

On the equivalence of some generalized network problems to pure network problems

The purpose of this paper is to show that any generalized network problem whose matrix does not have full row rank can be transformed into an equivalent pure network problem and to give a constructive method for doing this.