Computing the Writhing Number of a Polygonal Knot

The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give an algorithm for computing the writhing number for a polygonal knot with n edges in time roughly proportional to n^1.6. We also implement a different, simple algorithm and provide experimental evidence for its practical efficiency.     

Line bundles on non-primary Hopf manifolds

Let X be a Hopf manifolds with Abelian fundamental group, L any flat line bundle on X, we give a formula for computing explicitly the cohomology Hq(X,Ωp(L) using the method of group action and the generalized Douady sequence.     

关于Matveev的一个问题

在这篇文章里,我们给出了一个具有性质(a)Hausdorff star-Lindel?f空间X使得e(X)=2^c,这个例子部分地回答了Matveev的一个问题。     

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.     

A direct approach to Bergman kernel asymptotics for positive line bundles

We give an elementary proof of the existence of an asymptotic expansion in powers of k of the Bergman kernel associated to L ^k , where L is a positive line bundle over a compact complex manifold. We also give an algorithm for computing the coefficients in the expansion.     

Computing optimal islands

Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n³)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.     

Dimension de l’anneau des polynomes a valeurs entieres

Let A be a commutative domain with quotient field K and A_S the ring of integer-valued polynomials thus A_S={f∈K[X]; f(A)⊂A}; we show that the Krull dimension of A_S is such that dim A_S≥dim A[X]-1 and give examples where dim A_S=dim A[X]-1. Considering chains of primes of A_S above a maximal idealm of finite residue field, we give also examples where the length of such a chain can arbitrarily be prescribed (whereas in A[X] the length of such chains is always 1). To provide such examples we consider a pair of domains A⊂B sharing an ideal I such that A/I is finite; we give sufficient conditients to have A_S⊂B[X] and show that in this case dim A_S=dim B[X]. At last, as a generalisation of Noetherian rings of dimension 1, we consider domains with an ideal I such that A/I is finite and a power Iⁿ of I is contained in a proper principal ideal of A; for such domains we show that every prime of A_S above a primem containing I is maximal.      

连续小波在医学图像处理中的一种应用

本文构造了一类具有紧支撑的无限次可导的对称小波，提出了适应医学图像处理的边缘检测算法，并给出了计算实例。     

The Neumann problem on ellipsoids

The Neumann problem on an ellipsoid in \(\mathbf {R}^n\) asks for a function harmonic inside the ellipsoid whose normal derivative is some specified function on the ellipsoid. We solve this problem when the specified function on the ellipsoid is a normalized polynomial (a polynomial divided by the norm of the normal vector arising from the definition of the ellipsoid). Specifically, we give a necessary and sufficient condition for a solution to exist, and we show that if a solution exists then it is a polynomial whose degree is at most the degree of the polynomial giving the specified function. Furthermore, we give an algorithm for computing this solution. We also solve the corresponding generalized Neumann problem and give an algorithm for computing its solution.     

Effective formulas for the local ?ojasiewicz exponent

We give an effective formula for the local ?ojasiewicz exponent of a polynomial mapping. Moreover, we give an algorithm for computing the local dimension of an algebraic variety.     

FFTs for the 2-Sphere-Improvements and Variations

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this article we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most O(N log² N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable and computationally efficient floating point implementations of slightly modified algorithms. These claims are supported by extensive numerical experiments from our implementation in C on DEC, HP, SGI and Linux Pentium platforms. These results indicate that variations of the algorithm are both reliable and efficient for a large range of useful problem sizes. Performance appears to be architecture-dependent. The article concludes with a brief discussion of a few potential applications.     

A decision procedure for well-formed linear quantum cellular automata

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n²) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 381–394 (1997)     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Computing iterative roots of polygonal functions

Based on the iterative root theory for monotone functions, an algorithm for computing polygonal iterative roots of increasing polygonal functions was given by J. Kobza. In this paper we not only give an algorithm for roots of decreasing polygonal functions but also generalize Kobza's results to the general n. Furthermore, we extend our algorithms for polygonal PM functions, a class of non-monotonic functions.     

Subsemigroup,ideal and congruence growth of free semigroups

The growth of cofinite subsemigroups of free semigroups is investigated. Lower and upper bounds for the sequence are given and it is shown to have superexponential growth of strict type nⁿ for finite free rank greater than 1. Ideal growth is shown to be exponential with strict type 2ⁿ and congruence growth is shown to be at least exponential. In addition we consider the case when the index is fixed and rank increasing, proving that for subsemigroups and ideals this sequence fits a polynomial of degree the index, whereas for congruences this fits an exponential equation of base the index. We use these results to describe an algorithm for computing values of these sequences and give a table of results for low rank and index.     

准-Groebner基的计算

本文通过定义S－多项式，给出了系数环是整环的多项式中理想的准－Groebner基的一个算法，并据此给出了计算该理想极大无关变元组和维数的一种方法。     

On the X-Y convex hull of a set of X-Y polygons

We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.