See the main course page: Modern algorithms for symbolic summation and integration

Master 2 in computer science, 2022-2023

Alin Bostan, Bruno Salvy, Gilles Villard

Livre en français : A. Bostan et al., Algorithmes Efficaces en Calcul Formel (pdf).

Book in english: J. von zur Gathen, J. Gerhard, Modern Computer Algebra.

Send a mail for the notes in english for the M1 Course 2021-2022.

[C] Maple worksheet for the special projections (X,Y,C), and determinant algorithm over a ring: BM-no-divisions.mw.gz.

[D] Maple worksheet for the general (abstract+naive) algorithm interpolation_bases.mw.gz.
      Also see e.g. the gfun maple package, with functions like seriestorec or seriestoalgeq.

■ A/ Matrices over a field

Wed Sept. 14

    P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic Complexity Theory, especially chapter 16.

    Decompositions: C.-P. Jeannerod, C. Pernet, A. Storjohann, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, 2013.

    Characteristic polynomial: V. Neiger, C. Pernet, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, 2021.

■ B/ Coppersmith's block Wiedemann algorithm

Thu sept. 15

    Don Coppersmith, Solving Homogeneous Linear Equations over GF(2) via Block Wiedemann Algorithm, 1994.

    E. Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, 1995.

    Application example: F. Boudot et al., Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment, 2020.

Wed Sept. 21

■ C/ Matrix determinant over a ring

    V. Strassen, Vermeidung von Divisionen, 1973.

    E. Kaltofen, On computing determinants of matrices without divisions, 1992.

    E. Kaltofen, G. Villard, On the complexity of computing determinants, 2005.

Thu sept. 22

■ D/ Minimal interpolation and approximant bases

    B. Beckermann, G. Labhan, Recursiveness in matrix rational interpolation problems, 1997.

    M. Van Barel, A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, 1992.

    W. Zhou, G. Labahn, Efficient algorithms for order basis computation, 2012.

    C.-P. Jeannerod, V. Neiger, É. Schost, G. Villard, Computing minimal interpolation bases, 2017.

To come. Thu oct. 13.

■ E/ Modular composition of univariate polynomials.

     R. P. Brent, H. T. Kung, Fast algorithms for manipulating formal power series, 1978.

     M. Nüsken, M. Ziegler, Fast multipoint evaluation of bivariate polynomials, 2004.

     K. S. Kedlaya, C. Umans, Fast polynomial factorization and modular composition, 2011.

     V. Neiger, B. Salvy, É. Schost, G. Villard, Faster modular composition, 2021.

     Related problems, examples: J. van der Hoeven, G. Lecerf, Accelerated tower arithmetic, 2019.

■ F/ Polynomial matrices: high-order lifting for linear system solution.