Gilles Villard
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Gilles Villard has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Vincent Neiger
LIP6, Sorbonne Université, Paris, France
3 shared publications - Bruno Salvy
INRIA, Lyon, France
2 shared publications - Clément Pernet
Cnrs Univ. Grenoble Alpes Grenoble inp -uga 38000 ljk Grenoble France
2 shared publications - Éric Schost
University of Waterloo, Waterloo, ON, Canada
2 shared publications - Hippolyte Signargout
LIP UMR 5668, LJK UMR 5224, Univ. Lyon, ENS de Lyon, CNRS, Inria, UCBL, France
1 shared publication Jean-Louis Roch
Institut IMAG, Laboratoire LMC, 46, Av. F. Viallet, 38031 Grenoble Cedex, France
1 shared publication
Latest Publications
- Open Access
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 315-324
Faster Modular Composition Using Two Relation Matrices
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the algebraic algorithm with the best complexity bound for this problem was that of Brent and Kung (1978). Recently, we improved this algorithm by computing and using a polynomial matrix that encodes a certain basis of algebraic relations between the polynomials. This is further improved here by making use of two polynomial matrices of smaller dimension. Under genericity assumptions on the input, this results in an algorithm using \(\tilde{O}(n^{(\omega +3)/4})\) arithmetic operations in the base field, where ω is the exponent of matrix multiplication. With naive matrix multiplication, this is \(\tilde{O}(n^{3/2})\) , while with the best currently known exponent ω this is O(n1.343), improving upon the previously most efficient algorithms.- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 315-324
Open AccessFaster Modular Composition Using Two Relation Matrices
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the algebraic algorithm with the best complexity bound for this problem was that of Brent and Kung (1978). Recently, we improved this algorithm by computing and using a polynomial matrix that encodes a certain basis of algebraic relations between the polynomials. This is further improved here by making use of two polynomial matrices of smaller dimension. Under genericity assumptions on the input, this results in an algorithm using \(\tilde{O}(n^{(\omega +3)/4})\) arithmetic operations in the base field, where ω is the exponent of matrix multiplication. With naive matrix multiplication, this is \(\tilde{O}(n^{3/2})\) , while with the best currently known exponent ω this is O(n1.343), improving upon the previously most efficient algorithms. - Open Access
- 16 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 419-428
Computing Krylov iterates in the time of matrix multiplication
Krylov methods rely on iterated matrix-vector products Akuj for an n × n matrix A and vectors u1, …, um. The space spanned by all iterates Akuj admits a particular basis — the maximal Krylov basis — which consists of iterates of the first vector u1, Au1, A2u1, …, until reaching linear dependency, then iterating similarly the subsequent vectors until a basis is obtained. Finding minimal polynomials and Frobenius normal forms is closely related to computing maximal Krylov bases. The fastest way to produce these bases was, until this paper, Keller-Gehrig’s 1985 algorithm whose complexity bound Math 1 comes from repeated squarings of A and logarithmically many Gaussian eliminations. Here ω > 2 is a feasible exponent for matrix multiplication over the base field. We present an algorithm computing the maximal Krylov basis in Math 2 field operations when Math 3, and even Math 4 as soon as Math 5 for some fixed real c > 0. As a consequence, we show that the Frobenius normal form together with a transformation matrix can be computed deterministically in Math 6, and therefore matrix exponentiation Ak can be performed in the latter complexity if Math 7 for some fixed ε > 0. A key idea for these improvements is to rely on fast algorithms for m × m polynomial matrices of average degree n/m, involving high-order lifting and minimal kernel bases.
- 16 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 419-428
Open AccessComputing Krylov iterates in the time of matrix multiplication
Krylov methods rely on iterated matrix-vector products Akuj for an n × n matrix A and vectors u1, …, um. The space spanned by all iterates Akuj admits a particular basis — the maximal Krylov basis — which consists of iterates of the first vector u1, Au1, A2u1, …, until reaching linear dependency, then iterating similarly the subsequent vectors until a basis is obtained. Finding minimal polynomials and Frobenius normal forms is closely related to computing maximal Krylov bases. The fastest way to produce these bases was, until this paper, Keller-Gehrig’s 1985 algorithm whose complexity bound Math 1 comes from repeated squarings of A and logarithmically many Gaussian eliminations. Here ω > 2 is a feasible exponent for matrix multiplication over the base field. We present an algorithm computing the maximal Krylov basis in Math 2 field operations when Math 3, and even Math 4 as soon as Math 5 for some fixed real c > 0. As a consequence, we show that the Frobenius normal form together with a transformation matrix can be computed deterministically in Math 6, and therefore matrix exponentiation Ak can be performed in the latter complexity if Math 7 for some fixed ε > 0. A key idea for these improvements is to rely on fast algorithms for m × m polynomial matrices of average degree n/m, involving high-order lifting and minimal kernel bases.
- Open Access
- 10 April 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (2) , 1-79
Faster Modular Composition
A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n , the algorithm uses O ( n 1.43 ) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O ( n 1.63 ) field operations in general, and n 3/2+ o (1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n 5/3+ o (1) operations, while previous ones run in O ( n 2 ) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.
- 10 April 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (2) , 1-79
Open AccessFaster Modular Composition
A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n , the algorithm uses O ( n 1.43 ) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O ( n 1.63 ) field operations in general, and n 3/2+ o (1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n 5/3+ o (1) operations, while previous ones run in O ( n 2 ) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.
- Open Access
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 526-534
Elimination ideal and bivariate resultant over finite fields
A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to x or y) associated to two polynomials a and b in which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires (delog q)1 + o(1) bit operations, where d and e respectively bound the input degrees in x and in y. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal (or ), as long as the polynomial system a = b = 0 has not roots at infinity; the resultant of a and b when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra . By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 526-534
Open AccessElimination ideal and bivariate resultant over finite fields
A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to x or y) associated to two polynomials a and b in which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires (delog q)1 + o(1) bit operations, where d and e respectively bound the input degrees in x and in y. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal (or ), as long as the polynomial system a = b = 0 has not roots at infinity; the resultant of a and b when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra . By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.
- Open Access
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 480-489
Exact computations with quasiseparable matrices
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 480-489
Open AccessExact computations with quasiseparable matrices
- 1 June 1996
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 06 (02) , 203-212
FAST PARALLEL COMPUTATION OF THE JORDAN NORMAL FORM OF MATRICES
We establish that the problem of computing the Jordan normal form of a matrix over a field F is in [ ] for F being a field of characteristic zero or a finite field.
- 1 June 1996
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 06 (02) , 203-212
FAST PARALLEL COMPUTATION OF THE JORDAN NORMAL FORM OF MATRICES
We establish that the problem of computing the Jordan normal form of a matrix over a field F is in [ ] for F being a field of characteristic zero or a finite field.