Clément Pernet
Research Subjects
Clément Pernet has a total of 62 co-authors. Here are the top co-authors by number of shared publications:
- Jean-Guillaume Dumas
Laboratoire Jean Kuntzmann (UMR 5224), CNRS, Université Grenoble Alpes, Grenoble, France
27 shared publications - Erich Kaltofen
North Carolina State University
6 shared publications Ziad Sultan
5 shared publicationsArne Storjohann
Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
4 shared publicationsJean-Guillaume Dumas
4 shared publicationsThierry Gautier
4 shared publications
Latest Publications
- 15 October 2025
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 134
Towards automated generation of fast and accurate algorithms for recursive matrix multiplication
- 15 October 2025
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 134
Towards automated generation of fast and accurate algorithms for recursive matrix multiplication
- Open Access
A non-commutative algorithm for multiplying a 3×4 matrix by a 4×7 matrix using 63 non-complex multiplications
The number of scalar multiplications required to multiply a $3\times4$ matrix by a $4\times7$ matrix was reduced from 66 in [11] to 63 in [9] by an algorithm over complex numbers. We propose an algorithm in 63 multiplications with only rational coefficients, hence removing the requirement that the base field for the arithmetic operations contains a square root of -1, while it still needs to contain an inverse of 2. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm.Open AccessA non-commutative algorithm for multiplying a 3×4 matrix by a 4×7 matrix using 63 non-complex multiplications
The number of scalar multiplications required to multiply a $3\times4$ matrix by a $4\times7$ matrix was reduced from 66 in [11] to 63 in [9] by an algorithm over complex numbers. We propose an algorithm in 63 multiplications with only rational coefficients, hence removing the requirement that the base field for the arithmetic operations contains a square root of -1, while it still needs to contain an inverse of 2. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm. - Open Access
A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications
The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two~\(\matrixsize{4}{4}\) matrices was first reduced in~\cite{Fawzi:2022aa} from~\(49\) (two recursion levels of Strassen's algorithm) to~\(47\) but only in characteristic~\(2\) or more recently to~\(48\) in~\cite{alphaevolve} but over complex numbers.\par We propose an algorithm in~\(48\) multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers.We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in~\({\frac{19}{16}n^{2+\frac{\log_2{3}}{2}} +o\!\left({n^{2+\frac{log_2{3}}{2}}}\right)}\) operations over any ring containing an inverse of~\(2\).Open AccessA non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications
The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two~\(\matrixsize{4}{4}\) matrices was first reduced in~\cite{Fawzi:2022aa} from~\(49\) (two recursion levels of Strassen's algorithm) to~\(47\) but only in characteristic~\(2\) or more recently to~\(48\) in~\cite{alphaevolve} but over complex numbers.\par We propose an algorithm in~\(48\) multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers.We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in~\({\frac{19}{16}n^{2+\frac{\log_2{3}}{2}} +o\!\left({n^{2+\frac{log_2{3}}{2}}}\right)}\) operations over any ring containing an inverse of~\(2\). - Open Access
- 16 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 254-263
Strassen's algorithm is not optimally accurate
We propose a non-commutative algorithm for multiplying 2 × 2-matrices using 7 coefficient products. This algorithm reaches simultaneously a better accuracy in practice compared to previously known such fast 2 × 2 algorithms and a time complexity bound with the best currently known leading term (obtained via alternative basis sparsification). To build this algorithm, we consider matrix and tensor norm bounds governing the stability and accuracy of numerical matrix multiplication. First, we reduce those bounds by minimizing a growth factor along the unique orbit of Strassen’s 2 × 2-matrix multiplication tensor decomposition. Second, we develop heuristics that minimize the number of operations required to realize a bilinear formula, while further improving its accuracy. Third, we perform an alternative basis sparsification that improves on the time complexity constant and mostly preserves the overall accuracy.
- 16 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 254-263
Open AccessStrassen's algorithm is not optimally accurate
We propose a non-commutative algorithm for multiplying 2 × 2-matrices using 7 coefficient products. This algorithm reaches simultaneously a better accuracy in practice compared to previously known such fast 2 × 2 algorithms and a time complexity bound with the best currently known leading term (obtained via alternative basis sparsification). To build this algorithm, we consider matrix and tensor norm bounds governing the stability and accuracy of numerical matrix multiplication. First, we reduce those bounds by minimizing a growth factor along the unique orbit of Strassen’s 2 × 2-matrix multiplication tensor decomposition. Second, we develop heuristics that minimize the number of operations required to realize a bilinear formula, while further improving its accuracy. Third, we perform an alternative basis sparsification that improves on the time complexity constant and mostly preserves the overall accuracy.
- 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
- 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
- Open Access
- 5 August 2022
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 115, 285-315
Some fast algorithms multiplying a matrix by its adjoint
- 5 August 2022
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 115, 285-315
Open AccessSome fast algorithms multiplying a matrix by its adjoint
- Open Access
Dynamic proofs of retrievability with low server storage
Proofs of Retrievability (PoRs) are protocols which allow a client to store data remotely and to efficiently ensure, via audits, that the entirety of that data is still intact. A dynamic PoR system also supports efficient retrieval and update of any small portion of the data. We propose new, simple protocols for dynamic PoR that are designed for practical efficiency, trading decreased persistent storage for increased server computation, and show in fact that this tradeoff is inherent via a lower bound proof of time-space for any PoR scheme. Notably, ours is the first dynamic PoR which does not require any special encoding of the data stored on the server, meaning it can be trivially composed with any database service or with existing techniques for encryption or redundancy. Our implementation and deployment on Google Cloud Platform demonstrates our solution is scalable: for example, auditing a 1TB file takes just less than 5 minutes and costs less than $0.08 USD. We also present several further enhancements, reducing the amount of client storage, or the communication bandwidth, or allowing public verifiability, wherein any untrusted third party may conduct an audit.
Open AccessDynamic proofs of retrievability with low server storage
Proofs of Retrievability (PoRs) are protocols which allow a client to store data remotely and to efficiently ensure, via audits, that the entirety of that data is still intact. A dynamic PoR system also supports efficient retrieval and update of any small portion of the data. We propose new, simple protocols for dynamic PoR that are designed for practical efficiency, trading decreased persistent storage for increased server computation, and show in fact that this tradeoff is inherent via a lower bound proof of time-space for any PoR scheme. Notably, ours is the first dynamic PoR which does not require any special encoding of the data stored on the server, meaning it can be trivially composed with any database service or with existing techniques for encryption or redundancy. Our implementation and deployment on Google Cloud Platform demonstrates our solution is scalable: for example, auditing a 1TB file takes just less than 5 minutes and costs less than $0.08 USD. We also present several further enhancements, reducing the amount of client storage, or the communication bandwidth, or allowing public verifiability, wherein any untrusted third party may conduct an audit.
- 2 October 2020
- Published by Springer Nature
- p. 335-357
Hermite Rational Function Interpolation with Error Correction
- 2 October 2020
- Published by Springer Nature
- p. 335-357
Hermite Rational Function Interpolation with Error Correction