Pierre-Jean Spaenlehauer

Aude Le Gluher, Pierre-Jean Spaenlehauer, Emmanuel Thomé

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $ξ(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $ξ(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $ξ(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $ξ$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $ξ=0$ in the asymptotic formula.

Éric Schost, Pierre-Jean Spaenlehauer

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix $M$, the goal is to compute a matrix $M'$ of given rank $r$ in a linear or affine subspace $E$ of matrices (usually encoding a specific structure) such that the Frobenius distance $\lVert M-M'\rVert$ is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank $r$ and the linear/affine subspace $E$. We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank $r$ matrices in $E$. To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank Matrix completion (coordinate spaces) and denoising procedures (Hankel matrices). Experimental results give evidence that this all-purpose algorithm is competitive with state-of-the-art numerical methods dedicated to these problems.