Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.     

Logarithmic derivatives of solutions to linear differential equations

Given an ordinary differential field of characteristic zero, it is known that if and satisfy linear differential equations with coefficients in , then is algebraic over . We present a new short proof of this fact using Gröbner basis techniques and give a direct method for finding a polynomial over that satisfies. Moreover, we provide explicit degree bounds and extend the result to fields with positive characteristic. Finally, we give an application of our method to a class of nonlinear differential equations.

     

Ideals in a perfect closure, linear growth of primary decompositions, and tight closure

This paper is concerned with tight closure in a commutative Noetherian ring of prime characteristic , and is motivated by an argument of K. E. Smith and I. Swanson that shows that, if the sequence of Frobenius powers of a proper ideal of has linear growth of primary decompositions, then tight closure (of ) `commutes with localization at the powers of a single element'. It is shown in this paper that, provided has a weak test element, linear growth of primary decompositions for other sequences of ideals of that approximate, in a certain sense, the sequence of Frobenius powers of would not only be just as good in this context, but, in the presence of a certain additional finiteness property, would actually imply that tight closure (of ) commutes with localization at an arbitrary multiplicatively closed subset of .

Work of M. Katzman on the localization problem for tight closure raised the question as to whether the union of the associated primes of the tight closures of the Frobenius powers of has only finitely many maximal members. This paper develops, through a careful analysis of the ideal theory of the perfect closure of , strategies for showing that tight closure (of a specified ideal of ) commutes with localization at an arbitrary multiplicatively closed subset of and for showing that the union of the associated primes of the tight closures of the Frobenius powers of is actually a finite set. Several applications of the strategies are presented; in most of them it was already known that tight closure commutes with localization, but the resulting affirmative answers to Katzman's question in the various situations considered are believed to be new.

     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

用于细胞及组织培养的中等强度LED生物光源

研制出可用于细胞及组织培养的中等强度发光二极管光源,介绍了光源的光路原理和简要结构,测试了该光源的辐射照度及其强度分布,使用统计分析软件SPSS拟合得到该光源的辐射照度经验公式。     

线阵CCD拼接技术的应用

介绍采用性能先进的线阵CCD器件拼接技术实现光学系统的技术要求,给出了使用结果。     

Sparse matrix multiplications for linear scaling electronic structure calculations in an atom-centered basis set using multiatom blocks

A sparse matrix multiplication scheme with multiatom blocks is reported, a tool that can be very useful for developing linear-scaling methods with atom-centered basis functions. Compared to conventional element-by-element sparse matrix multiplication schemes, efficiency is gained by the use of the highly optimized basic linear algebra subroutines (BLAS). However, some sparsity is lost in the multiatom blocking scheme because these matrix blocks will in general contain negligible elements. As a result, an optimal block size that minimizes the CPU time by balancing these two effects is recovered. In calculations on linear alkanes, polyglycines, estane polymers, and water clusters the optimal block size is found to be between 40 and 100 basis functions, where about 55-75% of the machine peak performance was achieved on an IBM RS6000 workstation. In these calculations, the blocked sparse matrix multiplications can be 10 times faster than a standard element-by-element sparse matrix package.     

准周期链状聚合物电子谱及特征

研究了链状聚合物的长短键结构呈准周期排列的电子谱。利用紧束缚近似和转移矩阵方法通过理论证明和计算表明：这种准周期排列聚合物的电子谱,当长短键长度相差很小时,具有类似于金属晶体的能带结构;相差很大时,具有无序系统一维能级结构;而对于一般情形,其电子谱与上两者均异,形成所谓的类Cantor集。这3类不同的谱结构反映在链状聚合物的宏观物理性质上也将有所不同,它无疑会影响聚合物的稳定性及相关(超)导电性能,深入研究这方面问题将有助于对有机超导的认识。     

Orders on Braid Groups

It is shown that the braid group defies lattice ordering.     

An Open Question on Cyclic Relaxation

The problem discussed in this note is highly interesting. It is related to several dual iterative methods, such as the methods proposed by Kaczmarz, Hildreth, Agmon, Cryer, Mangasarian, Herman, Lent, Censor, and others. Cast as row-action methods these algorithms have been proved as useful tools for solving large convex feasibility problems that arise in medical image reconstruction from projections, in inverse problems in radiation therapy, and in linear programming.The question that we want to answer is how these algorithms behave when the feasible region is empty. It is shown that under certain conditions the primal sequence still converges while the dual sequence {y _k } obeys the rule y _k =u _k +k v, where {u _k } is a converging sequence and v is a fixed vector that satisfies A ^T v=0,v0,and,b ^T v>0. It is conjectured that these properties hold whenever the feasible region is empty. However, the validity of this claim remains an open question.This revised version was published online in October 2005 with corrections to the Cover Date.