Wavelet formulation of the polarizable continuum model

The first implementation of a wavelet discretization of the Integral Equation Formalism (IEF) for the Polarizable Continuum Model (PCM) is presented here. The method is based on the application of a general purpose wavelet solver on the cavity boundary to solve the integral equations of the IEF‐PCM problem. Wavelet methods provide attractive properties for the solution of the electrostatic problem at the cavity boundary: the system matrix is highly sparse and iterative solution schemes can be applied efficiently; the accuracy of the solver can be increased systematically and arbitrarily; for a given system, discretization error accuracy is achieved at a computational expense that scales linearly with the number of unknowns. The scaling of the computational time with the number of atoms N is formally quadratic but a N^1.5 scaling has been observed in practice. The current bottleneck is the evaluation of the potential integrals at the cavity boundary which scales linearly with the system size. To reduce this overhead, interpolation of the potential integrals on the cavity surface has been successfully used. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010     

Fisher information description of the classical-quantal transition

We investigate the classical limit of the dynamics of a semiclassical system that represents the interaction between matter and a given field. The concept of Fisher Information measure (F) on using as a quantifier of the process, we find that it adequately describes the transition, detecting the most salient details of the changeover. Used in conjunction with other possible information quantifiers, such as the Normalized Shannon Entropy (H) and the Statistical Complexity (C) by recourse to appropriate planar representations like the Fisher Entropy (F×H) and Fisher Complexity (F×C) planes, one obtains a better visualization of the transition than that provided by just one quantifier by itself. In the evaluation of these Information Theory quantifiers, we used the Bandt and Pompe methodology for the obtention of the corresponding probability distribution.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

二阶数乘问题的一个最优算法

研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下：给定n≥2个正整数a_1,a_2,…,a_n,设π为{1,2,…,n}的一个置换,表示该问题的一个解,试图找到一个置换π以至∑_（i=1）~n a_（π_i）a_（π_（i＋1））最小,在这里π_（n＋1）=π_1.给出了一个算法复杂度为O（n log n）的最优算法.     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.     

Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming

In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an -approximate solution of an SDP in O(n²ln(1/)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.Research supported in part by the Singapore-MIT alliance, and NUS Academic Research Grant R-146-000-032-112.Mathematics Subject Classification (1991): 90C05, 90C30, 65K05     

一类新的求解P_*(κ)阵线性互补问题的多项式内点算法

利用核函数及其性质,对P_*(k)阵线性互补问题提出了一种新的宽邻域不可行内点算法.对核函数作了一些适当的改进,所以是不同于Peng等人介绍的自正则障碍函数.最后证明了算法具有近似O((1+2k)n3/4log(nμ~0)/ε)多项式复杂性,是优于传统的基于对数障碍函数求解宽邻域内点算法的复杂性.     

Two Interior-Point Methods for Nonlinear P *(τ)-Complementarity Problems

Two interior-point algorithms using a wide neighborhood of the central path are proposed to solve nonlinear P _*-complementarity problems. The proof of the polynomial complexity of the first method requires the problem to satisfy a scaled Lipschitz condition. When specialized to monotone complementarity problems, the results of the first method are similar to those in Ref. 1. The second method is quite different from the first in that the global convergence proof does not require the scaled Lipschitz assumption. However, at each step of this algorithm, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied.     

Riemannian geometry of quantum computation

A review is given of some recent developments in the differential geometry of quantum computation for which the quantum evolution is described by the special unitary unimodular group, SU(2ⁿ). Using the Lie algebra su(2ⁿ), detailed derivations are given of a useful Riemannian geometry of SU(2ⁿ), including the connection and the geodesic equation for minimal complexity quantum computations.