Fast mixing for independent sets,colorings, and other models on trees

We study the mixing time of the Glauber dynamics for general spin systems on the regular tree, including the Ising model, the hard‐core model (independent sets), and the antiferromagnetic Potts model at zero temperature (colorings). We generalize a framework, developed in our recent paper (Martinelli, Sinclair, and Weitz, Tech. Report UCB//CSD‐03‐1256, Dept. of EECS, UC Berkeley, July 2003) in the context of the Ising model, for establishing mixing time O(nlog n), which ties this property closely to phase transitions in the underlying model. We use this framework to obtain rapid mixing results for several models over a significantly wider range of parameter values than previously known, including situations in which the mixing time is strongly dependent on the boundary condition. We also discuss applications of our framework to reconstruction problems on trees. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

求解两类Maxwell方程组棱元离散系统的快速算法和自适应方法

Maxwell方程组棱元离散系统的快速算法和自适应方法是当前计算电磁场中的研究热点和难点. 首先, 针对H(curl)椭圆方程组的棱元离散系统, 通过建立棱元空间的稳定性分解, 设计了相应的快速迭代法和高效预条件子, 并且证明了迭代算法的收敛率和预条件子的条件数均不依赖于模型参数和网格规模. 其次, 针对时谐Maxwell方程组的棱有限元方法, 利用离散的Helmholtz分解, 连续散度为零函数对离散散度为零函数的逼近性和对偶论证, 获得了在L²和H(curl)范数下的拟最优误差估计. 进而设计和分析了相应的两网格法. 最后, 分别针对变系数H(curl)椭圆方程组和不定时谐Maxwell方程组, 考虑了一种不需要标记振荡项和加密单元不需要满足“内节点” 性质的自适应棱有限元法(AEFEM), 并证明了AEFEM的收敛性. 进一步, 当初始网格和Dörfler标记策略参数满足一定的假设条件时, 利用AEFEM的收敛性、误差的整体下界和局部上界估计, 证明了AEFEM的拟最优复杂性.     

Fast and Stable Reduction of Diagonal Plus Semi-Separable Matrices to Tridiagonal and Bidiagonal Form

A two-way chasing algorithm to reduce a diagonal plus a symmetric semi-separable matrix to a symmetric tridiagonal one and an algorithm to reduce a diagonal plus an unsymmetric semi-separable matrix to a bidiagonal one are considered. Both algorithms are fast and stable, requiring a computational cost of N ², where N is the order of the considered matrix.     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Fast and stable two‐way algorithm for diagonal plus semi‐separable systems of linear equations

An algorithm for the solution of linear systems of equations where the coefficient matrix is diagonal plus a semi‐separable matrix is considered. The algorithm is stable with linear complexity. Furthermore, it is suitable for an implementation on a system of two processors. Copyright © 2001 John Wiley & Sons, Ltd.     

Fast solvers of integral and pseudodifferential equations on closed curves

On the basis of a fully discrete trigonometric Galerkin method and two grid iterations we propose solvers for integral and pseudodifferential equations on closed curves which solve the problem with an optimal convergence order , (Sobolev norms of periodic functions) in arithmetical operations.

     

Fast solution of the obstacle problem

The purpose of this paper is to present a fast algorithm for the numerical solution of the one-dimensional obstacle problem. It is proven that the algorithm converges in a finite number of steps; application examples showing its efficiency are presented.This work was supported by the National Research Council of Argentina, Grant No. PID-3091000.     

The topology of spaces of phylogenetic trees with symmetry

Natural Dowling analogues of the complex of phylogenetic trees are studied. Using discrete Morse theory, we find their homotopy types. In the process, the homotopy types of certain subposets of Dowling lattices are determined.     

Reconstruction of Gray-Scale Images

We present an algorithm to reconstruct gray scale images corrupted by noise. We use a Bayesian approach. The unknown original image is assumed to be a realization of a Markov random field on a finite two dimensional region Z². This image is degraded by some noise, which is assumed to act independently in each site of and to have the same distribution on all sites. For the estimator we use the mode of the posterior distribution: the so called maximum a posteriori (MAP) estimator. The algorithm, that can be used for both gray-scale and multicolor images, uses the binary decomposition of the intensity of each color and recovers each level of this decomposition using the identification of the problem of finding the two color MAP estimator with the min-cut max-flow problem in a binary graph, discovered by Greig et al. (1989). Experimental results and a detailed example are given in the text. We also provide a web page where additional information and examples can be found.     

Fast surface reconstruction and hole filling using positive definite radial basis functions

Surface reconstruction from large unorganized data sets is very challenging, especially if the data present undesired holes. This is usually the case when the data come from laser scanner 3D acquisitions or if they represent damaged objects to be restored. An attractive field of research focuses on situations in which these holes are too geometrically and topologically complex to fill using triangulation algorithms. In this work a local approach to surface reconstruction from point-clouds based on positive definite Radial Basis Functions (RBF) is presented that progressively fills the holes by expanding the neighbouring information. The method is based on the algorithm introduced in [7] which has been successfully tested for the smooth multivariate interpolation of large scattered data sets. The local nature of the algorithm allows for real time handling of large amounts of data, since the computation is limited to suitable small areas, thus avoiding the critical efficiency problem involved in RBF multivariate interpolation. Several tests on simulated and real data sets demonstrate the efficiency and the quality of the reconstructions obtained using the proposed algorithm. AMS subject classification 65D17, 65D05, 65Y20     

On Fast Computations with the Inverse to Harmonic Potential Operators via Domain Decomposition

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operations in terms of the Poincare-Steklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can be efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs are of the order O(N log^p N) and O(N log² N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations.     

电动公交枢纽直流快速充电模式及充电设施最优配置

发展电动公交能减少燃油消耗和城市污染物排放,对改善城市环境具有十分重要的意义.提出一种能显著减少电动公交运营成本的直流快速充电方式及相应的充电设施的建设模式.对公交枢纽直流快速充电模式下电动公交充电服务排队模型、高峰和平峰期充电设施最优配置模型进行了研究,并通过算例验证了这些模型的有效性.研究成果对我国电动公交的充电设施建设具有借鉴意义.     

Performance Analysis of Adaptive Genetic Algorithms with Fuzzy Logic and Heuristics

In this paper, we propose some genetic algorithms with adaptive abilities and compare with them. Crossover and mutation operators of genetic algorithms are used for constructing the adaptive abilities. All together four adaptive genetic algorithms are suggested: one uses a fuzzy logic controller improved in this paper and others employ several heuristics used in conventional studies. These algorithms can regulate the rates of crossover and mutation operators during their search process. All the algorithms are tested and analyzed in numerical examples. Finally, a best genetic algorithm is recommended.     

Finding cycles and trees in sublinear time

We present sublinear‐time (randomized) algorithms for finding simple cycles of length at least and tree‐minors in bounded‐degree graphs. The complexity of these algorithms is related to the distance of the graph from being C_k‐minor free (resp., free from having the corresponding tree‐minor). In particular, if the graph is ‐far from being cycle‐free (i.e., a constant fraction of the edges must be deleted to make the graph cycle‐free), then the algorithm finds a cycle of polylogarithmic length in time , where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of one‐sided error property testing algorithms in the bounded‐degree graphs model. For example, we show that cycle‐freeness of N‐vertex graphs can be tested with one‐sided error within time complexity , where ? denotes the proximity parameter. This matches the known query lower bound for one‐sided error cycle‐freeness testing, and contrasts with the fact that any minor‐free property admits a two‐sided error tester of query complexity that only depends on ?. We show that the same upper bound holds for testing whether the input graph has a simple cycle of length at least k, for any . On the other hand, for any fixed tree T, we show that T‐minor freeness has a one‐sided error tester of query complexity that only depends on the proximity parameter ?. Our algorithm for finding cycles in bounded‐degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree‐minors in complexity. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 139–184, 2014     

Divide and conquer algorithms for computing the eigendecomposition of symmetric diagonal-plus-semiseparable matrices

Three fast and stable divide and conquer algorithms to compute the eigendecomposition of symmetric diagonal-plus-semiseparable matrices are considered. AMS subject classification 15A18, 15A23, 65F15The research of the second and the third author was supported by the Research Council K.U. Leuven, to13.25cmproject OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research –     

Ordinal algorithms for packing with target center of gravity

The problem of arranging N unit length weights on a line segment of length N, given a target center of gravity on this line segment, is examined under the assumption that the only information we have about the weights is their order, i.e., a ₁ a ₂ ... a _N . Lower bounds on worst case performance of algorithms for this problem are developed, and algorithms (permutations) which come close to achieving these bounds are provided.This work was partially supported under Natural Sciences and Engineering Research Council (NSERC) of Canada research grant number OGP0002507.     

Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non‐adaptiveness

We are given n coins of which k are heavy (defective), while the remaining n ‐ k are light (good). We know both the weight of the good coins and the weight of the defective ones. Therefore, if we weigh a subset Q ? S with a spring scale, then the outcome will tell us exactly the number of defectives contained in Q. The problem, known as Counterfeit Coins problem, is to identify the set of defective coins by minimizing the number of weighings, also called queries. It is well known that Θ(klog _{k +1}(n/k)) queries are enough, even for non‐adaptive algorithms, in case k ≤ cn for some constant 0 < c < 1. A natural interesting generalization arises when we are required to identify any subset of m ≤ k defectives. We show that while for randomized algorithms \begin{align*}\tilde{\Theta}(m)\end{align*} queries are sufficient, the deterministic non‐adaptive counterpart still requires Θ(klog _{k +1}(n/k)) queries, in case k ≤ n/2⁸; therefore, finding any subset of defectives is not easier than finding all of them by a non‐adaptive deterministic algorithm. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

一类带有快扩散项的半导体方程的弱解存在性

In this paper, we consider the transient drift-diffusion model with fast diffusion term. This problem is not only degenerate but also singular. We present the existence result for the Neumann boundary value problem with general nonlinear diffusivities.