### Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

**2016-02-02**

1602.00810 | cs.SC

Certificates to a linear algebra computation are additional data structures
for each output, which can be used by a-possibly randomized- verification
algorithm that proves the correctness of each output. In this paper, we give an
algorithm that compute a certificate for the minimal polynomial of sparse or
structured n x n matrices over an abstract field, of sufficiently large
cardinality, whose Monte Carlo verification complexity requires a single
matrix-vector multiplication and a linear number of extra field operations. We
also propose a novel preconditioner that ensures irreducibility of the
characteristic polynomial of the preconditioned matrix. This preconditioner
takes linear time to be applied and uses only two random entries. We then
combine these two techniques to give algorithms that compute certificates for
the determinant, and thus for the characteristic polynomial, whose Monte Carlo
verification complexity is therefore also linear.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**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

**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

**2018-10-25**

1810.11068 | math.NT

We present a probabilistic Las Vegas algorithm for computing the local zeta
function of a genus-$g$ … show more

**2017-12-02**

1712.00669 | cs.CG

We present a novel randomized algorithm to factor polynomials over a finite
field $\F_q$ of odd char… show more

**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

**2015-11-11**

1511.03730 | cs.CC

In this paper we present a deterministic polynomial time algorithm for
testing if a symbolic matrix … show more

**2018-06-29**

1806.11293 | cs.SC

In an emerging computing paradigm, computational capabilities, from
processing power to storage capa… show more

**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

**2014-04-17**

1404.5525 | cs.NA

In this paper, we study iterative methods on the coefficients of the rational
univariate representat… show more

**2012-08-17**

1208.3639 | cs.CC

We show that linear differential operators with polynomial coefficients over
a field of characterist… show more

**2012-10-04**

1210.1451 | cs.CC

The multivariate resultant is a fundamental tool of computational algebraic
geometry. It can in part… show more

**2013-11-22**

1311.5694 | cs.SC

We present a deterministic polynomial-time algorithm which computes the
multilinear factors of multi… show more

**2016-04-29**

1604.08944 | cs.SC

Given a zero-dimensional polynomial system consisting of n integer
polynomials in n variables, we pr… show more

**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

**2016-02-29**

1602.09037 | cs.DS

We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders,
previously revisited b… show more

**2012-01-27**

1201.5810 | cs.SC

Sparse (or toric) elimination exploits the structure of polynomials by
measuring their complexity in… show more