Search

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]

Abstract: The tensor decomposition addressed in this paper may be seen as a generalization of Singular Value Decomposition of matrices. We consider general multilinear and multihomogeneous tensors. We show how to reduce the problem to a truncated moment matrix problem and give a new criterion for flat extension of Quasi-Hankel matrices. We connect this criterion to the commutation characterization of border bases. A new algorithm is described. It applies for general multihomogeneous tensors, extending the approach on binary forms by J.J. Sylvester. An example illustrates the algebraic operations involved in this approach and how the decomposition can be recovered from eigenvector computation. [Copyright &y& Elsevier]

Abstract: In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming its complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of Mourrain and Trébuchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) allow the incorporation of additional polynomials, e.g., to restrict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gröbner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal. [Copyright &y& Elsevier]

Abstract: This paper is a sequel to “Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases” (). We present a new fraction-free algorithm for the computation of a diagonal form of a matrix over a certain non-commutative Euclidean domain over a computable field with the help of Gröbner bases. This algorithm is formulated in a general constructive framework of non-commutative Ore localizations of -algebras (OLGAs). We use the splitting of the computation of a normal form for matrices over Ore localizations into the diagonalization and the normalization processes. Both of them can be made fraction-free. For a given matrix over an OLGA , we provide a diagonalization algorithm to compute and with fraction-free entries such that holds and is diagonal. The fraction-free approach allows to obtain more information on the associated system of linear functional equations and its solutions, than the classical setup of an operator algebra with coefficients in rational functions. In particular, one can handle distributional solutions together with, say, meromorphic ones. We investigate Ore localizations of common operator algebras over and use them in the unimodularity analysis of transformation matrices . In turn, this allows to lift the isomorphism of modules over an OLGA Euclidean domain to a smaller polynomial subring of it. We discuss the relation of this lifting with the solutions of the original system of equations. Moreover, we prove some new results concerning normal forms of matrices over non-simple domains. Our implementation in the computer algebra system Singular:Plural follows the fraction-free strategy and shows impressive performance, compared with methods which directly use fractions. In particular, we experience a moderate swell of coefficients and obtain simple transformation matrices. Thus the method we propose is well suited for solving nontrivial practical problems. [Copyright &y& Elsevier]

Abstract: In this paper, we present two algorithms for the computation of a shifted order basis of an matrix of power series over a field with . For a given order and balanced shift the first algorithm determines an order basis with a cost of field operations in , where is the exponent of matrix multiplication. Here an input shift is balanced when . This extends the earlier work of Storjohann which only determines a subset of an order basis that is within a specified degree bound using field operations for . While the first algorithm addresses the case when the column degrees of a complete order basis are unbalanced given a balanced input shift, it is not efficient in the case when an unbalanced shift results in the row degrees also becoming unbalanced. We present a second algorithm which balances the high degree rows and computes an order basis also using field operations in the case that the shift is unbalanced but satisfies the condition . This condition essentially allows us to locate those high degree rows that need to be balanced. This extends the earlier work by the authors from ISSAC’09. [Copyright &y& Elsevier]

Abstract: In this paper we describe a generalisation and adaptation of Kedlaya’s algorithm for computing the zeta-function of a hyperelliptic curve over a finite field of odd characteristic that the author used for the implementation of the algorithm in the Magma library. We generalise the algorithm to the case of an even degree model. We also analyse the adaptation of working with the rather than the differential basis. This basis has the computational advantage of always leading to an integral transformation matrix whereas the latter fails to in small genus cases. There are some theoretical subtleties that arise in the even degree case where the two differential bases actually lead to different redundant eigenvalues that must be discarded. [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: Let be a linear differential operator, where is an effective algebraically closed subfield of . It can be shown that the differential Galois group of  is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in local exponential groups. Moreover, there exist fast algorithms for the approximation of the entries of these matrices. In this paper, we present a numeric–symbolic algorithm for the computation of the closed algebraic subgroup generated by a finite number of invertible matrices. Using the above results, this yields an algorithm for the computation of differential Galois groups, when computing with a sufficient precision. Even though there is no straightforward way to find a “sufficient precision” for guaranteeing the correctness of the end result, it is often possible to check a posteriori whether the end result is correct. In particular, we present a non-heuristic algorithm for the factorization of linear differential operators. [Copyright &y& Elsevier]

Abstract: In this paper we give formulas for performing row reduction of a matrix of Ore polynomials in a fraction-free way. The reductions can be used for finding the rank and left nullspace of such matrices. When specialized to matrices of skew polynomials our reduction can be used for computing a weak Popov form of such matrices and for computing a GCRD and an LCLM of skew polynomials or matrices of skew polynomials. The algorithm is suitable for computation in exact arithmetic domains where the growth of coefficients in intermediate computations is a concern. This coefficient growth is controlled by using fraction-free methods. The known factor can be predicted and removed efficiently. [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: 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: 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]