ML p(r)ior | Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

### Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

2016-02-01
1602.00710 | cs.SC
We give a Las Vegas algorithm which computes the shifted Popov form of an $m \times m$ nonsingular polynomial matrix of degree $d$ in expected $\widetilde{\mathcal{O}}(m^\omega d)$ field operations, where $\omega$ is the exponent of matrix multiplication and $\widetilde{\mathcal{O}}(\cdot)$ indicates that logarithmic factors are omitted. This is the first algorithm in $\widetilde{\mathcal{O}}(m^\omega d)$ for shifted row reduction with arbitrary shifts. Using partial linearization, we reduce the problem to the case $d \le \lceil \sigma/m \rceil$ where $\sigma$ is the generic determinant bound, with $\sigma / m$ bounded from above by both the average row degree and the average column degree of the matrix. The cost above becomes $\widetilde{\mathcal{O}}(m^\omega \lceil \sigma/m \rceil)$, improving upon the cost of the fastest previously known algorithm for row reduction, which is deterministic. Our algorithm first builds a system of modular equations whose solution set is the row space of the input matrix, and then finds the basis in shifted Popov form of this set. We give a deterministic algorithm for this second step supporting arbitrary moduli in $\widetilde{\mathcal{O}}(m^{\omega-1} \sigma)$ field operations, where $m$ is the number of unknowns and $\sigma$ is the sum of the degrees of the moduli. This extends previous results with the same cost bound in the specific cases of order basis computation and M-Pad\'e approximation, in which the moduli are products of known linear factors.

Highlights - Most important sentences from the article

# Related Articles

2019-05-10
1905.04356 | cs.SC

Complexity bounds for many problems on matrices with univariate polynomial entries have been improve… show more

Highlights - Most important sentences from the article

2019-03-08
1903.03278 | cs.SC

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Ga… show more Highlights - Most important sentences from the article 2019-05-12 1905.04614 | cs.SC Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear… show more Highlights - Most important sentences from the article 2019-01-27 1901.09423 | cs.CC This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix ran… show more Highlights - Most important sentences from the article 2018-01-14 1801.04553 | cs.SC In this article, we design fast algorithms for the computation of approximant bases in shifted Popov… show more Highlights - Most important sentences from the article 2018-08-07 1808.02575 | math.AC We compute minimal solutions of the rational interpolation problem in terms of different notions of … show more Highlights - Most important sentences from the article 2018-10-30 1810.12588 | cs.SC Symmetric tensor decomposition is an important problem with applications in several areas for exampl… show more Highlights - Most important sentences from the article 2018-06-15 1806.05834 | math.NT We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperellipt… show more Highlights - Most important sentences from the article 2018-03-21 1803.07974 | math.AG We consider the problem of finding the isolated common roots of a set of polynomial functions defini… show more Highlights - Most important sentences from the article 2017-12-12 1712.04177 | cs.SC Consider a zero-dimensional ideal$I$in$\mathbb{K}[X_1,\dots,X_n]\$. Inspired by Faug\`ere and Mou'… show more

Highlights - Most important sentences from the article

2016-10-27
1610.08671 | math.RA

We propose a randomized polynomial time algorithm for computing nontrivial zeros of quadratic forms … show more

Highlights - Most important sentences from the article

2016-01-06
1601.01067 | cs.SC

In this paper, a polynomial-time algorithm is given to compute the generalized Hermite normal form f… show more

Highlights - Most important sentences from the article

2012-03-30
1203.6705 | cs.DS

We consider the problem of computing the rank of an m x n matrix A over a field. We present a random… show more

Highlights - Most important sentences from the article

2013-12-27
1312.7279 | cs.NA

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical … show more

Highlights - Most important sentences from the article

2016-08-09
1608.02674 | cs.DC

Censor-Hillel et al. [PODC'15] recently showed how to efficiently implement centralized algebraic al… show more

Highlights - Most important sentences from the article

2018-02-07
1802.02270 | cs.SC

We present new algorithms to detect and correct errors in the product of two matrices, or the invers… show more

Highlights - Most important sentences from the article