Algebraic interface‐based coarsening AMG preconditioner for multi‐scale sparse matrices with applications to radiation hydrodynamics computation

Coarsening is a crucial component of algebraic multigrid (AMG) methods for iteratively solving sparse linear systems arising from scientific and engineering applications. Its application largely determines the complexity of the AMG iteration operator. Usually, high operator complexities lead to fast convergence of the AMG method; however, they require additional memory and as such do not scale as well in parallel computation. In contrast, although low operator complexities improve parallel scalability, they often lead to deterioration in convergence. This study introduces a new type of coarsening strategy called algebraic interface‐based coarsening that yields a better balance between convergence and complexity for a class of multi‐scale sparse matrices. Numerical results for various model‐type problems and a radiation hydrodynamics practical application are provided to show the effectiveness of the proposed AMG solver.     

An algebraic multigrid method with interpolation reproducing rigid body modes for semi-definite problems in two-dimensional linear elasticity

Based on the geometric grid information as geometric coordinates, an algebraic multigrid (AMG) method with the interpolation reproducing the rigid body modes (namely the kernel elements of semi-definite operator arising from linear elasticity) is constructed, and such method is applied to the linear elasticity problems with a traction free boundary condition and crystal problems with free boundary conditions as well. The results of various numerical experiments in two dimensions are presented. It is shown from the numerical results that the constructed AMG method is robust and efficient for such semi-definite problems, and the convergence is uniformly bounded away from one independent of the problem size. Furthermore, the AMG method proposed in this paper has better convergence rate than the commonly used AMG methods. Simultaneously, an AMG method that can preserve the quotient space, which means that if the exact solution of original problem belongs to the quotient space of discrete operator considered, then the numerical solution of AMG method is convergent in the same quotient space, is obtained using the technique of orthogonal decomposition.     

An MPEC formulation and its cutting constraint algorithm for continuous network design problem with multi-user classes

Continuous network design problem (CNDP) is to determine the set of link capacity expansions and the corresponding equilibrium flows for which the measures of performance index for the network is optimal. Conventionally, CNDP assumed users to be homogeneous, that is, all travelers on the same link of the network are identical insofar as congestion effect and they have the same value of time (VOT). In fact, it does not accord with the real situation that all have the same VOT. So, multiple user classes with different VOT should be considered. This paper examines the CNDP with different VOT for multiple user classes, which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). Then, the cut constraint algorithm (CCA) is presented to solve the problem. The numerical experiments on the examples from the literature are illustrated to demonstrate that our model and algorithm are feasible.     

An algorithm for the zeros of transcendental functions

Summary In this paper, we extend the dual form of the generalized algorithm of Sebastião e Silva [3] for polynomial zeros and show that it is effective for finding zeros of transcendental functions in a circle of analyticity.     

改进的带驻留时间隐Markov模型的前向-后向算法

对隐Maxkov模型(hidden Markov model:HMM)的状态驻留时间的概率进行了修订,给出了改进的带驻留时间隐Markov模型的结构,并在传统的隐Markov模型(traditional hidden Markov model:THMM)的基础上讨论了新模型的前向.后向变量,导出了新模型的前向-后向算法的迭代公式,同时也给出了新模型各个参数的重估公式.     

A global optimization algorithm for reliable network design

In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.     

基于参数设计的信噪比交叉效率评价方法

针对DEA交叉效率评价过程中没有考虑自评与互评效率的作用而主观赋予相同权重导致交叉效率评价值不准确的问题.文章基于参数设计的思想,依据试验设计中可控与不可控因素的作用机理区分自评权重和互评权重对所评价决策单元交叉效率的影响与作用,将其界定为可控与不可控因素的管理学属性,明确不同权重作用机理;引入信噪比作为衡量决策单元交...     

An inexact shift‐and‐invert Arnoldi algorithm for Toeplitz matrix exponential

We revisit the shift‐and‐invert Arnoldi method proposed in [S. Lee, H. Pang, and H. Sun. Shift‐invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., 32: 774–792, 2010] for numerical approximation to the product of Toeplitz matrix exponential with a vector. In this approach, one has to solve two large‐scale Toeplitz linear systems in advance. However, if the desired accuracy is high, the cost will be prohibitive. Therefore, it is interesting to investigate how to solve the Toeplitz systems inexactly in this method. The contribution of this paper is in three regards. First, we give a new stability analysis on the Gohberg–Semencul formula (GSF) and define the GSF condition number of a Toeplitz matrix. It is shown that when the size of the Toeplitz matrix is large, our result is sharper than the one given in [M. Gutknecht and M. Hochbruck. The stability of inversion formulas for Toeplitz matrices, Linear Algebra Appl., 223/224: 307–324, 1995]. Second, we establish a relation between the error of Toeplitz systems and the residual of Toeplitz matrix exponential. We show that if the GSF condition number of the Toeplitz matrix is medium‐sized, then the Toeplitz systems can be solved in a low accuracy. Third, based on this relationship, we present a practical stopping criterion for relaxing the accuracy of the Toeplitz systems and propose an inexact shift‐and‐invert Arnoldi algorithm for the Toeplitz matrix exponential problem. Numerical experiments illustrate the numerical behavior of the new algorithm and show the effectiveness of our theoretical results. Copyright © 2015 John Wiley & Sons, Ltd.