Search

Multiplicative relations between the roots of a polynomial in Q [ x ] have drawn much attention in the field of arithmetic and algebra, while the problem of computing these relations is interesting to researchers in many other fields. In this paper, a sufficient condition is given for a polynomial f ∈ Q [ x ] to have only trivial multiplicative relations between its roots, which is a generalization of those sufficient conditions proposed in Smyth (1986) , Baron et al. (1995) and Dixon (1997). Based on the new condition, a subset E ⊂ Q [ x ] is defined and proved to be generic (i.e. , the set Q [ x ] \ E is very small). We develop an algorithm deciding whether a given polynomial f ∈ Q [ x ] is in E and returning a basis of the lattice consisting of the multiplicative relations between the roots of f whenever f ∈ E. The numerical experiments show that the new algorithm is very efficient for the polynomials in E. A large number of polynomials with much higher degrees, which were intractable before, can be handled successfully with the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we describe the method which we applied to successfully compute the primary decomposition of a certain ideal coming from applications in combinatorial algebra and algebraic statistics regarding conditional independence statements with hidden variables. While our method is based on the algorithm for primary decomposition by Gianni, Trager and Zacharias, we were not able to decompose the ideal using the standard form of that algorithm, nor by any other method known to us. [ABSTRACT FROM AUTHOR]

Abstract The growth of tropical geometry has generated significant interest in the tropical semiring in the past decade. However, there are other semirings in tropical algebra that provide more information, such as the symmetrized (max ⁡ , +) , Izhakian's extended and Izhakian–Rowen's supertropical semirings. In this paper we identify in which of these upper-bound semirings we can express symmetric polynomials in terms of elementary ones. We show that in the case of idempotent semirings we can do this precisely when the Frobenius property is satisfied, that in the case of supertropical semirings this is always possible, and that in non-trivial symmetrized semirings this is never possible. Our results allow us to determine the tropical algebra semirings where an analogue of the Fundamental Theorem of Symmetric Polynomials holds and to what extent. [ABSTRACT FROM AUTHOR]

In recent years, the log-concavity of the n -th root of a sequence { S n n } n ≥ 1 has been received a lot of attention. Recently, Sun posed the following conjecture in his new book: the sequences { a n n } n ≥ 2 and { b n n } n ≥ 1 are log-concave, where a n : = 1 n ∑ k = 0 n − 1 ( n − 1 k ) 2 ( n + k k ) 2 4 k 2 − 1 and b n : = 1 n 3 ∑ k = 0 n − 1 (3 k 2 + 3 k + 1) ( n − 1 k ) 2 ( n + k k ) 2. In this paper, two methods, semi-automatic and analytic methods, are used to confirm Sun's conjecture. The semi-automatic method relies on a criterion on the log-concavity of { S n n } n ≥ 1 given by us and a mathematica package due to Hou and Zhang, while the analytic method relies on a result due to Xia. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm which, given a point and a set of polynomials, constructs a single cylindrical cell containing the point, such that the given polynomials are sign-invariant in the computed cell. To represent a single cylindrical cell, a novel data structure is introduced. The algorithm works with this representation and proceeds incrementally, i.e., first constructing a cell representing the whole real space, and then iterating over the input polynomials, refining the cell at each step to ensure the sign-invariance of the current input polynomial. A merge procedure realizing this refinement is described, and its correctness is proven. The merge procedure is based on McCallum's projection operator, but uses geometric information relative to the input point to reduce the number of projection polynomials computed. The use of McCallum's operator implies the incompleteness of the algorithm in general. However, the algorithm is complete for well-oriented sets of polynomials. Moreover, the incremental approach described in this paper can be easily adapted to a different projection operator. The cell construction algorithm presented in this paper is an alternative to the “model-based” method described by Jovanović and de Moura in a 2012 paper. It generalizes the algorithm described by the first author in a 2013 paper, which could only produce full-dimensional cells, to allow for the construction of cells of arbitrary dimension. While a thorough comparison, whether analytical or empirical, of the new algorithm and the “model-based” approach will be the subject of future work, this paper provides preliminary justification for asserting the superiority of the new method. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider systems of algebraic and non-linear partial differential equations and inequations. We decompose these systems into so-called simple subsystems and thereby partition the set of solutions. For algebraic systems, simplicity means triangularity, square-freeness and non-vanishing initials. Differential simplicity extends algebraic simplicity with involutivity. We build upon the constructive ideas of J. M. Thomas and develop them into a new algorithm for disjoint decomposition. The present paper is a revised version of and includes the proofs of correctness and termination of our decomposition algorithm. In addition, we illustrate the algorithm with further instructive examples and describe its Maple implementation together with an experimental comparison to some other triangular decomposition algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we summarize our recent work on establishing, for the first time, an algorithm for the symbolic solution of linear boundary problems. We put our work in the frame of Wen-Tsun Wu’s approach to algorithmic problem solving in analysis, geometry, and logic by mapping the significant aspects of the underlying domains into algebra. We briefly compare this with the lines of thought of Wolfgang Groebner. For building up the necessary tower of domains in a generic and flexible way, we use the machinery of algorithmic functors introduced in our Theorema project. The essence of this concept is explained in the first section of the paper. The main part of the paper then describes our symbolic analysis approach to linear boundary problems, which hinges on three basic principles: (1) Differentiation as well as integration is treated axiomatically, setting up an algebraic data structure that can encode the problem statement (differential equation and boundary conditions) and suitable symbolic expressions for their solution (Green’s operators qua integral operators). (2) Abstract boundary problems are introduced as pairs consisting of an epimorphism on a vector space (abstract differential operator) and a subspace of its dual (abstract boundary conditions). (3) Operator algebras are treated by noncommutative polynomials, modulo Groebner bases for certain relation ideals. [Copyright &y& Elsevier]

Abstract: This is the continuation of Montes’ paper “On the canonical discussion of polynomial systems with parameters”. In this paper, we define the Minimal Canonical Comprehensive Gröbner System of a parametric ideal and fix under which hypothesis it exists and is computable. An algorithm to obtain a canonical description of the segments of the Minimal Canonical CGS is given, thus completing the whole MCCGS algorithm (implemented in Maple and Singular). We show its high utility for applications, such as automatic theorem proving and discovering, and compare it with other existing methods. A way to detect a counterexample to deny its existence is outlined, although the high number of tests done give evidence of the existence of the Minimal Canonical CGS. [Copyright &y& Elsevier]

Abstract: In this paper we describe software for an efficient factorization of polynomials over global fields . The algorithm for function fields was recently incorporated into our system KANT. The method is based on a generic algorithm developed by the second author in an earlier paper in this journal. Besides algorithmic aspects not contained in that paper we give details about the current implementation and about some complexity issues as well as a few illustrative examples. Also, a generalization of the application of LLL reduction for factoring polynomials over arbitrary global fields is developed. [Copyright &y& Elsevier]

Abstract: Maple’s symbolic evaluator, together with a feature that is usually known as the assume facility, implements a powerful form of conditional rewriting. In a previous paper the authors showed that Maple’s evaluation process can be recast as constraint contextual rewriting (CCR), a form of conditional rewriting that incorporates the services provided by a decision procedure through a well-specified interface. In the present paper, this analysis is extended to a component of the assume facility that deals with problems beyond linear arithmetic and that we call the general solver. This led to the discovery of a fault that causes Maple to return wrong results with some contexts. The reason for this is that the facility wrongly assumes that the general solver is complete in the sense that it uses all the available assumptions in the context. While a simple fix to this problem would reduce the logical strength of the assume facility, we show that a more general approach inspired by techniques available in CCR does not suffer from the problem and naturally leads to stronger forms of simplification. [Copyright &y& Elsevier]

Abstract: This paper advances the design of a unified model for the representation of search in first-order clausal theorem-proving, by extending to tableau-based subgoal-reduction strategies (e.g., model-elimination tableaux), the marked search-graph model, already introduced for ordering-based strategies, those that use (ordered) resolution, paramodulation/superposition, simplification, and subsumption. The resulting analytic marked search-graphs subsume AND–OR graphs, and allow us to represent those dynamic components, such as backtracking and instantiation of rigid variables, that have long been an obstacle to modelling subgoal-reduction strategies properly. The second part of the paper develops for analytic marked search-graphs the bounded search spaces approach to the analysis of infinite search spaces. We analyze how tableau inferences and backtracking affect the bounded search spaces during a derivation. Then, we apply this analysis to measure the effects of regularity and lemmatization by folding-up on search complexity, by comparing the bounded search spaces of strategies with and without these features. We conclude with a discussion comparing the marked search-graphs for tableaux, linear resolution, and ordering-based strategies, showing how this search model applies across these classes of strategies. [Copyright &y& Elsevier]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

Abstract: In this paper we give an insight into the behavior of signature-based Gröbner basis algorithms, like F5, G2V or SB, for inhomogeneous input. On the one hand, it seems that the restriction to sig-safe reductions puts a penalty on the performance. The lost connection between polynomial degree and signature degree can disallow lots of reductions and can lead to an overhead in the computations. On the other hand, the way critical pairs are sorted and corresponding s-polynomials are handled in signature-based algorithms is a very efficient one, strongly connected to sorting w.r.t. the well-known sugar degree of polynomials. [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: Multiobjective discrete programming is a well-known family of optimization problems with a large spectrum of applications. The linear case has been tackled by many authors during the past few years. However, the polynomial case has not been studied in detail due to its theoretical and computational difficulties. This paper presents an algebraic approach for solving these problems. We propose a methodology based on transforming the polynomial optimization problem to the problem of solving one or more systems of polynomial equations and we use certain Gröbner bases to solve these systems. Different transformations give different methodologies that are theoretically stated and compared by some computational tests via the algorithms that they induce. [Copyright &y& Elsevier]

Abstract: This paper explores the certification of properties of an efficient functional program in the area of symbolic computation: the calculation of Gröbner basis of a set of multivariate polynomials. Our experience in the development of industrial systems and the certification of some of its relevant properties has led us to use a methodology consisting of functional programs to write the code and the formal verification of fundamental properties. The functional language objective caml has been chosen to implement the program. To verify the properties two approaches are explored: manual proofs that reason directly over the source code of the algorithms, applying techniques like equational reasoning, and theorem provers that are used as a tool to help us certify a model of the real system. The chosen proof assistant is coq. Not only will the certification of the software be taken into consideration but also its efficiency. In addition, we present a graphical interface which eases the use of the program. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for solving a system of polynomials, in a domain of . It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule. We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of . The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem. [Copyright &y& Elsevier]

Abstract: The aim of the paper is to demonstrate the superiority of Cartan’s method over direct methods based on differential elimination for handling otherwise intractable equivalence problems. In this sense, using our implementation of Cartan’s method, we establish two new equivalence results. We establish when a system of second order ODEs is equivalent to flat system (second derivations are zero), and when a system of holomorphic PDEs with two independent variables and one dependent variable is flat. We consider the problem of finding transformation that brings a given equation to the target one. We shall see that this problem becomes algebraic when the symmetry pseudogroup of the target equation is zerodimensional. We avoid the swelling of the expressions, by using non-commutative derivations adapted to the problem. [Copyright &y& Elsevier]

Abstract: A well-known result due to J.T. Stafford asserts that a stably free left module over the Weyl algebras or –where is a field of characteristic 0–with is free. The purpose of this paper is to present a new constructive proof of this result as well as an effective algorithm for the computation of bases of . This algorithm, based on the new constructive proofs [Hillebrand, A., Schmale, W., 2001. Towards an effective version of a theorem of Stafford. J. Symbolic Comput. 32, 699–716; Leykin, A., 2004. Algorithmic proofs of two theorems of Stafford. J. Symbolic Comput. 38, 1535–1550] of J.T. Stafford’s result on the number of generators of left ideals of , performs Gaussian elimination on the formal adjoint of the presentation matrix of . We show that J.T. Stafford’s result is a particular case of a more general one asserting that a stably free left -module with is free, where denotes the stable rank of a ring . This result is constructive if the stability of unimodular vectors with entries in can be tested. Finally, an algorithm which computes the left projective dimension of a general left -module defined by means of a finite free resolution is presented. It allows us to check whether or not the left -module is stably free. [Copyright &y& Elsevier]

Abstract: Latin squares can be seen as multiplication tables of quasigroups, which are, in general, non-commutative and non-associative algebraic structures. The number of Latin squares having a fixed isotopism in their autotopism group is at the moment an open problem. In this paper, we use Gröbner bases to describe an algorithm that allows one to obtain the previous number. Specifically, this algorithm is implemented in Singular to obtain the number of Latin squares related to any autotopism of Latin squares of order up to 7. [Copyright &y& Elsevier]

Abstract: Buchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several -polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip -polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary for skipping -polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient. [Copyright &y& Elsevier]

Abstract: Triangular decompositions for systems of polynomial equations with variables, with exact coefficients, are well developed theoretically and in terms of implemented algorithms in computer algebra systems. However there is much less research concerning triangular decompositions for systems with approximate coefficients. In this paper we discuss the zero-dimensional case of systems having finitely many roots. Our methods depend on having approximations for all the roots, and these are provided by the homotopy continuation methods of Sommese, Verschelde and Wampler. We introduce approximate equiprojectable decompositions for such systems, which represent a generalization of the recently developed analogous concept for exact systems. We demonstrate experimentally the favorable computational features of this new approach, and give a statistical analysis of its error. [Copyright &y& Elsevier]

Abstract: In 1992, V. Weispfenning proved the existence of Comprehensive Gröbner Bases (CGB) and gave an algorithm for computing one. That algorithm was not very efficient and not canonical. Using his suggestions, A. Montes obtained in 2002 a more efficient algorithm (DISPGB) for Discussing Parametric Gröbner Bases. Inspired by its philosophy, V. Weispfenning defined, in 2002, how to obtain a Canonical Comprehensive Gröbner Basis (CCGB) for parametric polynomial ideals, and provided a constructive method. In this paper we use Weispfenning’s CCGB ideas to make substantial improvements on Montes’ DISPGB algorithm. It now includes rewriting of the discussion tree using the discriminant ideal and provides a compact and effective discussion. We also describe the new algorithms in the DPGB library containing the improved DISPGB as well as new routines for checking whether a given basis is a CGB or not, and for obtaining a CGB. Examples and tests are also provided. [Copyright &y& Elsevier]

Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]

Abstract: In this paper a new algorithm for computing the intersection of two rational ruled surfaces, given in parametric/parametric or implicit/parametric form, is presented. This problem can be considered as a quantifier elimination problem over the reals with an additional geometric flavor which is one of the central themes in V. Weispfenning research. After the implicitization of one of the surfaces, the intersection problem is reduced to finding the zero set of a bivariate equation which represents the parameter values of the intersection curve, as a subset of the other surface. The algorithm, which involves both symbolic and numerical computations, determines the topology of the intersection curve as an intermediate step and eliminates extraneous solutions that might arise in the implicitization process. [Copyright &y& Elsevier]

Abstract: In this paper we describe an algorithm that takes as input a description of a semi-algebraic set , defined by a Boolean formula with atoms of the form for , and outputs the first Betti numbers of , . The complexity of the algorithm is , where and , which is singly exponential in for any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler–Poincaré characteristic, the zeroth and the first Betti numbers. [Copyright &y& Elsevier]

Abstract: In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for “witness conjectures”. [Copyright &y& Elsevier]

Abstract: Consider the class of exp–log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let be such an exp–log constant and let be its size as an expression. Witness conjectures attempt to give bounds for the number of decimal digits which need to be evaluated in order to test whether equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by 1. In that context, several witness conjectures have appeared in the literature and the strongest one states that it is possible to choose . In this paper we give a counterexample to this conjecture. We also extend it so as to cover similar, polynomial witness conjectures. [Copyright &y& Elsevier]

Abstract: Algebraic surfaces–which are frequently used in geometric modelling–are represented either in implicit or parametric form. Several techniques for parametrizing a rational algebraic surface as a whole exist. However, in many applications, it suffices to parametrize a small portion of the surface. This motivates the analysis of local parametrizations, i.e., parametrizations of a small neighborhood of a given point of the surface . In this paper we introduce several techniques for generating such parametrizations for nonsingular cubic surfaces. For this class of surfaces, it is shown that the local parametrization problem can be solved for all points, and any such surface can be covered completely. [Copyright &y& Elsevier]

Abstract: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given. [Copyright &y& Elsevier]

Abstract: In this paper we present a generic algorithm for factoring polynomials over global fields . As efficient implementations of that algorithm for number fields and function fields differ substantially, these cases will be treated separately. Complexity issues and implementations will be discussed in part II which also contains illustrative examples. [Copyright &y& Elsevier]

Abstract: A well-known lemma of Suslin says that for a commutative ring if is unimodular where is monic and , then there exist such that the ideal generated by equals . This lemma played a central role in the resolution of Serre’s Conjecture. In the case where contains a set of cardinality greater than such that is invertible for each in , we prove that the can simply correspond to the elementary operations , , where . These efficient elementary operations enable us to give new and simple algorithms for reducing unimodular rows with entries in to using elementary operations in the case where is an infinite field. Another feature of this paper is that it shows that the concrete local–global principles can produce competitive complexity bounds. [Copyright &y& Elsevier]

Abstract: The concept of a -basis was introduced in the case of parametrized curves in 1998 and generalized to the case of rational ruled surfaces in 2001. The -basis can be used to recover the parametric equation as well as to derive the implicit equation of a rational curve or surface. Furthermore, it can be used for surface reparametrization and computation of singular points. In this paper, we generalize the notion of a -basis to an arbitrary rational parametric surface. We show that: (1) the -basis of a rational surface always exists, the geometric significance of which is that any rational surface can be expressed as the intersection of three moving planes without extraneous factors; (2) the -basis is in fact a basis of the moving plane module of the rational surface; and (3) the -basis is a basis of the corresponding moving surface ideal of the rational surface when the base points are local complete intersections. As a by-product, a new algorithm is presented for computing the implicit equation of a rational surface from the -basis. Examples provide evidence that the new algorithm is superior than the traditional algorithm based on direct computation of a Gröbner basis. Problems for further research are also discussed. [Copyright &y& Elsevier]

Abstract: Let be a finite group. It is easy to compute the character of corresponding to a given complex representation, but much more difficult to compute a representation affording a given character. In part this is due to the fact that a class of equivalent representations contains no natural canonical representation. Although there is a large literature devoted to computing representations, and methods are known for particular classes of groups, we know of no general method which has been proposed which is practical for any but small groups. We shall describe an algorithm for computing an irreducible matrix representation which affords a given character of a given group . The algorithm uses properties of the structure of which can be computed efficiently by a program such as GAP, theoretical results from representation theory, theorems from group theory (including the classification of finite simple groups), and linear algebra. All results in this paper have been implemented in the GAP package REPSN. [Copyright &y& Elsevier]

Abstract: In this paper we present some algorithms for computing an irreducible decomposition of an ideal in a polynomial ring where is an arbitrary effective field. [Copyright &y& Elsevier]

In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms. [Copyright &y& Elsevier]

The short product of two power series is the meaningful part of the product of these objects, i.e., ∑i+j. Mulders (AAECC 11 (2000) 69) gives an algorithm to compute a short product faster than the full product in the case of Karatsuba’s multiplication (Karatsuba and Ofman, Dokl. Akad. Nauk SSSR 145 (1962) 293). This algorithm works by selecting a cutoff point k and performing a full k×k product and two (n−k)×(n−k) short products recursively. Mulders also gives a heuristically optimal cutoff point βn. In this paper, we determine the optimal cutoff point in Mulders’ algorithm. We also give a slightly more general description of Mulders’ method. [Copyright &y& Elsevier]

Let An(k) be the Weyl algebra, with k a field of characteristic zero. It is known that every projective finitely generated left module is free or isomorphic to a left ideal. Let M be a left submodule of a free module. In this paper we give an algorithm to compute the projective dimension of M. If M is projective and rank(M)≥2 we give a procedure to find a basis. [Copyright &y& Elsevier]

In this paper we study plane conic geometry, particularly different representations of geometric constructions and relations in plane conic geometry, with Cayley and bracket algebras. We propose three powerful simplification techniques for bracket computation involving conic points, and an algorithm for rational Cayley factorization in conic geometry. The factorization algorithm is not a general one, but works for all the examples tried so far. We establish a series of elimination rules for various geometric constructions based on the idea of bracket-oriented representation and elimination, and an algorithm for optimal representation of the conclusion in theorem proving. These techniques can be used in any applications involving brackets and conics. In theorem proving, our algorithm based on these techniques can produce extremely short proofs for difficult theorems in conic geometry. [Copyright &y& Elsevier]

In this paper we present a theoretical and algorithmic analysis on the normality of rational parametrizations of algebraic plane curves over arbitrary fields of characteristic zero. If the field is algebraically closed we give an algorithm to decide whether a parametrization is proper and, if not, a normal parametrization is computed. If the field is not algebraically closed the problem is more complicated, and a degenerated situation may appear. We classify the degenerations in strong and weak degenerations, and an algorithm to decide this phenomenon is derived. Furthermore, we prove that if the parametrization is strongly degenerated then the curve cannot be normally parametrized, but weak degenerations can be resolved, and an algorithm to reparametrize the input weakly degenerated parametrization into a non-degenerated one is given. In addition, we show how these results can be applied and improved to the case of real rational curves. In this case, we present an algorithm that decides whether a given real parametrization can be normally parametrized over the reals, and that computes such a parametrization if it exists. [Copyright &y& Elsevier]