InforLorV4, Hal, Curation, bibRecord, 002F16

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

Identifieur interne : 002F16 ( Hal/Curation ); précédent : 002F15; suivant : 002F17

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

Auteurs : Jean-Guillaume Dumas [France] ; Erich Kaltofen [États-Unis] ; Emmanuel Thomé [France] ; Gilles Villard [France]

Source :

RBID : Hal:hal-01266041

Abstract

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 × 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.

Url:

https://hal.archives-ouvertes.fr/hal-01266041

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002F16

Links to Exploration step

Hal:hal-01266041

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix</title>
<author><name sortKey="Dumas, Jean Guillaume" sort="Dumas, Jean Guillaume" uniqKey="Dumas J" first="Jean-Guillaume" last="Dumas">Jean-Guillaume Dumas</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388448" status="VALID"><orgName>Calculs Algébriques et Systèmes Dynamiques</orgName>
<orgName type="acronym">CASYS</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24474" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300339" type="indirect"></relation>
<relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID"><orgName>Laboratoire Jean Kuntzmann</orgName>
<orgName type="acronym">LJK</orgName>
<desc><address><addrLine>Tour IRMA 51 rue des Mathématiques - 53 38041 GRENOBLE CEDEX 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://ljk.imag.fr</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300339" type="direct"></relation>
<relation name="UMR5224" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID"><orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Kaltofen, Erich" sort="Kaltofen, Erich" uniqKey="Kaltofen E" first="Erich" last="Kaltofen">Erich Kaltofen</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-169897" status="VALID"><orgName>Department of Mathematics [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Box 8205, Raleigh, NC 27695-8205, USA</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.math.ncsu.edu/</ref>
</desc>
<listRelation><relation active="#struct-306579" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-306579" type="direct"><org type="institution" xml:id="struct-306579" status="VALID"><orgName>North Carolina State University [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Raleigh, NC 27695</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.ncsu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-178327" status="VALID"><idno type="RNSR">201221021B</idno>
<orgName>Arithmetic and Computing</orgName>
<orgName type="acronym">ARIC</orgName>
<desc><address><addrLine>46 Allée d'Italie 69364 Lyon France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/aric</ref>
</desc>
<listRelation><relation active="#struct-2497" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-35418" type="direct"></relation>
<relation active="#struct-6818" type="indirect"></relation>
<relation active="#struct-194495" type="indirect"></relation>
<relation active="#struct-301088" type="indirect"></relation>
<relation name="UMR5668" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-2497" type="direct"><org type="laboratory" xml:id="struct-2497" status="VALID"><idno type="RNSR">199218244V</idno>
<orgName>Inria Grenoble - Rhône-Alpes</orgName>
<desc><address><addrLine>Inovallée655 avenue de l'Europe38330 Montbonnot</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/grenoble</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-35418" type="direct"><org type="laboratory" xml:id="struct-35418" status="VALID"><orgName>Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="acronym">LIP</orgName>
<desc><address><addrLine>46 Allée d'Italie 69364 LYON CEDEX 07</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-lyon.fr/LIP/</ref>
</desc>
<listRelation><relation active="#struct-6818" type="direct"></relation>
<relation active="#struct-194495" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-301088" type="direct"></relation>
<relation name="UMR5668" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-6818" type="indirect"><org type="institution" xml:id="struct-6818" status="VALID"><idno type="IdRef">149154992</idno>
<orgName>École normale supérieure - Lyon</orgName>
<orgName type="acronym">ENS Lyon</orgName>
<desc><address><addrLine>15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-lyon.eu/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-194495" type="indirect"><org type="institution" xml:id="struct-194495" status="VALID"><orgName>Université Claude Bernard Lyon 1</orgName>
<orgName type="acronym">UCBL</orgName>
<desc><address><addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lyon1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301088" type="indirect"><org type="institution" xml:id="struct-301088" status="VALID"><orgName>PRES Université de Lyon</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5668" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Lyon</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Claude Bernard Lyon 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lyon</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01266041</idno>
<idno type="halId">hal-01266041</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01266041</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01266041</idno>
<date when="2016-02-01">2016-02-01</date>
<idno type="wicri:Area/Hal/Corpus">002F16</idno>
<idno type="wicri:Area/Hal/Curation">002F16</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix</title>
<author><name sortKey="Dumas, Jean Guillaume" sort="Dumas, Jean Guillaume" uniqKey="Dumas J" first="Jean-Guillaume" last="Dumas">Jean-Guillaume Dumas</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388448" status="VALID"><orgName>Calculs Algébriques et Systèmes Dynamiques</orgName>
<orgName type="acronym">CASYS</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-24474" type="direct"></relation>
<relation active="#struct-3886" type="indirect"></relation>
<relation active="#struct-51016" type="indirect"></relation>
<relation active="#struct-300339" type="indirect"></relation>
<relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID"><orgName>Laboratoire Jean Kuntzmann</orgName>
<orgName type="acronym">LJK</orgName>
<desc><address><addrLine>Tour IRMA 51 rue des Mathématiques - 53 38041 GRENOBLE CEDEX 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://ljk.imag.fr</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300339" type="direct"></relation>
<relation name="UMR5224" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID"><orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Kaltofen, Erich" sort="Kaltofen, Erich" uniqKey="Kaltofen E" first="Erich" last="Kaltofen">Erich Kaltofen</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-169897" status="VALID"><orgName>Department of Mathematics [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Box 8205, Raleigh, NC 27695-8205, USA</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.math.ncsu.edu/</ref>
</desc>
<listRelation><relation active="#struct-306579" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-306579" type="direct"><org type="institution" xml:id="struct-306579" status="VALID"><orgName>North Carolina State University [Raleigh]</orgName>
<orgName type="acronym">NCSU</orgName>
<desc><address><addrLine>Raleigh, NC 27695</addrLine>
<country key="US"></country>
</address>
<ref type="url">https://www.ncsu.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-178327" status="VALID"><idno type="RNSR">201221021B</idno>
<orgName>Arithmetic and Computing</orgName>
<orgName type="acronym">ARIC</orgName>
<desc><address><addrLine>46 Allée d'Italie 69364 Lyon France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/aric</ref>
</desc>
<listRelation><relation active="#struct-2497" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-35418" type="direct"></relation>
<relation active="#struct-6818" type="indirect"></relation>
<relation active="#struct-194495" type="indirect"></relation>
<relation active="#struct-301088" type="indirect"></relation>
<relation name="UMR5668" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-2497" type="direct"><org type="laboratory" xml:id="struct-2497" status="VALID"><idno type="RNSR">199218244V</idno>
<orgName>Inria Grenoble - Rhône-Alpes</orgName>
<desc><address><addrLine>Inovallée655 avenue de l'Europe38330 Montbonnot</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/grenoble</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-35418" type="direct"><org type="laboratory" xml:id="struct-35418" status="VALID"><orgName>Laboratoire de l'Informatique du Parallélisme</orgName>
<orgName type="acronym">LIP</orgName>
<desc><address><addrLine>46 Allée d'Italie 69364 LYON CEDEX 07</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-lyon.fr/LIP/</ref>
</desc>
<listRelation><relation active="#struct-6818" type="direct"></relation>
<relation active="#struct-194495" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-301088" type="direct"></relation>
<relation name="UMR5668" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-6818" type="indirect"><org type="institution" xml:id="struct-6818" status="VALID"><idno type="IdRef">149154992</idno>
<orgName>École normale supérieure - Lyon</orgName>
<orgName type="acronym">ENS Lyon</orgName>
<desc><address><addrLine>15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-lyon.eu/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-194495" type="indirect"><org type="institution" xml:id="struct-194495" status="VALID"><orgName>Université Claude Bernard Lyon 1</orgName>
<orgName type="acronym">UCBL</orgName>
<desc><address><addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lyon1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301088" type="indirect"><org type="institution" xml:id="struct-301088" status="VALID"><orgName>PRES Université de Lyon</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5668" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Lyon</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Claude Bernard Lyon 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lyon</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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 × 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.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix</title>
<author role="aut"><persName><forename type="first">Jean-Guillaume</forename>
<surname>Dumas</surname>
</persName>
<email>Jean-Guillaume.Dumas@imag.fr</email>
<ptr type="url" target="http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/"></ptr>
<idno type="idhal">jean-guillaume-dumas</idno>
<idno type="halauthor">713905</idno>
<idno type="arXiv">http://arxiv.org/a/dumas_j_1</idno>
<affiliation ref="#struct-388448"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Erich</forename>
<surname>Kaltofen</surname>
</persName>
<email></email>
<idno type="halauthor">270463</idno>
<affiliation ref="#struct-169897"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Emmanuel</forename>
<surname>Thomé</surname>
</persName>
<email></email>
<idno type="halauthor">69691</idno>
<affiliation ref="#struct-119560"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Gilles</forename>
<surname>Villard</surname>
</persName>
<email></email>
<idno type="halauthor">62681</idno>
<affiliation ref="#struct-178327"></affiliation>
<affiliation ref="#struct-35418"></affiliation>
</author>
<editor role="depositor"><persName><forename>Jean-Guillaume</forename>
<surname>Dumas</surname>
</persName>
<email>Jean-Guillaume.Dumas@imag.fr</email>
</editor>
<funder ref="#projanr-15543"></funder>
<funder ref="#projeurop-181668"></funder>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2016-02-01 23:12:53</date>
<date type="whenModified">2016-03-16 11:28:50</date>
<date type="whenReleased">2016-02-02 08:29:41</date>
<date type="whenProduced">2016-02-01</date>
<date type="whenEndEmbargoed">2016-02-01</date>
<ref type="file" target="https://hal.archives-ouvertes.fr/hal-01266041/document"><date notBefore="2016-02-01"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.archives-ouvertes.fr/hal-01266041/file/det_techreport.pdf"><date notBefore="2016-02-01"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="100212"><persName><forename>Jean-Guillaume</forename>
<surname>Dumas</surname>
</persName>
<email>Jean-Guillaume.Dumas@imag.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">hal-01266041</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01266041</idno>
<idno type="halBibtex">dumas:hal-01266041</idno>
<idno type="halRefHtml">2016</idno>
<idno type="halRef">2016</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="UNIV-PMF_GRENOBLE" p="UGA">Université Pierre-Mendès-France - Grenoble II</idno>
<idno type="stamp" n="INPG" p="UGA">Institut polytechnique de Grenoble</idno>
<idno type="stamp" n="INRIA-RHA">INRIA Grenoble - Rhône-Alpes</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno>
<idno type="stamp" n="LIP">Laboratoire de l'Informatique du Parallélisme</idno>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="ENS-LYON">École Normale Supérieure de Lyon</idno>
<idno type="stamp" n="UNIV-GRENOBLE1" p="UGA">Université Joseph Fourier - Grenoble I</idno>
<idno type="stamp" n="LJK" p="UGA">Laboratoire Jean Kuntzmann</idno>
<idno type="stamp" n="OPENAIRE">OpenAIRE</idno>
<idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA2">INRIA 2</idno>
<idno type="stamp" n="LORIA-ALGO-TEST5">LORIA-ALGO-TEST5  </idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="UGA">HAL Grenoble Alpes</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="LJK_MAD" p="LJK">Département Modèles et Algorithmes Déterministes</idno>
<idno type="stamp" n="LJK_MAD_CASYS" p="LJK_MAD">CASYS</idno>
</seriesStmt>
<notesStmt></notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix</title>
<author role="aut"><persName><forename type="first">Jean-Guillaume</forename>
<surname>Dumas</surname>
</persName>
<email>Jean-Guillaume.Dumas@imag.fr</email>
<ptr type="url" target="http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/"></ptr>
<idno type="idHal">jean-guillaume-dumas</idno>
<idno type="halAuthorId">713905</idno>
<idno type="arXiv">http://arxiv.org/a/dumas_j_1</idno>
<affiliation ref="#struct-388448"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Erich</forename>
<surname>Kaltofen</surname>
</persName>
<idno type="halAuthorId">270463</idno>
<affiliation ref="#struct-169897"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Emmanuel</forename>
<surname>Thomé</surname>
</persName>
<idno type="halAuthorId">69691</idno>
<affiliation ref="#struct-119560"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Gilles</forename>
<surname>Villard</surname>
</persName>
<idno type="halAuthorId">62681</idno>
<affiliation ref="#struct-178327"></affiliation>
<affiliation ref="#struct-35418"></affiliation>
</author>
</analytic>
<monogr><imprint></imprint>
</monogr>
<idno type="arxiv">1602.00810</idno>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><classCode scheme="halDomain" n="info.info-sc">Computer Science [cs]/Symbolic Computation [cs.SC]</classCode>
<classCode scheme="halTypology" n="UNDEFINED">Preprints, Working Papers, ...</classCode>
</textClass>
<abstract xml:lang="en">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 × 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.</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002F16 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 002F16 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:hal-01266041
   |texte=   Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

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

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri