Fast polynomial computations with space constraints

This habilitation thesis investigates polynomial algorithmics under space constraints, presenting time- and space-efficient algorithms for fundamental operations and introducing the first quasi-linear algorithm for sparse polynomial interpolation while addressing hard problems in sparse factorization and divisibility.

The Gist

Imagine you are a master chef in a massive, high-tech kitchen. Your job is to manipulate "recipes" (polynomials). Sometimes these recipes are long lists of ingredients (dense polynomials), and sometimes they are very short lists with just a few key spices (sparse polynomials).

Bruno Grenet's paper is a collection of advanced cooking techniques designed to solve two specific problems:

1. The "Tiny Kitchen" Problem: How do you cook these complex recipes if your kitchen counter is incredibly small? You can't spread out all your ingredients; you have to work in a tiny, constant amount of space.
2. The "Sparse Ingredient" Problem: How do you cook efficiently when the recipe only has a few ingredients, but the numbers describing them (the exponents) are astronomically large?

Here is a breakdown of his work using simple analogies.

---

Part I: Cooking in a Tiny Kitchen (Space-Efficient Algorithms)

For decades, mathematicians have developed "fast" ways to multiply or divide these polynomial recipes. However, these fast methods usually require a huge kitchen counter (lots of memory) to hold intermediate results. If you try to use a fast method in a tiny kitchen, you run out of space and have to throw things away, slowing everything down.

The Challenge:
Imagine you are trying to multiply two giant numbers. The "naive" way (doing it slowly) requires almost no counter space. The "fast" way (using a shortcut) usually requires a counter as big as the numbers themselves.

Grenet's Solution:
He figured out how to perform these fast calculations in a constant-sized kitchen. No matter how big the recipe is, he only needs a fixed number of small bowls and spoons.

• The "Reversible" Trick:
  Usually, when you do a calculation, you write the result down and keep the old numbers. Grenet's method is like a magic trick where you write the new number over the old one, but you do it in a way that you can "undo" the steps if you need to.

  • Analogy: Imagine you are rearranging furniture in a tiny room. Instead of moving a sofa to a hallway to make space for a table, you slide the sofa, put the table in the empty spot, and then slide the sofa back. You never needed the hallway; you just moved things around in a specific, reversible order.

• The "Cumulative" Approach:
  Instead of calculating a whole new result and storing it, he adds the new result directly into the existing space.

  • Analogy: Instead of buying a new box for every item you buy, you just keep adding items to the same box, rearranging them as you go.

Why it matters:
This is crucial for devices with limited memory (like old computers, embedded chips, or even quantum computers where "memory" is extremely expensive). It proves you don't need a massive warehouse to do fast math; you just need a clever way to shuffle your tools.

---

Part II: Cooking with Sparse Ingredients (Sparse Polynomials)

Now, imagine a recipe that says: "Take 1 cup of flour, skip 1,000,000 cups of sugar, take 1 cup of salt, skip 1,000,000,000 cups of pepper..."
In math, this is a sparse polynomial. It has a huge degree (the numbers are huge), but very few actual ingredients (terms).

The Problem:
Standard fast algorithms assume the recipe is a full list of ingredients. If you try to use a standard fast algorithm on a sparse recipe, it's like trying to fill a swimming pool with a teaspoon because you are counting every single drop of water, even the empty spaces. It becomes incredibly slow and inefficient.

The Goal:
Create a "Fast Fourier Transform" (FFT) for sparse recipes. The FFT is the magic tool that makes dense math fast. Grenet wanted to find the "Sparse FFT."

The Breakthroughs:

1. The "Magic Mirror" (Interpolation):
   To figure out what a sparse recipe actually is, you usually have to taste it at many points. Grenet developed a method to reconstruct the whole recipe from just a few "tastes" (evaluations).

   • Analogy: Imagine a broken mirror. You only have a few shards. Most people would say, "You can't see the whole picture." Grenet found a way to use the specific angles of those few shards to perfectly reconstruct the entire image of the person standing in front of it.

2. The "Integer" Success:
   He achieved a "quasi-linear" speed (almost the fastest possible) for polynomials with integer coefficients.

   • Analogy: He found a way to sort a massive, messy pile of mail where most letters are blank, but a few have huge, complex addresses, without having to read every single blank letter.

3. The "Noise" Problem (Unbalanced Coefficients):
   Sometimes, a recipe has one ingredient that is a mountain (a huge number) and the rest are pebbles. This makes the math unstable. Grenet developed a "Top-Down" approach: find the mountain first, remove it, and then deal with the pebbles.

   • Analogy: If you are trying to find a needle in a haystack, but the needle is actually a giant steel beam, you don't look for the needle first. You lift the steel beam out of the way, and then you look for the tiny needles hidden underneath.

4. Verification (Did I cook it right?):
   He also created a way to quickly check if a multiplication was done correctly without re-doing the whole calculation.

   • Analogy: Instead of re-cooking the entire cake to check if the ingredients were mixed right, you just take a tiny, random sample, taste it, and use a special "magic tongue" to instantly know if the whole cake is correct.

---

The Big Picture: Why Should You Care?

1. Efficiency: This research allows computers to do complex math using less memory and less energy. This is vital for the future of computing, especially as we move toward Quantum Computers, where memory (qubits) is incredibly scarce and expensive.
2. Cryptography & Security: Many encryption codes rely on these polynomial calculations. If we can do them faster and with less space, we can build more secure systems or break them faster (which helps us build better defenses).
3. Error Correction: When you stream a movie or send a text, errors happen. These algorithms help fix those errors quickly, even when the data is huge but mostly empty (sparse).

In Summary:
Bruno Grenet is like a master mechanic who figured out how to build a Formula 1 engine that fits inside a bicycle. He took the fastest math algorithms we have, which usually require a massive garage, and shrunk them down to fit in a pocket, while also inventing new ways to handle "empty" data so we don't waste time on things that aren't there.

Technical Summary

This document is a Habilitation à Diriger des Recherches (HDR) by Bruno Grenet, summarizing his research contributions to Computer Algebra, specifically focusing on polynomial computations under two distinct constraints: space efficiency and sparse representations.

The work is divided into two main parts:

1. Time- and Space-Efficient Polynomial Computations: Developing algorithms that are both fast (quasi-linear time) and use minimal memory (constant space).
2. Sparse Polynomial Computations: Developing algorithms that exploit the sparsity of polynomials (few non-zero terms) to achieve efficiency, including the first quasi-linear sparse interpolation algorithm over integers.

---

1. Problem Statement

Computer algebra has historically focused on time complexity, developing fast algorithms (e.g., FFT-based multiplication, fast Euclidean division) that often require linear or even super-linear space (e.g., $O(n \log n)$ or $O(n)$ extra registers).

• The Space Bottleneck: As hardware memory becomes a constraint (e.g., in embedded systems, large-scale data processing, or quantum computing), the trade-off between speed and memory usage is critical. Standard fast algorithms are often infeasible in strict space-constrained environments.
• The Sparsity Bottleneck: Many real-world polynomials are sparse (having $t$ non-zero terms where $t \ll \text{degree}$). Standard "dense" algorithms treat them as having degree $d$, resulting in exponential complexity relative to the input size (which is roughly $t \log d$). While sparse interpolation is a known problem, achieving quasi-linear time complexity (linear in the bit-size of the sparse representation) has been a long-standing open problem, particularly over finite fields.

2. Methodology

The author employs a combination of advanced algorithmic techniques:

Part I: Space-Efficient Algorithms

• Computational Models: The author rigorously defines computational models, distinguishing between:
  • ro/wo (Read-Only Input / Write-Only Output): The standard theoretical model, which imposes quadratic lower bounds on polynomial multiplication.
  • ro/rw (Read-Only Input / Read-Write Output): Allows overwriting the output buffer.
  • rw/rw (Read-Write Input / Read-Write Output): The most permissive model, allowing inputs to be overwritten.
• Techniques:
  • Recursive Decomposition: Adapting divide-and-conquer strategies (like Karatsuba and FFT) to use the output space as temporary workspace.
  • Pre- and Post-Additions: A technique to "undo" operations or distribute intermediate results without extra storage, effectively making algorithms reversible.
  • Transposition Principle: Using the duality between a linear map and its transpose to derive constant-space variants of standard algorithms.
  • In-Place Computation: Designing algorithms where the input is overwritten by the output (e.g., $f \leftarrow f/g$).

Part II: Sparse Polynomial Computations

• Black Box Interpolation: Using Prony's method (or Berlekamp-Massey) to reconstruct a polynomial from evaluations at powers of a root of unity.
• SLP (Straight-Line Program) Interpolation: Using folding (reduction modulo $x^p - 1$) to handle large exponents. This involves computing $f \pmod{x^p-1}$ and $(xf') \pmod{x^p-1}$ to recover exponents via the derivative trick.
• Unbalanced Handling: Developing Bottom-up and Top-down approaches to handle polynomials with coefficients of vastly different magnitudes (unbalanced coefficients).
• Verification: Using modular product verification (evaluating products modulo $x^p-1$ and at random points) to verify sparse products without computing the full product.

3. Key Contributions and Results

Part I: Time- and Space-Efficient Computations

• Constant-Space Reductions: The author proves that for fundamental operations (multiplication, division, interpolation), any linear-space algorithm can be converted into a constant-space algorithm with the same asymptotic time complexity (up to logarithmic factors).
  • Multiplication: Generic reductions for Full, Lower, Upper, and Middle products in the ro/rw and rw/rw models.
  • Division & Remainder: Constant-space Euclidean division and remainder computation.
  • Interpolation: Constant-space multipoint evaluation and interpolation.
• Cumulative Algorithms: Introduction of cumulative algorithms (e.g., $h \leftarrow h + f \times g$) which are essential for in-place operations.
• Linear Algebra: Application of these techniques to matrix multiplication (e.g., a constant-space variant of Strassen-Winograd algorithm) and other linear algebraic tasks.
• Reversibility: Many of the proposed algorithms are reversible, meaning they can be inverted to restore the original input. This is significant for quantum computing, where operations must be unitary (reversible) and ancilla qubits (extra space) are scarce.

Part II: Sparse Polynomial Computations

• Quasi-Linear Sparse Interpolation (Integers): The paper presents the first quasi-linear time algorithm for sparse interpolation over the integers ($\mathbb{Z}$).
  • It combines black-box techniques with modular arithmetic (using primes $p$ and lifting via Hensel lifting).
  • It handles both balanced (similar coefficient sizes) and unbalanced (varying coefficient sizes) cases.
• Sparse Arithmetic:
  • Multiplication: An output-sensitive algorithm for sparse multiplication over $\mathbb{Z}$ with complexity $\tilde{O}(t \log d)$, where $t$ is the sparsity and $d$ the degree.
  • Division & Divisibility: Algorithms for exact division and divisibility testing, including polynomial-time tests for specific structural divisors.
• Factorization: A reduction of multivariate sparse factorization to univariate factorization and low-degree factorization, utilizing Puiseux series and Gap Theorems.
• Root Finding in Finite Fields: A new deterministic root-finding algorithm for finite fields using Graeffe transforms and Tangent Graeffe transforms, improving practical performance over Berlekamp-Rabin for FFT-friendly fields.

4. Significance and Impact

• Bridging Theory and Practice: The work challenges the assumption that fast algorithms must consume significant memory. It demonstrates that time-space efficiency is achievable for core computer algebra operations.
• Quantum Computing Relevance: The reversible, constant-space algorithms are directly applicable to quantum algorithms, where minimizing ancilla qubits is a primary bottleneck. The author explicitly links these results to quantum factoring and modular multiplication.
• Sparse Interpolation Breakthrough: The quasi-linear interpolation over integers is a major theoretical advance, enabling efficient reconstruction of sparse polynomials from black-box access, which is crucial for applications in cryptography (e.g., Syndrome Decoding, Niederreiter cryptosystems) and error-correcting codes.
• Practical Performance: Experimental results (e.g., in the FFLAS-FFPACK library) show that these constant-space algorithms often perform competitively with, or even faster than, standard implementations due to reduced memory allocation overhead.
• Open Problems: The work clearly delineates remaining challenges, such as achieving quasi-linear sparse interpolation over finite fields (currently limited by discrete logarithm or root-finding bottlenecks) and generalizing the unbalanced coefficient handling to unbalanced exponents.

Summary of Algorithms

The document lists numerous specific algorithms, including:

• SemiCumulativeProduct, LowerProduct, MiddleProduct (Constant-space variants).
• Inversion, Division, EuclideanDivision (Constant-space variants).
• SparseInterpolationBB (Black box), SparseInterpolationSLP (SLP-based).
• SparseFoldedInterpolation (Quasi-linear over integers).
• ConstantSpaceStrassenWinograd (Matrix multiplication).
• ModularMultiplication (Finite field extensions).

In conclusion, Bruno Grenet's work provides a comprehensive framework for resource-constrained polynomial computation, establishing new theoretical bounds for space complexity and delivering the first quasi-linear solutions for sparse interpolation over integers, with broad implications for cryptography, coding theory, and quantum computing.