Parallel Processing Letters cfl World Scientific Publishing Company (2009)
Jean-louis Roch, Gilles Villard
Accepted by D. Bini ABSTRACT We establish that the problem of computing the Jordan normal form of a matrix over a field F is in N C3F for F being a field of characteristic zero or a finite field.
Analyse numérique et réduction de réseaux (2009)
Morel, Ivan, Stehlé, Damien, Villard, Gilles
L'algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu'il est donc important de rendre...
Analyse numérique et réduction de réseaux (2009)
Morel, Ivan, Stehlé, Damien, Villard, Gilles
L'algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu'il est donc important de rendre...
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard
We propose a new algorithm to find a rational solution to a sparse system of linear equations over the integers. This algorithm is based on a p-adic lifting technique combined with the use of block...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2008)
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard
Efficient block projections of non-singular matrices have recently been used by the authors in [10] to obtain an efficient algorithm to find rational solutions for sparse systems of linear equations....
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard
We propose a new algorithm to find a rational solution to a sparse system of linear equations over the integers. This algorithm is based on a p-adic lifting technique combined with the use of block...
URL:www.apmaths.uwo.ca/˜djeffrey (2008)
Matt Davison, Laureano Gonzalez-vega, Gilles Villard, Michael Wester, Vice-chair Wolfgang, ...
A method for removing all intermediate terms from a given equation
URL:www.apmaths.uwo.ca/˜djeffrey Associate Editors (2008)
Gene Cooperman, Xiaoqin Ma, Michael P. Barnett, Laureano Gonzalez-vega, Austin Lobo, Gilles Villard, ...
Formally Reviewed Articles Formally reviewed articles in this issue of the SIGSAM BULLETIN are indicated as such by an imprint on their first page; unreviewed articles do not have such an imprint....
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2008)
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard
Efficient block projections of non-singular matrices have recently been used by the authors in [10] to obtain an efficient algorithm to find rational solutions for sparse systems of linear equations....
Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation (2008)
Kaltofen has proposed a new approach in 1992 for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
Analyse numérique et réduction de réseaux (2008)
Morel, Ivan, Stehlé, Damien, Villard, Gilles
L'algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu'il est donc important de rendre...
Analyse numérique et réduction de réseaux (2008)
Morel, Ivan, Stehlé, Damien, Villard, Gilles
L'algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu'il est donc important de rendre...
Calcul formel et parallélisme : résolution de systèmes linéaires (2008)
On considère la résolution exacte des systèmes linéaires en parallèle et on traite deux aspects de base du problème : le calcul du noyau d'une matrice dont les coefficients sont dans un corps...
Differentiation of Kaltofen's division-free determinant algorithm (2008)
Kaltofen has proposed a new approach in [Kaltofen 1992] for computing matrix determinants. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
TIMELY COMMUNICATIONS Factoring a binary polynomial of degree over one million (2008)
Joachim Von Gathen, Michael A. Nielson, Olaf Bonorden, Joachim Von, Zur Gathen, Jürgen Gerhard, ...
A Quarterly Publication of the Homotopies and polynomial system solving I: Basic Principles......................................................ILIAS S. KOTSIREAS 19
Alain Darte, Robert Schreiber, Gilles Villard
We investigate the problem of memory reuse in order to reduce the memory needed to store an array variable. We develop techniques that can lead to smaller memory requirements in the synthesis of...
MATRIX RANK CERTIFICATION ∗ ELA (2008)
B. David Saunders, Arne Storjohann, Gilles Villard
Abstract. Randomized algorithmsare given for computing the rank of a matrix over a field of characteristic zero with conjugation operator. The matrix is treated as a black box. Only the capability to...
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, Gilles Villard
We propose a new algorithm to find a rational solution to a sparse system of linear equations over the integers. This algorithm is based on a p-adic lifting technique combined with the use of block...
Erich Kaltofen, Gilles Villard
Computing the sign or the value of the determinant of an integer matrix, a complexity survey 1
computational complexity ON THE COMPLEXITY OF COMPUTING DETERMINANTS (2008)
Erich Kaltofen, Gilles Villard
on the occasion of his 60th birthday Abstract. We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant,...
On the complexity of computing determinants (extended abstract (2008)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
Differentiation of Kaltofen's division-free determinant algorithm (2008)
Kaltofen has proposed a new approach in [Kaltofen 1992] for computing matrix determinants. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
Differentiation of Kaltofen's division-free determinant algorithm (2008)
Kaltofen has proposed a new approach in [Kaltofen 1992] for computing matrix determinants. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation (2008)
Kaltofen has proposed a new approach in 1992 for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation (2008)
Kaltofen has proposed a new approach in 1992 for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the...
Jeannerod, Claude-Pierre, Knochel, Hervé, Monat, Christophe, Revy, Guillaume, Villard, Gilles
This paper deals with the design and implementation of low latency software for binary floating-point division with correct rounding to nearest. The approach we present here targets a VLIW integer...
Jeannerod, Claude-Pierre, Knochel, Hervé, Monat, Christophe, Revy, Guillaume, Villard, Gilles
This paper deals with the design and implementation of low latency software for binary floating-point division with correct rounding to nearest. The approach we present here targets a VLIW integer...
Jeannerod, Claude-Pierre, Knochel, Hervé, Monat, Christophe, Revy, Guillaume, Villard, Gilles
This paper deals with the design and implementation of low latency software for binary floating-point division with correct rounding to nearest. The approach we present here targets a VLIW integer...
Jeannerod, Claude-Pierre, Knochel, Hervé, Monat, Christophe, Revy, Guillaume, Villard, Gilles
This paper deals with the design and implementation of low latency software for binary floating-point division with correct rounding to nearest. The approach we present here targets a VLIW integer...
On efficient sparse integer matrix Smith normal form computations (2007)
Jean-Guillaume Dumas, B. David Saunders, Gilles Villard
We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo...
Pour une matrice polynomiale P (x) de degr'e d dans Mn;n(K[x]), o`u K est un corps commutatif, une r'eduction `a la forme normale d'Hermite peut etre calcul'ee en O (M(nd))...
Parallel Computer Algebra 1 (2007)
Jean-louis Roch, Gilles Villard
Building and implementing parallel algorithms in the area of computer algebra has become an important thread of research for more than a decade with the increasing availability of various parallel...
Straight-line computation of the polynomial (2007)
École Normale, École Normale, Supérieure Lyon, Supérieure Lyon, Claude-pierre Jeannerod, Claude-pierre Jeannerod, ...
matrix inverse
On the complexity of computing determinants (Extended Abstract) (2007)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
Bernhard Beckermann, George Labahn, Gilles Villard
We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specic input shifts, we obtain methods for computing the matrix greatest common...
Unit Mixte, Bernd Beckermann, Bernd Beckermann, ...
We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specic input shifts, we obtain methods for computing the matrix greatest common...
Matrix Rank Certication (2007)
Unit Mixte, B. David Saunders, B. David Saunders, ...
Randomized algorithms are given for computing the rank of a matrix over a eld of characteristic zero. The matrix is treated as a black box. Only the capability to compute matrix column-vector and...
Abstract. We want to achieve ecient exact computations, such as the rank, of sparse matrices over nite elds. We therefore compare the practical behaviors, on a wide range of sparse matrices of the...
On the Complexity of Polynomial Matrix Computations (2007)
Unite Mixte, Pascal Giorgi, Pascal Giorgi, Claude-pierre Jeannerod, Claude-pierre Jeannerod, ...
We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n...
A Rank Theorem for Vandermonde Matrices (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran, Pascal Koiran, ...
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the \limit theory of generic polynomials".
On the complexity of computing determinants (extended abstract (2007)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
Essentially Optimal Computation of the Inverse of Generic Polynomial Matrices (2007)
Claude-pierre Jeannerod, Gilles Villard
We present an inversion algorithm for nonsingular n n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires O(n d) field...
Pascal Koiran Natacha, Pascal Koiran, Natacha Portier, Gilles Villard
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the "limit theory of generic polynomials". 2003 Elsevier...
Certification of the QR factor R, and of lattice basis reducedness (2007)
Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Certification of the QR factor R, and of lattice basis reducedness (2007)
Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections (2007)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is...
Certification of the QR factor R, and of lattice basis reducedness (2007)
Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Solving Sparse Integer Linear Systems (2006)
Eberly, Wayne, Giesbrecht, Mark, Giorgi, Pascal, Storjohann, Arne, Villard, Gilles
We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with...
Computing the Kalman form (2005)
Pernet, Clément, Rondepierre, Aude, Villard, Gilles
We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the...
Computing the Kalman form (2005)
Pernet, Clément, Rondepierre, Aude, Villard, Gilles
We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the...
Computing the Kalman form (2005)
Pernet, Clément, Rondepierre, Aude, Villard, Gilles
We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the...
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
14 p., 17 références bibliographiques
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they...
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they...
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2005)
Storjohann, Arne, Villard, Gilles
We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a...
Computing the rank and a small nullspace basis of a polynomial matrix. (2005)
Storjohann, Arne, Villard, Gilles
(eng) We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2005)
Storjohann, Arne, Villard, Gilles
We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2005)
Storjohann, Arne, Villard, Gilles
We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a...
Computing the Kalman form (2005)
Pernet, Clément, Rondepierre, Aude, Villard, Gilles
We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the...
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2005)
Storjohann, Arne, Villard, Gilles
We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2005)
Storjohann, Arne, Villard, Gilles
We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a...
Computing the Kalman form (2005)
Pernet, Clément, Rondepierre, Aude, Villard, Gilles
We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the...
Asymptotically fast polynomial matrix algorithms for multivariable systems (2005)
Jeannerod, Claude-Pierre, Villard, Gilles
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they...
École Normale, Supérieure Lyon, Gilles Villard, École Normale, Supérieure Lyon, Gilles Villard
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form [8, 9, 16, 17]. We show...
Lattice-Based Memory Allocation. (2004)
Darte, Alain, Schreiber, Rob, Villard, Gilles
(eng) We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both...
FPGA Implementation of a Recently Published Signature Scheme (2004)
Beuchat, Jean-Luc, Sendrier, Nicolas, Tisserand, Arnaud, Villard, Gilles
An algorithm producing cryptographic digital signatures less than 100 bits long with a security level matching nowadays standards has been recently proposed by Courtois, Finiasz, and Sendrier. This...
FPGA Implementation of a Recently Published Signature Scheme. (2004)
Beuchat, Jean-Luc, Sendrier, Nicolas, Tisserand, Arnaud, Villard, Gilles
(eng) An algorithm producing cryptographic digital signatures less than 100 bits long with a security level matching nowadays standards has been recently proposed by Courtois, Finiasz, and Sendrier....
FPGA Implementation of a Recently Published Signature Scheme (2004)
Beuchat, Jean-Luc, Sendrier, Nicolas, Tisserand, Arnaud, Villard, Gilles
An algorithm producing cryptographic digital signatures less than 100 bits long with a security level matching nowadays standards has been recently proposed by Courtois, Finiasz, and Sendrier. This...
FPGA Implementation of a Recently Published Signature Scheme (2004)
Beuchat, Jean-Luc, Sendrier, Nicolas, Tisserand, Arnaud, Villard, Gilles
An algorithm producing cryptographic digital signatures less than 100 bits long with a security level matching nowadays standards has been recently proposed by Courtois, Finiasz, and Sendrier. This...
Lattice-Based Memory Allocation (2004)
École Normale, Supérieure Lyon, Alain Darte, Rob Schreiber, Gilles Villard, École Normale, ...
We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both important and...
FPGA Implementation of a Recently Published Signature Scheme (2004)
Arnaud Tisserand, Jean-luc Beuchat, Jean-luc Beuchat, Nicolas Sendrier, Nicolas Sendrier, ...
An algorithm producing cryptographic digital signatures less than 100 bits long with a security level matching nowadays standards has been recently proposed by Courtois, Finiasz, and Sendrier. This...
On the complexity of computing determinants. (2003)
Kaltofen, Erich, Villard, Gilles
(eng) By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann approach and...
On the Complexity of Polynomial Matrix Computations. (2003)
Giorgi, Pascal, Jeannerod, Claude-Pierre, Villard, Gilles
(eng) We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we...
On the Complexity of Polynomial Matrix Computations (2003)
École Normale, Supérieure Lyon, Pascal Giorgi, Claude-pierre Jeannerod, Gilles Villard, École Normale, ...
We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n...
A rank theorem for Vandermonde matrices (2003)
Pascal Koiran, Natacha Portier, Gilles Villard
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the "limit theory of generic polynomials". 1
Lattice-based memory allocation (2003)
Alain Darte, Alain Darte, Rob Schreiber, Rob Schreiber, Gilles Villard, ...
We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both important and...
Lattice-Based Memory Allocation (2003)
Alain Darte, Rob Schreiber, Gilles Villard
We investigate the problem of memory reuse, for reducing the necessary memory size, in the context of compilation of dedicated processors. Memory reuse is a well-known concept when allocating...
On The Complexity Of Computing Determinants (2003)
Unit Mixte, Erich Kaltofen, Erich Kaltofen, ...
By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann...
On the Complexity of Polynomial Matrix Computations (2003)
Pascal Giorgi, Claude-pierre Jeannerod, Gilles Villard
We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n...
Straight-line computation of the polynomial matrix inverse. (2002)
Jeannerod, Claude-Pierre, Villard, Gilles
(eng) We present an inversion algorithm for nonsingular n x n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and requires O~(n^3d) field operations for a...
LinBox: A Generic Library for Exact Linear Algebra. (2002)
Dumas, J.G., Gautier, T., Giesbrecht, M., Giorgi, Pascal, Hovinen, B., ...
(eng) LinBox is a high-performance generic software library for black box linear algebra over symbolic (exact) entry domains. The generic software methodology enables the user to instantiate the...
Normal Forms for General Polynomial Matrices. (2002)
Beckermann, Bernd, Labahn, George, Villard, Gilles
(eng) We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specific input shifts, we obtain methods for computing the matrix greatest...
Computing the sign or the value of the determinant. (2002)
Kaltofen, Erich, Villard, Gilles
(eng) Computation of the sign of the determinant of a matrix and determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these...
Li Chen, Wayne Eberly, Erich Kaltofen, B. David, Saunders William, J. Turner, ...
The main idea of the “black box ” approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the...
Gilles Villard, Summary Emmanuel Thomé
Available online at the URL
Gilles Villard, Summary Emmanuel Thomé
Available online at the URL
Normal forms for general polynomial matrices (2002)
Bernhard Beckermann, George Labahn, Gilles Villard
We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specific input shifts, we obtain methods for computing the matrix greatest common...
Computing the rank of large sparse matrices over finite fields (2002)
Jean-guillaume Dumas, Gilles Villard
Abstract. We want to achieve efficient exact computations, such as the rank, of sparse matrices over finite fields. We therefore compare the practical behaviors, on a wide range of sparse matrices of...
Matrix Rank Certification. (2001)
Saunders, David, Storjohann, Arne, Villard, Gilles
(eng) Randomized algorithms are given for computing the rank of a matrix over a field of characteristic zero. The matrix is treated as a black box. Only the capability to compute matrix x...
Efficient Matrix Preconditioners for Black Box Linear Algebra. (2001)
Chen, L., Eberly, W., Kaltofen, Erich, Saunders, B.D., Turner, W.J., ...
(eng) The main idea of the ``black box'' approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain...
On the complexity of computing determinants (2001)
Erich Kaltofen, Gilles Villard
Abstract. We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius...
Normal Forms for General Polynomial Matrices (2001)
Bernhard Beckermann, George Labahn, Gilles Villard
We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specific input shifts, we obtain methods for computing the matrix greatest common...
On The Complexity Of Computing (2001)
Erich Kaltofen, Gilles Villard
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal...
Algorithms for similarity transforms (2000)
Arne Storjohann, Gilles Villard
Let F be a eld. Corresponding to any matrix A 2 F
On computing the determinant and Smith form of an integer matrix (2000)
Wayne Eberly, Mark Giesbrecht, Gilles Villard
Abstract A probabilistic algorithm is presented to find the de-terminant of a nonsingular, integer matrix. For a matrix A 2 Zn\Theta n the algorithm requires O(n3:5(logn)4:5) bit oper-ations...
On computing the determinant and Smith form of an integer matrix (2000)
Wayne Eberly, Mark Giesbrecht, Gilles Villard
A probabilistic algorithm is presented to find the determinant of a nonsingular, integer matrix. For a matrix A 2 Z nn the algorithm requires O(n
Computing the Frobenius normal form of a sparse matrix (2000)
Abstract. We probabilistically determine the Frobenius form and thus the characteristic polynomial of a matrix A 2 F nn by O(n log(n)) multiplications of A by vectors and O n 2
Integer Smith Form via the Valence: Experience with Large Sparse Matrices from Homology (2000)
Jean-Guillaume Dumas, B. David Saunders, Gilles Villard
We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo...
Processor Efficient Parallel Solution of Linear Systems of Equations (1998)
. We present a deterministic parallel algorithm that solves a n-dimensional system Ax = b of linear equations over a field of characteristic zero. This algorithm uses O(log 2 n) parallel time and...
A study of Coppersmith’s block Wiedemann algorithm using matrix polynomials (1997)
Nous analysons un algorithme probabiliste par blocs, propos'e par Coppersmith, pour la r'esolution de grands syst`emes lin'eaires creux Aw = 0 donn'es sur un corps fini K =GF(q)....
Calcul formel et parallélisme : résolution de systèmes linéaires (1988)
On considère la résolution exacte des systèmes linéaires en parallèle et on traite deux aspects de base du problème : le calcul du noyau d'une matrice dont les coefficients sont dans un corps...
Calcul formel et parallélisme : résolution de systèmes linéaires (1988)
On considère la résolution exacte des systèmes linéaires en parallèle et on traite deux aspects de base du problème : le calcul du noyau d'une matrice dont les coefficients sont dans un corps...
Calcul formel et parallélisme : résolution de systèmes linéaires (1988)
On considère la résolution exacte des systèmes linéaires en parallèle et on traite deux aspects de base du problème : le calcul du noyau d'une matrice dont les coefficients sont dans un corps...