Search

One method to determine whether or not a system of partial differential equations is consistent is to attempt to construct a solution using merely the “algebraic data” associated to the system. In technical terms, this translates to the problem of determining the existence of regular realizations of differential kernels via their possible prolongations. In this paper we effectively compute an improved upper bound for the number of prolongations needed to guarantee the existence of such realizations, which ultimately produces solutions to many types of systems of partial differential equations. This bound has several applications, including an improved upper bound for the order of characteristic sets of prime differential ideals. We obtain our upper bound by proving a new result on the growth of the Hilbert–Samuel function, which may be of independent interest. [ABSTRACT FROM AUTHOR]

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]

A tensor T , in a given tensor space, is said to be h -identifiable if it admits a unique decomposition as a sum of h rank one tensors. A criterion for h -identifiability is called effective if it is satisfied in a dense, open subset of the set of rank h tensors. In this paper we give effective h -identifiability criteria for a large class of tensors. We then improve these criteria for some symmetric tensors. For instance, this allows us to give a complete set of effective identifiability criteria for ternary quintic polynomials. Finally, we implement our identifiability algorithms in Macaulay2. [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]

Abstract: The context of this work is the design of a software, called MEMSALab, dedicated to the automatic derivation of multiscale models of arrays of micro- and nanosystems. In this domain a model is a partial differential equation. Multiscale methods approximate it by another partial differential equation which can be numerically simulated in a reasonable time. The challenge consists in taking into account a wide range of geometries combining thin and periodic structures with the possibility of multiple nested scales. In this paper we present a transformation language that will make the development of MEMSALab more feasible. It is proposed as a Maple™ package for rule-based programming, rewriting strategies and their combination with standard Maple™ code. We illustrate the practical interest of this language by using it to encode two examples of multiscale derivations, namely the two-scale limit of the derivative operator and the two-scale model of the stationary heat equation. [Copyright &y& Elsevier]

Abstract: Automated verification of memory safety and functional correctness for heap-manipulating programs has been a challenging task, especially when dealing with complex data structures with strong invariants involving both shape and numerical properties. Existing verification systems usually rely on users to supply annotations to guide the verification, which can be cumbersome and error-prone by hand and can significantly restrict the usability of the verification system. In this paper, we reduce the need for some user annotations by automatically inferring loop invariants over an abstract domain with both shape and numerical information. Our loop invariant synthesis is conducted automatically by a fixed-point iteration process, equipped with newly designed abstraction mechanism, together with join and widening operators over the combined domain. We have also proven the soundness and termination of our approach. Initial experiments confirm that we can synthesise loop invariants with non-trivial constraints. [Copyright &y& Elsevier]

Abstract: This paper introduces a new method for interpolation of Boolean functions using Boolean polynomials. It was motivated by some problems arising from computational biology, for reverse engineering the structure of mechanisms in gene regulatory networks. For this purpose polynomial expressions have to be generated, which match known state combinations observed during experiments. Earlier approaches using Gröbner techniques have not been powerful enough to treat real-world applications. The proposed method avoids expensive Gröbner basis computations completely by directly calculating reduced normal forms. The problem statement can be described by Boolean polynomials, i.e. polynomials with coefficients in and a degree bound of one for each variable. Therefore, the reference implementations mentioned in this work are built on the top of the PolyBoRi framework, which has been designed exclusively for the treatment of this special class of polynomials. A series of randomly generated examples is used to demonstrate the performance of the direct method. It is also compared with other approaches, which incorporate Gröbner basis computations. [Copyright &y& Elsevier]

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: One way of solving polynomial systems of equations is by computing a Gröbner basis, setting up an eigenvalue problem and then computing the eigenvalues numerically. This so-called eigenvalue method is an excellent bridge between symbolic and numeric computation, enabling the solution of larger systems than with purely symbolic methods. We investigate the case that the system of polynomial equations has symmetries. For systems with symmetry, some matrices in the eigenvalue method turn out to have special structure. The exploitation of this special structure is the aim of this paper. For theoretical development we make use of SAGBI bases of invariant rings. Examples from applications illustrate our new approach. [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: This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Gröbner bases and polynomial spectral factorization which can be observed through the sum of roots, and allows us to perform polynomial spectral factorization in the presence of real parameters. It is discussed that parametric polynomial spectral factorization enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs two quantifier elimination techniques. This proposed approach is demonstrated in a numerical example of a particular control problem. [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]

Abstract: The formula in Corollary 2.2 in [Hernández, X., Miret, J., Xambó, S., 2007. Computing the characteristic numbers of the variety of nodal plane cubics in . Journal of Symbolic Computation 42 (1–2), 192–202] should be . This mistake does not affect the rest of the paper. We also take the opportunity to supply details of the proof that were only hinted at there. [Copyright &y& Elsevier]