CPClément Pernet

Clément Pernet

*This is an algorithmically generated author record based on publicly available information.

Clément Pernet has a total of 62 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

    • 19 June 2025
    • Published by HAL in HAL
    Open Access

    A non-commutative algorithm for multiplying a 3×4 matrix by a 4×7 matrix using 63 non-complex multiplications

    by Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic

    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.

    • 13 June 2025
    • Published by HAL in HAL
    Open Access

    A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications

    by Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic

    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

    Strassen's algorithm is not optimally accurate

    by Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic

    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

    Computing Krylov iterates in the time of matrix multiplication

    by Vincent Neiger, Clément Pernet, Gilles Villard

    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

    Exact computations with quasiseparable matrices

    by Clément Pernet, Hippolyte Signargout, Gilles Villard


    • 6 February 2023
    • Published by HAL in HAL
    Open Access

    Leading constants of rank deficient Gaussian elimination

    by Clément Pernet, Hippolyte Signargout, Gilles Villard

  • Open Access

    Some fast algorithms multiplying a matrix by its adjoint

    by Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic


  • Open Access

    Dynamic proofs of retrievability with low server storage

    by Gaspard Anthoine, Jean-Guillaume Dumas, Michael Hanling, Mélanie de Jonghe, Aude Maignan, Clément Pernet, Daniel Roche

    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.

  • Hermite Rational Function Interpolation with Error Correction

    by Erich L. Kaltofen, Clément Pernet, Zhi-Hong Yang