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...
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...
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...
Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix (2006)
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 (2006)
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...
FPGA Implementation of a Recently Published Signature Scheme (2006)
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 (2006)
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...
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 (2006)
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 (2006)
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...
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, Laboratoire De L'informatique Du Parallélisme
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...
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)
Laboratoire De L'informatique Du Parallélisme, 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...
On The Complexity Of Computing (2004)
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...
On The Complexity Of Computing (2004)
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...
Essentially Optimal Computation of the Inverse of Generic Polynomial Matrices (2004)
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...
Lattice Based Memory Allocation (2004)
Alain Darte, Rob Schreiber, Gilles Villard
this paper, i.e., memory mappings that access multi-dimensional arrays with a#ne functions followed by a modulo operation in each dimension. Thies, Vivien, Sheldon, and Amarasinghe, aware of the...
Lattice-Based Memory Allocation. (2004)
Laboratoire De L'informatique Du Parallélisme, 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...
Laboratoire de l'Informatique du Paralllisme (2004)
Arnaud Tisserand, Jean-luc Beuchat, Nicolas Sendrier, Arnaud Tisser, Gilles Villard
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...
FPGA Implementation of a Recently Published Signature Scheme. (2004)
Laboratoire De L'informatique Du Parallélisme, 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....
Journal ofCom;B-vSD-5W and AppliedMathemWDq- 162 (2004) 133 -- 146 (2004)
Erich Kaltofen, Gilles Villard
Com9v9v9v of the sign of thedeterm9vSof amWDz[ and thedetermBvSitself is a challenge for both numhvB5q and exactmactv;W We survey the comWzqDvS of existingmistin to solve theseproblem when the input...
Lattice-Based Memory Allocation (2004)
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...
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 Inc. All...
On the Complexity of Polynomial Matrix Computations (2004)
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...
Laboratoire de l'Informatique du (2003)
Cole Normale Suprieure De Lyon, Unit Mixte, Recherche Cnrs-inria-ens Lyon, Erich Kaltofen, Gilles Villard
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 computing determinants. (2003)
Laboratoire De L'informatique Du Parallélisme, 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...
Exact Computations on Polynomial and Integer Matrices (2003)
One may consider that the algebraic complexity of basic linear algebra over an abstract field K is well known. Indeed, if # is the exponent of matrix multiplication over K, then for instance...
On the Complexity of Polynomial Matrix Computations (2003)
Unite Mixte, Recherche Cnrs-inria-ens Lyon, 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...
On the Complexity of Polynomial Matrix Computations. (2003)
Laboratoire De L'informatique Du Parallélisme, 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...
Straight-Line Computation of the Polynomial Matrix Inverse (2002)
Unite Mixte, Recherche Cnrs-inria-ens Lyon, 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 requires O(n d) field operations for a generic...
Straight-line computation of the polynomial matrix inverse. (2002)
Laboratoire De L'informatique Du Parallélisme, 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...
A Rank Theorem for Vandermonde Matrices (2002)
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".
LinBox: A Generic Library for Exact Linear Algebra. (2002)
Laboratoire De L'informatique Du Parallélisme, 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...
Computing the Sign Or the Value of the Determinant of an Integer Matrix, a Complexity Survey (2002)
Unit Mixte, Recherche Cnrs-inria-ens Lyon, Gilles Villard Janvier, Erich Kaltofen, Gilles Villard
Certified computation of the sign of the determinant of a matrix or computation of the determinant itself are a challenge for both numerical and exact methods. We survey the complexities of existing...
Normal Forms for General Polynomial Matrices. (2002)
Laboratoire De L'informatique Du Parallélisme, 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)
Laboratoire De L'informatique Du Parallélisme, 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...
Matrix Rank Certification (2001)
B. David Saunders, Arne Storjohann, Gilles Villard
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 matrixThetacolumn-vector...
A Rank Theorem for Vandermonde Matrices (2001)
Unite Mixte, Recherche Cnrs-inria-ens Lyon, Pascal Koiran, Natacha Portier, Gilles Villard
Introduction Let V = V d (x 1 ; : : : ; x n ) denote the n (d + 1) Vandermonde matrix built from the complex numbers x 1 ; : : : ; x n (that is, V ij = x j 1 i ). The main purpose of this note is to...
Matrix Rank Certification (2001)
B. David Saunders, Arne Storjohann, Gilles Villard
Randomized algorithms are given for computing the rank of a matrix over a field of...
Efficient Matrix Preconditioners for Black Box Linear Algebra (2001)
Li Chen, Wayne Eberly, Erich Kaltofen, B. David Saunders, William J. Turner, Gilles Villard
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...
Matrix Rank Certification. (2001)
Laboratoire De L'informatique Du Parallélisme, 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)
Laboratoire De L'informatique Du Parallélisme, 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 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 3:5 (logn) 4:5 ) bit operations (assuming for now...
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 n n the algorithm requires O n 3 5 logn 4 5 bit operations (assuming for now that...
Computing the Frobenius Normal Form of a Sparse Matrix (2000)
. 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 log 2 (n) log log(n)...
Some Algorithms for Matrix Polynomials (1999)
G. Villard, Rt Part Mars, Gilles Villard
For a polynomial matrix P (x) of degree d in Mn;n (K[x]) where K is a commutative field, a reduction to the Hermite normal form can be computed in O (M(nd)) arithmetic operations if M(n) is the time...
Parallel Computer Algebra (1999)
Jean-louis Roch, Gilles Villard
measures used to analyze algorithms are depth and work; arithmetic and communication costs are distinguished. The one corresponds to operations performed (macro-instructions nodes) while the other to...
A study of Coppersmith's block Wiedemann algorithm using matrix polynomials (1999)
We analyse a randomized block algorithm proposed by Coppersmith for solving large sparse systems of linear equations, Aw = 0, over a finite field K =GF(q). It is a modification of an algorithm of...
Some Algorithms for Matrix Polynomials (1999)
G. Villard, Rt Part Mars, Gilles Villard
Continuing a series of articles on normal forms of matrices, we investigate fast parallel algorithms to compute the corresponding transformations. Given a matrix B in Mn;n (K), where K is an...
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...
Some Algorithms for Matrix Polynomials (1996)
G. Villard, Rt Part Mars, Gilles Villard
. For a polynomial matrix P (x) of degree d in Mn;n (K[x]) where K is a commutative field, a reduction to the Hermite normal form can be computed in O ~ (M(nd)) arithmetic operations if M(n) is the...