Consider a matrix F ε K [x]^mxn of univariate polynomials over a field K. We study the problem of computing the column rank profile of F. To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of F with a rank-sensitive complexity of O~ (rw-2n(m+d)) operations in K. Here, D is the sum of row degrees of F, w is the exponent of matrix multiplication, and O~ (.) hides logarithmic factors.

Given a rectangular matrix F ∈ K[x]mxn with m < n of univariate polynomials over a field K. we give an efficient algorithm for computing a unimodular completion of F. Our algorithm is deterministic and computes such a completion, when it exists, with cost O~ (nωs) field operations from K. Here s is the average of the m largest column degrees of F and ω is the exponent on the cost of matrix multiplication. Here O~ is big-O but with log factors removed. If a unimodular completion does not exist for F, our algorithm computes a unimodular completion for a right cofactor of a column basis of F, or equivalently, computes a completion that preserves the generalized determinant.

Given a matrix of univariate polynomials over a field K, its columns generate a K[x]-module. We call any basis of this module a column basis of the given matrix. Matrix gcds and matrix normal forms are examples of such module bases. In this paper we present a deterministic algorithm for the computation of a column basis of an m x n input matrix with m ≤ n. If s is the average column degree of the input matrix, this algorithm computes a column basis with a cost of Õ(nmω-1s) field operations in K. Here the soft-O notation is Big-O with log factors removed while ω is the exponent of matrix multiplication. Note that the average column degree s is bounded by the commonly used matrix degree that is also the maximum column degree of the input matrix.

In this paper we present a deterministic algorithm for the computation of a minimal nullspace basis of an m x n input matrix of univariate polynomials over a field K with m ≤ n. This algorithm computes a minimal nullspace basis of a degree d input matrix with a cost of O~ (nω ⌈md/n⌉) field operations in K. Here the soft-O notation is Big-O with log factors removed while ω is the exponent of matrix multiplication. The same algorithm also works in the more general situation on computing a shifted minimal nullspace basis, with a given degree shift [equation] whose entries bound the corresponding column degrees of the input matrix. In this case if ρ is the sum of the m largest entries of s, then a s-minimal right nullspace basis can be computed with a cost of O~(nωρ/m) field operations.

In this paper we give an efficient algorithm for computation of order basis of a matrix of power series. For a problem with an m x n input matrix over a field K, m ≤ n, and order σ, our algorithm uses O(MM(n, ⊂O~(nω⌈mσ/n⌉) field operations in B.K, where the soft-O notation O~ is Big O with log factors omitted and MM(n,d) denotes the cost of multiplying two polynomial matrices with dimension n and degree d. The algorithm extends earlier work of Storjohann, whose method can be used to find a subset of an order basis that is within a specified degree bound δ using O~(MM(n,δ)) field operations for δ≥⌈ mσ/n⌉.