Efficient Algorithms for Approximate String Matching with Swaps

Most research on the edit distance problem and thek-differences problem considered the set of edit operations consisting of changes, insertions, and deletions. In this paper we include theswapoperation that interchanges two adjacent characters into the set of allowable edit operations, and we present anO(t min(m, n))-time algorithm for the extended edit distance problem, wheretis the edit distance between the given strings, and anO(kn)-time algorithm for the extendedk-differences problem. That is, we add swaps into the set of edit operations without increasing the time complexities of previous algorithms that consider only changes, insertions, and deletions for the edit distance andk-differences problems.     

Algorithms for Computing Characters for Symmetric Spaces

Symmetric spaces or more general symmetric k-varieties can be defined as the homogeneous spaces G _k /K _k , where G is a reductive algebraic group defined over a field k of characteristic not 2, K the fixed point group of an involution θ of G and G _k resp. K _k the sets k-rational points of G resp. K. These symmetric spaces have a fine structure of root systems, characters, Weyl groups etc., similar to the underlying algebraic group G. The relationship between the fine structure of the symmetric space and the group plays an important role in the study of these symmetric spaces and their applications. To develop a computer algebra package for symmetric spaces one needs explicit formulas expressing the fine structure of the symmetric space and group in terms of each other. In this paper we consider the case that k is algebraically closed and give explicit algorithmic formulas for expressing the characters of the weight lattice of the symmetric space in terms of the characters of the weight lattice of the group. These algorithms can easily be implemented in a computer algebra package. The root system of the symmetric space can be described as the image of the root system of the group under a projection π derived from an involution θ on . This implies that . Using these formulas for the characters of each of these lattices we show that in fact . A.G. Helminck is partially supported by N.S.F. Grant DMS-0532140.     

Fast Algorithms for Complete Linkage Clustering

It is shown that the complete linkage clustering of n points can be computed in O(n log ² n) time. Furthermore, it is shown that the complete linkage clustering can be approximated within an arbitrarily small constant factor in O(n log n) time. Received September 18, 1995, and in revised form April 17, 1997.     

Fast Algorithms for Nonparametric Curve Estimation

Abstract

Naive implementations of local polynomial fits and kernel estimators require almost O(n ²) operations. In this article two fast O(n) algorithms for nonparametric local polynomial fitting are presented. They are based on updating normal equations. Numerical stability is guaranteed by controlling ill-conditioned situations for small bandwidths and data-tuned restarting of the updating procedure. Restarting at every output point results in a moderately fast but highly stable O(n ^7/5) algorithm. Applicability of algorithms is evaluated for estimation of regression curves and their derivatives. The idea is also applied to kernel estimators of regression curves and densities.     

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R (respectively, B). This rule implicitly partitions space into a red set and a blue set that are separated by a red-blue decision boundary. In this paper we develop output-sensitive algorithms for computing this decision boundary for point sets on the line and in ². Both algorithms run in time O(n log k), where k is the number of points that contribute to the decision boundary. This running time is the best possible when parameterizing with respect to n and k.     

Fast Parallel Algorithms for Computing Generalized Inverses $A^+$ and $A_{MN}^+$

The parallel arithmetic complexities for computing generalized inverse $A^+$, computing the minimum-norm least-squares solution of $Ax=b$, computing order $m+n-r$ determinants and finding the characteristic polynomials of order $m+n-r$ matrices are shown to have the same grawth rate. Algorithms are given that compute $A^+$ and $A_{MN}^+$ in $O(\log r\dot \log n+\log m)$ and $O(\log^2n+\log m)$ steps using a number of processors which is a polynomial in $m, \ n$ and $r$ $(A\in B_r^{m\times n},r=rank \ A)$.     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Some Algorithms for Use with the Fast Fourier Transform

This paper gives algorithms for the Fast Fourier Transform ofreal half range even data, real half range odd data and complexhalf range even data.     

A Practical Algorithm for Computing a Subadditive Dual Function for Set Partitioning

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.     

Fast Algorithms for Identification and Comparison of Braids

A method for constructing algorithms solving the word and comparison problems for mapping class groups (in particular, for the braid group) is presented, and a family of one-side invariant orderings on the mapping class group of a surface with boundary is described. A method for constructing comparison algorithms for all finite orderings on the mapping class group of any surface with boundary is described, a fast and simple comparison algorithm for the Dehornoy order on the braid group is presented, examples of normal forms for braid groups are given, and algorithms for finding the forms are indicated. Bibliography: 15 titles.     

Fast Algorithms for Centro-Symmetric and Centro-Skewsymmetric Toeplitz-Plus-Hankel Matrices

Subject of the paper are centro-symmetric and centro-skewsymmetric Toeplitz-plus-Hankel matrices with the property that all central submatrices are nonsingular. Fast algorithms are presented that solve an n×n system of equations with O(n ²) operations in sequential and O(n) operations in parallel processing and compute the ZW-factorization with the same computational complexity. These algorithms are more efficient than existing algorithms because they fully exploit the symmetry properties of the matrices.     

Fast and Flexible ADMM Algorithms for Trend Filtering

This article presents a fast and robust algorithm for trend filtering, a recently developed nonparametric regression tool. It has been shown that, for estimating functions whose derivatives are of bounded variation, trend filtering achieves the minimax optimal error rate, while other popular methods like smoothing splines and kernels do not. Standing in the way of a more widespread practical adoption, however, is a lack of scalable and numerically stable algorithms for fitting trend filtering estimates. This article presents a highly efficient, specialized alternating direction method of multipliers (ADMM) routine for trend filtering. Our algorithm is competitive with the specialized interior point methods that are currently in use, and yet is far more numerically robust. Furthermore, the proposed ADMM implementation is very simple, and, importantly, it is flexible enough to extend to many interesting related problems, such as sparse trend filtering and isotonic trend filtering. Software for our method is freely available, in both the C and R languages.     

Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination

High-dimension-low-sample size statistical analysis is important in a wide range of applications. In such situations, the highly appealing discrimination method, support vector machine, can be improved to alleviate data piling at the margin. This leads naturally to the development of distance weighted discrimination (DWD), which can be modeled as a second-order cone programming problem and solved by interior-point methods when the scale (in sample size and feature dimension) of the data is moderate. Here, we design a scalable and robust algorithm for solving large-scale generalized DWD problems. Numerical experiments on real datasets from the UCI repository demonstrate that our algorithm is highly efficient in solving large-scale problems, and sometimes even more efficient than the highly optimized LIBLINEAR and LIBSVM for solving the corresponding SVM problems. Supplementary material for this article is available online.     

计算Riemann-Liouville分数阶积分和导数的数值算法

研究计算Riemann-Liouville (RL)分数阶积分和导数的数值算法.首先,分析了RL分数阶积分和导数的定义式,由于定义式中包含一个积分瑕点,使RL分数阶积分和导数难于计算.然后,给出了一种去掉积分瑕点的方法,在此基础上设计出计算RL分数阶积分和导数的数值算法,并证明了此数值算法具有一阶精度.最后,给出了计算实例,计算结果说明提出的算法是有效的.     

Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

In this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log²n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given.     

求矩阵对策全部解的单纯形法

给出求矩阵对策全部解的一种单纯形法 ,并指出参考文献 [1 ]中的两个错误 .     

Efficient and Practical Algorithms for Sequential Modular Decomposition

A module of an undirected graph G = (V, E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n + mα(m, n)) time bound and a variant with a linear time bound.     

Dualize,Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms

Journal of Optimization Theory and Applications - We consider minimizing the sum of three convex functions, where the first one F is smooth, the second one is nonsmooth and proximable and the third...     

离散信道容量的迭代算法

引入信息量偏差概念，给出平均交互信息量关于输入概率的增量公式，设计出离散信道容量线性乘法迭代和线性常系数迭代算法，它们都优于现有的指数迭代算法．并证明在所有单步迭代算法中它们几乎是最好的算法.