Search

Abstract: In this paper we compute and manipulate the support of monomial resolutions based on iterated mapping cones. We derive in this way algorithms to obtain homological and numerical invariants of monomial ideals without actually computing their resolution. Our computations include Betti diagrams, Hilbert series and irreducible decompositions. The algorithms derived by the method presented in the paper are efficient in practice as shown by experiments. [Copyright &y& Elsevier]

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]

Abstract: We describe an algorithm (VQE) for a variant of the real quantifier elimination problem (QE). The variant problem requires the input to satisfy a certain extra condition, and allows the output to be almost equivalent to the input. The motivation/rationale for studying such a variant QE problem is that many quantified formulas arising in applications do satisfy the extra conditions. Furthermore, in most applications, it is sufficient that the output formula is almost equivalent to the input formula. The main idea underlying the algorithm is to substitute the repeated projection step of CAD by a single projection without carrying out a parametric existential decision over the reals. We find that the algorithm can tackle important and challenging problems, such as numerical stability analysis of the widely-used MacCormack’s scheme. The problem has been practically out of reach for standard QE algorithms in spite of many attempts to tackle it. However, the current implementation of VQE can solve it in about 12 hours. This paper extends the results reported at the conference ISSAC 2009. [Copyright &y& Elsevier]

Abstract: In this paper we describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach. [Copyright &y& Elsevier]

Abstract: In this paper we present an algorithm for the computation of a diagonal form of a matrix over non-commutative Euclidean domain over a field with the help of Gröbner bases. We propose a general framework of Ore localizations of non-commutative -algebras and show its merits and constructiveness. It allows us to handle, among others, common operator algebras with rational coefficients. We introduce the splitting of the computation of a normal form (like the Jacobson form over simple domain) for matrices over Ore localizations into the diagonalization (the computation of a diagonal form of a matrix) and the normalization (the computation of the normal form of a diagonal matrix). These ideas are also used for the computation of the Smith normal form in the commutative case. We give a special algorithm for the normalization of a diagonal matrix over the rational Weyl algebra and present counterexamples to its idea over rational shift and -Weyl algebras. Our implementation of the algorithm in Singular:Plural relies on the fraction-free polynomial strategy, details of which will be described in the forthcoming article. It shows quite an impressive performance, compared with methods which directly use fractions. In particular, we experience quite a moderate swell of coefficients and obtain uncomplicated transformation matrices. We leave questions on the algorithmic complexity of this algorithm open, but we stress the practical applicability of the proposed method to a large class of non-commutative algebras. [Copyright &y& Elsevier]

Abstract: A Reed–Solomon code of length can be list decoded using the well-known Guruswami–Sudan algorithm. By a result of the interpolation part in this algorithm can be done in complexity , where denotes the designed list size and the multiplicity parameter. The parameters and are sometimes considered to be constants in the complexity analysis, but for high rate Reed–Solomon codes, their values can be very large. In this paper we will combine ideas from and the concept of key equations to get an algorithm that has complexity . This compares favorably to the complexities of other known interpolation algorithms. [Copyright &y& Elsevier]

Abstract: The Buchberger–Möller algorithm is a well-known efficient tool for computing the vanishing ideal of a finite set of points. If the coordinates of the points are (imprecise) measured data, the resulting Gröbner basis is numerically unstable. In this paper we introduce a numerically stable Approximate Vanishing Ideal (AVI) Algorithm which computes a set of polynomials that almost vanish at the given points and almost form a border basis. Moreover, we provide a modification of this algorithm which produces a Macaulay basis of an approximate vanishing ideal. We also generalize the Border Basis Algorithm ([Kehrein, A., Kreuzer, M., 2006. Computing border bases. J. Pure Appl. Algebra 205, 279–295]) to the approximate setting and study the approximate membership problem for zero-dimensional polynomial ideals. The algorithms are then applied to actual industrial problems. [Copyright &y& Elsevier]

Abstract: The main goal of this paper is to present an algorithm bounding the dimension of a linear system of plane curves of given degree (or monomial basis) with multiple points in general position. As a result we prove the Harbourne–Hirschowitz conjecture when the multiplicities of base points are bounded by 11. This gives a partial answer to the question of when bivariate polynomial interpolation is possible. [Copyright &y& Elsevier]

Abstract: This paper develops a validated numerical algorithm to compute the -norm, a norm which plays an important role in modern control. The method reduces the -norm computation problem to real root localization of polynomials and some Sturm chain tests, both of which can be executed in a manner which guarantees accuracy. A computational complexity estimate is also given. [Copyright &y& Elsevier]

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