ML p(r)ior | Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

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

2016-02-02
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-03-08

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Ga… show more
PDF

Highlights - Most important sentences from the article

2019-05-12

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear… show more
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-12-02

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

Highlights - Most important sentences from the article

2018-06-15

We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperellipt… show more
PDF

Highlights - Most important sentences from the article

2015-11-11

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

Highlights - Most important sentences from the article

2018-06-29
1806.11293 | cs.SC

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

Highlights - Most important sentences from the article

2017-12-12

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faug\`ere and Mou'… show more
PDF

Highlights - Most important sentences from the article

2014-04-17

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

Highlights - Most important sentences from the article

2012-08-17

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

Highlights - Most important sentences from the article

2012-10-04

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

Highlights - Most important sentences from the article

2013-11-22

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2012-03-30

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2012-01-27
1201.5810 | cs.SC

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

Highlights - Most important sentences from the article