Serre’s conjecture, stating that every finitely generated projective module over a polynomial ring is free, was proven by Quillen and Suslin independently in 1976. An equivalent form of the Quillen-Suslin theorem says, “Every unimodular row over a polynomial ring can be completed to a unimodular matrix.” In this paper, we generalize the Quillen-Suslin theorem to the parametric case and present an algorithm to construct the unimodular completion matrix system for any polynomial vector with parameters. Specifically, we first determine the conditions on the parameters under which the vector is unimodular using the comprehensive Gröbner system. Furthermore, we use a constructive method to find a finite partition of the parameter space such that, for each branch, the vector under specializations can be completed into a unimodular matrix in the same form. Since the method is constructive, we present an explicit algorithm to construct the unimodular completion matrix system for any polynomial vector with parameters. The correctness and termination of the algorithm have been proven, and an example is provided to demonstrate how the algorithm works.

A new algorithm for computing the parametric greatest common right divisor (GCRD) of a set of parametric Ore polynomials is presented in this paper. The algorithm is based on Gröbner bases for modules. Inspired by the resultant theory in Ore polynomial rings, the Sylvester matrix is defined for a set of Ore polynomials. In the case of non-parametric polynomials, the GCRD of Ore polynomials can be obtained by computing the row echelon form of the Sylvester matrix. For the parametric case, the parametric Sylvester matrix is also defined in the paper. Based on this, under the assumption that the specializations commute with the conjugate operator and derivation in the Ore polynomial ring, the parametric GCRD of parametric Ore polynomials can be obtained by computing the Gröbner basis for the module generated by rows of the parametric Sylvester matrix. As a consequence, the algorithm for computing the parametric GCRD is presented in detail and has been implemented in the computer algebra system Singular.

A fundamental challenge in robot perception is the coupling of the sensor pose and robot pose. This has led to research in active vision where robot pose is changed to reorient the sensor to areas of interest for perception. Further, egomotion such as jitter, and external effects such as wind and others affect perception requiring additional effort in software such as image stabilization. This effect is particularly pronounced in micro-air vehicles and micro-robots who typically are lighter and subject to larger jitter but do not have the computational capability to perform stabilization in real-time. We present a novel microelectromechanical (MEMS) mirror LiDAR system to change the field of view of the LiDAR independent of the robot motion. Our design has the potential for use on small, low-power systems where the expensive components of the LiDAR can be placed external to the small robot. We show the utility of our approach in simulation and on prototype hardware mounted on a UAV. We believe that this LiDAR and its compact movable scanning design provide mechanisms to decouple robot and sensor geometry allowing us to simplify robot perception. We also demonstrate examples of motion compensation using IMU and external odometry feedback in hardware.

This paper is concerned with a property of modules over a polynomial ring and its application in multivariate polynomial matrix factorizations. We construct a specific polynomial such that the product of the polynomial and a nonzero vector in a module over a polynomial ring can be represented by the elements in a maximum linearly independent vector set of the module over the polynomial ring. Based on this property, a relationship between a rank-deficient matrix and any of its full row rank submatrices is presented. By this result, we show that the problem for general factorizations of rank-deficient matrices can be translated into that of any of their full row rank submatrices in the regular case. Then many results on factorizations of full row rank matrices, such as zero prime factorizations, minor prime factorizations and factor prime factorizations, can be extended to the rank-deficient case. We implement the algorithm of general factorizations for rank-deficient matrices on the computer algebra system Maple, and two examples are given to illustrate the algorithm.

An algorithm for computing the rational univariate representation of zero-dimensional ideals with parameters is presented in the paper. Different from the rational univariate representation of zero-dimensional ideals without parameters, the number of zeros of zero-dimensional ideals with parameters under various specializations is different, which leads to choosing and checking the separating element, the key to computing the rational univariate representation, is difficult. In order to pick out the separating element, by partitioning the parameter space we can ensure that under each branch the ideal has the same number of zeros. Subsequently based on the extended subresultant theorem for parametric cases, the separating element corresponding to each branch is chosen with the further partition of parameter space. Finally, with the help of parametric greatest common divisor theory a finite set of the rational univariate representation of zero-dimensional ideals with parameters can be obtained.

This paper is concerned with the factorization and equivalence problems of multivariate polynomial matrices. We present a new criterion for the existence of matrix factorizations for a class of multivariate polynomial matrices, and prove that these matrix factorizations are unique. Based on this new criterion and the constructive proof process, we give an algorithm to compute a matrix factorization of a multivariate polynomial matrix. After that, we put forward a sufficient and necessary condition for the equivalence of square polynomial matrices: a square polynomial matrix is equivalent to a diagonal triangle if it satisfies the condition. An illustrative example is given to show the effectiveness of the matrix equivalence theorem.

An extended greatest common divisor (GCD) algorithm for parametric univariate polynomials is presented in this paper. This algorithm computes not only the GCD of parametric univariate polynomials in each constructible set but also the corresponding representation coefficients (or multipliers) for the GCD expressed as a linear combination of these parametric univariate polynomials. The key idea of our algorithm is that for non-parametric case the GCD of arbitrary finite number of univariate polynomials can be obtained by computing the minimal Gröbner basis of the ideal generated by those polynomials. But instead of computing the Gröbner basis of the ideal generated by those polynomials directly, we construct a special module by adding the unit vectors which can record the representation coefficients, then obtain the GCD and representation coefficients by computing a Gröbner basis of the module. This method can be naturally generalized to the parametric case because of the comprehensive Gröbner systems for modules. As a consequence, we obtain an extended GCD algorithm for parametric univariate polynomials. More importantly, we apply the proposed extended GCD algorithm to the computation of Smith normal form, and give the first algorithm for reducing a univariate polynomial matrix with parameters to its Smith normal form.

A new efficient algorithm for computing a parametric greatest common divisor (GCD) of parametric multivariate polynomials over k[u][x] is presented. The algorithm is based on a well-known simple insight that the GCD of two multivariate polynomials (non-parametric as well as parametric) can be extracted using the generator of the quotient ideal of a polynomial with respect to the second polynomial. And, further, this generator can be obtained by computing a minimal Gröbner basis of the quotient ideal. The main attraction of this idea is that it generalizes to the parametric case for which a comprehensive Gröbner basis is constructed for the parametric quotient ideal. It is proved that in a minimal comprehensive Gröbner system of a parametric quotient ideal, each branch of specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric GCD of that branch is obtained by division. This algorithm does not need to consider whether parametric polynomials are primitive w.r.t. the main variable. This is in sharp contrast to two algorithms recently proposed by Nagasaka (ISSAC, 2017). The resulting algorithm is not only conceptually simple to understand but is considerably efficient. The proposed algorithm and both of Nagasaka's algorithms have been implemented in Singular (available at http://www.mmrc.iss.ac.cn/~dwang/software.html), and their performance is compared on a number of examples. For more than two polynomials, this process can be repeated by considering pairs of polynomials; the efficiency in that case becomes even more evident.

A new algorithm, which combines the GVW algorithm with the Mora normal form algorithm, is presented to compute the standard bases of ideals in a local ring. Since term orders in local ring are not well-orderings, there may not be a minimal signature in an infinite set, and we can not extend the GVW algorithm from a polynomial ring to a local ring directly. Nevertheless, when given an anti-graded order in R and a term-over-position order in Rm that are compatible, we can construct a special set such that it has a minimal signature, where R , Rm are a local ring and a R -module, respectively. That is, for any given polynomial v0 ın R, the set consisting of signatures of pairs (u,v)ın Rm x R has a minimal element, where the leading power products of v and v0 are equal. In this case, we prove a cover theorem in R , and use three criteria (syzygy criterion, signature criterion and rewrite criterion) to discard useless J-pairs without any reductions. Mora normal form algorithm is also extended to do regular top-reductions in Rm x R, and the correctness and termination of the algorithm are proved. The proposed algorithm has been implemented in the computer algebra system Maple, and experiment results show that most of J-pairs can be discarded by three criteria in the examples.

We investigate how to factorize a multivariate polynomial matrix into the product of two matrices. There are two major parts. The first is a factorization theorem, which asserts that a multivariate polynomial matrix whose lower order minors satisfy certain conditions admits a matrix factorization. Our theory is a generalization to the previous results given by Lin et.al [16] and Liu et.al [17]. The second is the implementation for factorizing polynomial matrices. According to the proof of factorization theorem, we construct a main algorithm which extends the range of polynomial matrices that can be factorized. In this algorithm, two critical steps are involved in how to compute a zero left prime matrix and a unimodular matrix. Firstly, based on the famous Quillen-Suslin theorem, a new sub-algorithm is presented to obtain a zero left prime matrix by calculating the bases of the syzygies of two low-order polynomial matrices. Experiments show that it is more efficient than the algorithm constructed by Wang and Kwong [31]. Secondly, some auxiliary information provided by the above new sub-algorithm is used to construct a unimodular matrix. As a consequence, the main algorithm extends the application range of the constructive algorithm in [17]. We implement all the algorithms proposed above on the computer algebra system Singular and give a nontrivial example to show the process of the main algorithm.

We initiate the study of metric embeddings with outliers. Given some finite metric space we wish to remove a small set of points and to find either an isometric or a low-distortion embedding of the remaining points into some host metric space. This is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. We present polynomial-time approximation algorithms for computing outlier embeddings into Euclidean space, trees, and ultrametrics. In the case of isometric embeddings the objective is to minimize the number of outliers, while in the case of non-isometries we have a bi-criteria optimization problem where the goal is to minimize both the number of outliers and the distortion. We complement our approximation algorithms with NP-hardness results for these problems. We conclude with a brief experimental evaluation of our non-isometric outlier embedding on synthetic and real-world data sets.

Signature-based algorithms, including F5, F5C, G2V and GVW, are efficient algorithms for computing Gröbner bases in commutative polynomial rings. In this paper, we present a signature-based algorithm to compute Gröbner bases in solvable polynomial algebras which include usual commutative polynomial rings and some non-commutative polynomial rings like Weyl algebra. The generalized Rewritten Criterion (discussed in Sun and Wang, ISSAC 2011) is used to reject redundant computations. When this new algorithm uses the partial order implied by GVW, its termination is proved without special assumptions on computing orders of critical pairs. Data structures similar to F5 can be used to speed up this new algorithm, and Gröbner bases of syzygy modules of input polynomials can be obtained from the outputs easily. Experimental data show that most redundant computations can be avoided in this new algorithm.

In Kapur et al (ISSAC, 2010), a new method for computing a comprehensive Grobner system of a parameterized polynomial system was proposed and its efficiency over other known methods was effectively demonstrated. Based on those insights, a new approach is proposed for computing a comprehensive Grobner basis of a parameterized polynomial system. The key new idea is not to simplify a polynomial under various specialization of its parameters, but rather keep track in the polynomial, of the power products whose coefficients vanish; this is achieved by partitioning the polynomial into two parts-nonzero part and zero part for the specialization under consideration. During the computation of a comprehensive Grobner system, for a particular branch corresponding to a specialization of parameter values, nonzero parts of the polynomials dictate the computation, i.e., computing S-polynomials as well as for simplifying a polynomial with respect to other polynomials; but the manipulations on the whole polynomials (including their zero parts) are also performed. Grobner basis computations on such pairs of polynomials can also be viewed as Grobner basis computations on a module. Once a comprehensive Grobner system is generated, both nonzero and zero parts of the polynomials are collected from every branch and the result is a faithful comprehensive Grobner basis, to mean that every polynomial in a comprehensive Grobner basis belongs to the ideal of the original parameterized polynomial system. This technique should be applicable to other algorithms for computing a comprehensive Grobner system as well, thus producing both a comprehensive Grobner system as well as a faithful comprehensive Grobner basis of a parameterized polynomial system simultaneously. The approach is exhibited by adapting the recently proposed method for computing a comprehensive Grobner system in (ISSAC, 2010) for computing a comprehensive Grobner basis. The timings on a collection of examples demonstrate that this new algorithm for computing comprehensive Grobner bases has better performance than other existing algorithms.

A generalized criterion for signature related algorithms to compute Gröbner basis is proposed in this paper. Signature related algorithms are a popular kind of algorithms for computing Gröbner basis, including the famous F5 algorithm, the F5C algorithm, the extended F5 algorithm and the GVW algorithm. The main purpose of current paper is to study in theory what kind of criteria is correct in signature related algorithms and provide a generalized method to develop new criteria. For this purpose, a generalized criterion is proposed. The generalized criterion only relies on a general partial order defined on a set of polynomials. When specializing the partial order to appropriate specific orders, the generalized criterion can specialize to almost all existing criteria of signature related algorithms. For admissible partial orders, a proof is presented for the correctness of the algorithm that is based on this generalized criterion. And the partial orders implied by the criteria of F5 and GVW are also shown to be admissible in this paper. More importantly, the generalized criterion provides an effective method to check whether a new criterion is correct as well as to develop new criteria for signature related algorithms.

A new algorithm for computing a comprehensive Gröbner system of a parametric polynomial ideal over k[U][X] is presented. This algorithm generates fewer branches (segments) compared to Suzuki and Sato's algorithm as well as Nabeshima's algorithm, resulting in considerable efficiency. As a result, the algorithm is able to compute comprehensive Gröbner systems of parametric polynomial ideals arising from applications which have been beyond the reach of other well known algorithms. The starting point of the new algorithm is Weispfenning's algorithm with a key insight by Suzuki and Sato who proposed computing first a Gröbner basis of an ideal over k[U,X] before performing any branches based on parametric constraints. Based on Kalkbrener's results about stability and specialization of Gröbner basis of ideals, the proposed algorithm exploits the result that along any branch in a tree corresponding to a comprehensive Gröbner system, it is only necessary to consider one polynomial for each nondivisible leading power product in k(U)[X] with the condition that the product of their leading coefficients is not 0; other branches correspond to the cases where this product is 0. In addition, for dealing with a disequality parametric constraint, a probabilistic check is employed for radical membership test of an ideal of parametric constraints. This is in contrast to a general expensive check based on Rabinovitch's trick using a new variable as in Nabeshima's algorithm. The proposed algorithm has been implemented in Magma and experimented with a number of examples from different applications. Its performance (vis a vie number of branches and execution timings) has been compared with the Suzuki-Sato's algorithm and Nabeshima's speed-up algorithm. The algorithm has been successfully used to solve the famous P3P problem from computer vision.