Search

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

The computation of Kronecker coefficients is a challenging problem with a variety of applications. In this paper we present an approach based on methods from symplectic geometry and residue calculus. We outline a general algorithm for the problem and then illustrate its effectiveness in several interesting examples. Significantly, our algorithm does not only compute individual Kronecker coefficients, but also symbolic formulas that are valid on an entire polyhedral chamber. As a byproduct, we are able to compute several Hilbert series. [ABSTRACT FROM AUTHOR]

Suppose M is a finite cell decomposition of a space X and that for 0 = t 0 < t 1 < ⋯ < t r = 1 we have a discrete Morse function F t i : M → R . In this paper, we study the births and deaths of critical cells for the functions F t i and present an algorithm for pairing the cells that occur in adjacent slices. We first study the case where the cell decomposition of X is the same for each t i , and then generalize to the case where they may differ. This has potential applications in topological data analysis, where one has function values at a sample of points in some region in space at several different times or at different levels in an object. [ABSTRACT FROM AUTHOR]

The Morse–Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse–Smale complexes have been presented in case of piecewise linear manifolds ( Edelsbrunner et al., 2003a ). However, previous research in this field is incomplete in the case of smooth functions. In the current paper we address the following question: Given an arbitrarily complex Morse–Smale system on a planar domain, is it possible to compute its certified (topologically correct) Morse–Smale complex? Towards this, we develop an algorithm using interval arithmetic to compute certified critical points and separatrices forming the Morse–Smale complexes of smooth functions on bounded planar domain. Our algorithm can also compute geometrically close Morse–Smale complexes. [ABSTRACT FROM AUTHOR]

Forman's discrete Morse theory appeared to be useful for providing filtration-preserving reductions of complexes in the study of persistent homology. So far, the algorithms computing discrete Morse matchings have only been used for one-dimensional filtrations. This paper is perhaps the first attempt in the direction of extending such algorithms to multidimensional filtrations. An initial framework related to Morse matchings for the multidimensional setting is proposed, and a matching algorithm given by King, Knudson, and Mramor is extended in this direction. The correctness of the algorithm is proved, and its complexity analyzed. The algorithm is used for establishing a reduction of a simplicial complex to a smaller but not necessarily optimal cellular complex. First experiments with filtrations of triangular meshes are presented. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for implicitizing tensor product surfaces of bi-degree ( m , n ) with no base points, assuming that there are no moving planes of bi-degree ( m − 1 , n − 1 ) following the surface. The algorithm is based on some structural results: (1) There are exactly 2 n linearly independent moving planes of bi-degree ( m , n − 1 ) following the surface; (2) mn linearly independent moving quadrics of bi-degree ( m − 1 , n − 1 ) following the surface can be constructed from the 2 n linearly independent moving planes; (3) The mn linearly independent moving quadrics form a compact determinant of order mn which exactly gives the implicit equation of the rational surface. Complexity analysis and experimental results show that the new algorithm is significantly more efficient than the previous methods. [ABSTRACT FROM AUTHOR]

In Kaltofen and Yang (2014) we give an algorithm based algebraic error-correcting decoding for multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (“outliers”). Our 2014 algorithm can interpolate a sparse multivariate rational function from evaluations where the error rate 1 / q is quite high, say q = 5 . For the algorithm with exact arithmetic and exact values at non-erroneous points, one avoids quadratic oversampling by using random evaluation points. Here we give the full probabilistic analysis for this fact, thus providing the missing proof to Theorem 2.1 in Section 2 of our ISSAC 2014 paper. Our argumentation already applies to our original 2007 sparse rational function interpolation algorithm ( Kaltofen et al., 2007 ), where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T + O ( 1 ) evaluations rather than O ( T 2 ) (cf. Candès and Tao sparse sensing), the latter of which we have proved in 2007. Here we prove that T + O ( 1 ) evaluations at random points indeed suffice. [ABSTRACT FROM AUTHOR]

In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d . Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable. [ABSTRACT FROM AUTHOR]

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O ( n 3 log ⁡ n ) , faster than the existing O ( n 4 log ⁡ n ) QFT algorithm. In addition, we show that the algorithm can be performed in O ( n 3 ) if the use of threshold gates is allowed. [ABSTRACT FROM AUTHOR]

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial n th Weyl algebra, the polynomial n th shift algebra, and Z n -graded polynomials in the n th q _ -Weyl algebra. The most unexpected result is that this noncommutative problem of factoring partial differential operators can be approached effectively by reducing it to the problem of solving systems of polynomial equations over a commutative ring. In the case where a given polynomial is Z n -graded, we can reduce the problem completely to factoring an element in a commutative multivariate polynomial ring. The implementation in Singular is effective on a broad range of polynomials and increases the ability of computer algebra systems to address this important problem. We compare the performance and output of our algorithm with other implementations in major computer algebra systems on nontrivial examples. [ABSTRACT FROM AUTHOR]

Let R be a non-commutative PID finitely generated as a module over its center C . In this paper we give a criterion to decide effectively whether two given elements f , g ∈ R are similar, that is, if there exists an isomorphism of left R -modules between R / R f and R / R g . Since these modules are of finite length, we also consider the more general problem of deciding when two given left R -modules of finite length are isomorphic. This criterion allows the design of algorithms when R is an Ore extension of a skew-field whose center is a commutative polynomial ring. We propose two methods which, essentially, check the equality of the rational canonical forms of certain matrices with coefficients in C associated to each of the modules. These algorithms are based on the fact that, if R is finitely generated as a C -module, then the existence of an isomorphism of R -modules can be reduced to checking the existence of an isomorphism of C -modules. Actually, we prove this result in the realm of non-commutative principal ideal domains, generalizing a version given by Jacobson for some Ore extensions of a skew field by an automorphism. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of isoclinism among crossed modules and describe various properties of the notion. We give an algorithm for checking isoclinism among crossed modules and apply the algorithm (implemented in GAP) to classify certain crossed modules. [ABSTRACT FROM AUTHOR]

The main goal of the paper is to present an algorithm to realize the theoretical method by Berlyand and Mityushev (2001, 2005) for computations of the effective conductivity of fibrous composites expressed in therms of the linear combinations of the basic e -sums. Algorithms are presented in Mathematical Pseudo-language with examples in Mathematica ® . A method for simplifying the basic e -sums by reducing mirror terms is presented. Developed algorithms are applied to the optimal packing problem of disks in the plane. [ABSTRACT FROM AUTHOR]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]

In 1994 Lazard proposed an improved projection operation for cylindrical algebraic decomposition (CAD). For the proof he introduced a certain notion of valuation of a multivariate Puiseux series at a point. However a gap in one of the key supporting results for the improved projection was subsequently noticed. In this paper we show that Lazard's projection is valid for CAD construction for so-called well-oriented polynomial sets. Our proof does not make use of Lazard's notion of valuation, however. [ABSTRACT FROM AUTHOR]

Recently, Lombardi, Quitté and Yengui have given a Gröbner-free algorithm which computes the V -saturation of any finitely generated submodule of V [ X ] n , where V is a valuation domain. The goal of this paper is to clarify this algorithm, to give precise complexity bounds, and a complete submodule membership test for the saturation. As application, we give precise degree bounds on syzygies over V [ X ] . [ABSTRACT FROM AUTHOR]

Let R be a discrete valuation ring (DVR) and K be its fraction field. If M is a matrix over R admitting an LU decomposition, it could happen that the entries of the factors L and U do not lie in R , but just in K . Having a good control on the valuations of these entries is very important for algorithmic applications. In the paper, we prove that on average these valuations are not too large and explain how one can apply this result to provide an efficient algorithm computing a basis of a coherent sheaf over A K 1 from the knowledge of its stalks. [ABSTRACT FROM AUTHOR]

The notion of strict equivalence for order one differential equations of the form f ( y ′ , y , z ) = 0 with coefficients in a finite extension K of C ( z ) is introduced. The equation gives rise to a curve X over K and a derivation D on its function field K ( X ) . Procedures are described for testing strict equivalence, strict equivalence to an autonomous equation, computing algebraic solutions and verifying the Painlevé property. These procedures use known algorithms for isomorphisms of curves over an algebraically closed field of characteristic zero, the Risch algorithm and computation of algebraic solutions. The most involved cases concern curves X of genus 0 or 1. This paper complements work of M. Matsuda and of G. Muntingh & M. van der Put. [ABSTRACT FROM AUTHOR]

We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations. [ABSTRACT FROM AUTHOR]

Mumford showed that Schottky subgroups of PGL ( 2 , K ) give rise to certain curves, now called Mumford curves, over a non-archimedean field K . Such curves are foundational to subjects dealing with non-archimedean varieties, including Berkovich theory and tropical geometry. We develop and implement numerical algorithms for Mumford curves over the field of p -adic numbers. A crucial and difficult step is finding a good set of generators for a Schottky group, a problem solved in this paper. This result allows us to design and implement algorithms for tasks such as: approximating the period matrices of the Jacobians of Mumford curves; computing the Berkovich skeleta of their analytifications; and approximating points in canonical embeddings. We also discuss specific methods and future work for hyperelliptic Mumford curves. [ABSTRACT FROM AUTHOR]

In this paper, the concept of sparse difference resultant for a Laurent transformally essential system of difference polynomials is introduced and a simple criterion for the existence of sparse difference resultant is given. The concept of transformally homogenous polynomial is introduced and the sparse difference resultant is proved to be transformally homogenous. It is shown that the vanishing of the sparse difference resultant gives a necessary condition for the corresponding difference polynomial system to have non-zero solutions. Order and degree bounds for the sparse difference resultant are given. Based on these bounds, an algorithm to compute the sparse difference resultant is proposed, which is single exponential in terms of the number of variables, the Jacobi number, and the size of the Laurent transformally essential system. Furthermore, the precise order and degree, a determinant representation, and a Poisson-type product formula for the difference resultant are given. [ABSTRACT FROM AUTHOR]

Let M be a given positive integer and r = ( r δ ) δ | M a sequence indexed by the positive divisors δ of M . In this paper we present an algorithm that takes as input a generating function of the form ∑ n = 0 ∞ a r ( n ) q n : = ∏ δ | M ∏ n = 1 ∞ ( 1 − q δ n ) r δ and positive integers m , N and t ∈ { 0 , … , m − 1 } . Given this data we compute a set P m , r ( t ) which contains t and is uniquely defined by m , r and t . Next we decide if there exists a sequence ( s δ ) δ | N indexed by the positive divisors δ of N , and modular functions b 1 , … , b k on Γ 0 ( N ) (where each b j equals the product of finitely many terms from { q δ / 24 ∏ n = 1 ∞ ( 1 − q δ n ) : δ | N } ), such that: q α ∏ δ | N ∏ n = 1 ∞ ( 1 − q δ n ) s δ × ∏ t ′ ∈ P m , r ( t ) ∑ n = 0 ∞ a ( m n + t ′ ) q n = c 1 b 1 + ⋯ + c k b k for some c 1 , ⋯ , c k ∈ Q and α : = ∑ δ | N δ s δ 24 + ∑ t ′ ∈ P m , r ( t ) 24 t ′ + ∑ δ | M δ r δ 24 m . Our algorithm builds on work by Rademacher (1942) , Newman (1959) , and Kolberg (1957) . [ABSTRACT FROM AUTHOR]

In this paper, we use the theory of theta functions to generalise to all abelian varieties the usual Miller's algorithm to compute a function associated with a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extends preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we obtain a variant of optimal pairings on abelian varieties. Finally, by introducing new addition formulas, we explain how to compute optimal pairings on Kummer varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case. [ABSTRACT FROM AUTHOR]

We correct a minor mistake in the paper of Hanrot and Zimmermann (2004). [ABSTRACT FROM AUTHOR]